Design Strategies: How to Construct A Hashing Mode?

Recap

In our previous blog, we explored the fundamental properties of cryptographic hash functions (CHFs) and discussed their crucial role in maintaining the integrity and security of data with 3MI Labs. In this post, we delve into the architectural strategies behind hash functions. These strategies, or modes of operation, are essential for how cryptographic hash functions handle variable-length inputs while producing fixed-length digests. Understanding these modes helps clarify the strengths and limitations of various hashing approaches, especially in modern applications like secure messaging, blockchains, and digital signatures.

Hash Function Modes: Iterated vs. Tree-Based

Cryptographic hash functions rely on different operational modes to process inputs of arbitrary length. These modes manage how data is broken down and processed, ensuring efficient and secure output. Two primary mode design paradigms we'll explore are Iterated aka sequential hashing (e.g., Merkle-Damgård and Sponge hash) and Tree-Based aka parallel hashing (e.g., Merkle Tree Hashing).

1. Merkle-Damgård Construction (Iterated Hashing)

In this section, we first discuss the Merkle-Damgård construction which is a cornerstone of iterated hashing techniques. It processes input data by breaking it into fixed-size blocks and applying a compression function (CF) repeatedly. The result of each compression is passed to the next step along with the next block, and after processing the final block, the hash is produced.

How It Works:

• Padding: The input is padded to ensure its length is a multiple of the block sizer (typically 512 bits for algorithms like SHA-256). To avoid trivial collisions, padding rules are required to be one-to-one mappings. A commonly used padding rule is — concatenating the input with a "1" bit followed by enough "0" bits to make the padded input length a multiple ofr.
• Initialisation Vector (IV): The process begins with a fixed initialization vector (IV) ofc bits, which serves as the initial state for the hash function. Think of this as the hash’s starting point.
• Block-wise Compression: Each message block is processed one by one through the (r+c)-to-c bit compression functionf. The output of one block becomes the input to the next.
• Final Hash Output: After processing the last block, the final state serves as the hash output. See Figure 1 for a pictorial representation of the Merkle-Damgård construction.

Figure 1: Block Diagram of Merkle-Damgård Construction using CFf

Key Features:

• Efficiency: This construction is efficient for processing large messages due to its block-by-block approach. It’s used in widely known hash functions like MD5 and SHA-2.
• Security: If the underlying compression function is collision resistant/preimage-resistant/second preimage-resistant, the Merkle-Damgård construction is provably also collision resistance/preimage-resistant/second preimage-resistant, respectively.

Are We Good?: The Length Extension Attack

One notable vulnerability in the Merkle-Damgård construction is the length extension attack. This attack exploits the fact that, given a hash of a messageH(m), an attacker can compute the hash of an extended messagem||m′ without knowing the content of the original messagem. This occurs because of how intermediate states are reused across block boundaries, making the construction predictable to a certain extent. See Figure 2 for a block description of this attack.

Note that length extension attack on Merkle-Damgård shows that basic cryptographic hash propoerties like collision resistance and pre-image resistance may not be sufficient for security in many hash applications.

Figure 2: Visual Representation of Length Extension Attack

2. Sponge Construction

The Sponge construction is a relatively recent innovation, offering greater flexibility and security over traditional designs like Merkle-Damgård. It is a versatile mode capable of processing an arbitrary-length input, while producing an output of configurable length.

How It Works:

• Absorb Phase: The input message is absorbed into the internal state of the sponge. Unlike the fixed block size in Merkle-Damgård, the sponge function uses a larger internal state; often split into a “capacity” and “rate”. The input message is XORed with the rate portion of the state in a block-wise manner.
• Permutation/Transformation: After each absorption step, a transformation functionf (often a cryptographic permutation like the one used in Keccak, which powers SHA-3) is applied to the internal state. This ensures that the internal state remains unpredictable.
• Squeeze Phase: Once the input is fully absorbed, the sponge can begin producing the output (the hash). The state is transformed repeatedly, and portions of the state are “squeezed out” as the hash output. See Figure 3 for a pictorial representation of Sponge construction.

Figure 3: Block Diagram of Sponge Construction

Advantages:

• Resistance to Length Extension Attacks: Unlike Merkle-Damgård, the sponge function resists length extension attacks due to safely discardingc bits of capacity from the last function outputs. We will see in the upcoming blog that this simple idea of final truncation also helps Sponge to achieve even stronger provable security namely indifferentiability from a random oracle which is a popular assumption considered nowadays for hash functions in many protocols including ZK proof systems.
• Versatility: The sponge construction is suitable for more than just hashing; it can be used for functions like authenticated encryption and random number generation.

Applications:

• SHA-3: The sponge construction is the foundation of SHA-3, the newest member of the SHA family, offering robust security features compared to its predecessors (SHA-1, SHA-2).
• Cryptographic Protocols: The sponge’s flexibility also makes it ideal for protocols that require both hashing and encryption, such as payment systems, secure file storage, secure login systems and Blockchain technology.

3. Merkle Tree Hashing (Tree-Based Hashing)

Merkle Tree Hashing is particularly useful in distributed and hierarchical systems where efficient verification of large datasets is necessary. This mode splits the input into smaller pieces, hashes each part, and combines them in a tree structure, with the final root hash representing the entire data set.

How It Works:

For simplicity, let us assume that the compression function is two-to-one.

• Splitting the Input: The message is split into multiple smaller chunks (leaf nodes), each of length at most half of the primitive’s input length.
• Hashing the Chunks: These chunks are paired up and then each pair is hashed with one call to the primitive.
• Building the Tree: These hash values are combined pairwise, and each pair is hashed again to form the next level of the tree, continuing this process until only one hash (the root hash) remains (as exemplified with an 8-block message in Figure 4).

Figure 4: Block Diagram of Merkle Tree Hashing

Advantages:

• Efficient Verification: Merkle trees are incredibly efficient for verifying the integrity of large datasets. One can verify the integrity of any chunk by only rehashing a portion of the tree. More specifically, rehashing the sub-tree defined by the intermediate hash values along the path from the target chunk to the root.

Applications:

• Blockchain: Merkle trees are critical in blockchain systems (such as Bitcoin), where verifying transaction histories without recalculating the entire chain is necessary. Simply put, each block in a blockchain contains a Merkle root, which is a compact cryptographic summary of all transactions in that block. To verify a specific transaction, you don’t need to process all transactions in the block. Instead, you use the Merkle root and a Merkle proof—a small subset of hashes from the tree—to confirm the transaction’s inclusion efficiently.
• File Systems: Distributed file systems like IPFS use Merkle trees to verify data integrity across nodes.

Comparing Modes: Security and Efficiency

Each hashing mode offers unique trade-offs between security and efficiency:

• Merkle-Damgård is efficient and has been widely deployed, but it suffers from length extension vulnerabilities. It’s still a strong candidate when used for basic cryptographic hash properties like collision resistance or when combined with countermeasures like HMAC to avoid length extension attacks.
• Sponge constructions, like those in SHA-3, are highly flexible and offer stronger security guarantees than Merkle-Damgård, especially when it comes to resilience against length extension attacks.
• Merkle Tree Hashing is essential for distributed systems that require frequent and efficient integrity verification of large datasets. It is better for scenarios where subset verification, dynamic and incremental updates, or parallel computation is required.

Conclusion

Choosing the right hashing mode is critical for ensuring both the security and performance of a cryptographic system. While Merkle-Damgård is a tried-and-tested strategy, more modern approaches like Sponge functions offer greater flexibility and stronger security properties. Merkle Tree Hashing provides a highly efficient way to verify data integrity in distributed systems, making it a staple in applications like blockchain.

In our next blog, Provable Security of Hash Functions: Reducing Security from Hashing Modes to Underlying Primitives, we’ll explore how to formally analyse the security of different hashing modes. We will take an intuitive look at adversarial models and security goals for hash functions, before diving deep into two specific modes—Merkle-Damgård and Sponge—to understand how their security (by indifferentiability from random oracle) can be reduced to underlying primitives. We’ll also explore how indifferentiability captures length extension and similar attacks.

Stay tuned!