Hash Functions & Merkle Structures

Why this module exists

Hashes are everywhere: integrity checks, passwords, signatures, blockchains, content-addressed storage, and protocols. But using them safely requires more than calling sha256.Sum256. You must understand what properties are actually provided, how the construction works, and where the attacks live.

This module goes deep on hash function security, Merkle-Damgard structure, length extension, domain separation, and Merkle trees. You will implement SHA-256 from scratch and perform a real attack on a naive MAC.

---

1) What a hash function promises (and does not)

A cryptographic hash is a deterministic function H(m) -> n bits with three core security properties:

• Preimage resistance: given y, hard to find m where H(m)=y.
• Second preimage resistance: given m, hard to find m' != m where H(m')=H(m).
• Collision resistance: hard to find any m1 != m2 with same hash.

These are different properties with different attack costs.

Generic costs for an n-bit hash

• Preimage: ~2^n
• Second preimage: ~2^n
• Collision: ~2^(n/2) (birthday bound)

The generic collision attack needs fewer trials than generic preimage search. Thus an ideal 256-bit hash offers approximately 128 bits of collision-search security; these work factors do not make the security definitions interchangeable.

---

2) Merkle-Damgard construction

Many classic hashes (MD5, SHA-1, SHA-256) are built using Merkle-Damgard:

1. Pad the message to a multiple of the block size.
2. Iterate a compression function over fixed-size blocks.
3. The final chaining value is the digest.

This gives streaming and incremental hashing: you can hash data as it arrives. But it also introduces a structural weakness: length extension.

---

3) Padding: the hidden part of the message

Merkle-Damgard padding is precise:

• Append a 1 bit (0x80).
• Append 0 bits until the message length is 56 mod 64 bytes.
• Append the original length (in bits) as a 64-bit big-endian integer.

For supported byte-message lengths, SHA-256 padding preserves the original message and its length; it does not itself create two distinct byte messages with identical padded blocks. Structured fields can still serialize ambiguously before padding, so specify their encoding separately.

---

Trace padding, schedule, and the first round

Use the byte string abc: hex 61 62 63, length 3 bytes or 24 bits. After the marker, 52 zero bytes, and the eight-byte bit length, it occupies one 64-byte block. The first big-endian word is W[0]=0x61626380; W[1] through W[14] are zero and W[15]=0x00000018. For this block, the schedule recurrence in the statement gives W[16]=0x61626380 and W[17]=0x000f0000. Rotations wrap bits around a 32-bit word; logical shifts fill the vacated high positions with zero.

Keep the eight-word chaining state separate from the eight working words. The supplied IV initializes the chain once per message. Every block copies the current chain into a..h, performs 64 rounds using its schedule, then adds the final working words back into that chain modulo 2^32. Resetting to the IV for every block would pass some short examples while breaking multi-block messages.

For the first abc round, using the supplied IV and K[0]:

Quantity	32-bit hexadecimal value
T1 = h + Sigma1(e) + Ch(e,f,g) + K[0] + W[0]	54da50e8
T2 = Sigma0(a) + Maj(a,b,c)	08909ae5
new a = T1 + T2	5d6aebcd
new e = old d + T1	fa2a4622

All right-hand sides use the old round values. The remaining moves are b=old a, c=old b, d=old c, f=old e, g=old f, h=old g. Updating a before computing the new b loses the needed old value unless it was saved. After all rounds and feed-forward, serialize the chain as big-endian words. The abc digest begins ba7816bf8f01cfea. The exact word operations are specified in FIPS 180-4, sections 5–6; the table here is a worked checkpoint, not a substitute for implementing all rounds.

Before coding the compressor, predict padding for 55 and 56 bytes. At 55, marker plus length fit exactly in one block. At 56, the marker forces the length into a second block: padding is 72 bytes, for 128 total. Test both boundaries and messages spanning several blocks against an independent digest, not only against another function sharing the same implementation.

4) Length extension attacks

If a system uses a naive MAC like:

MAC = H(key || message)

an attacker who knows MAC and message can compute a valid MAC for message || padding || suffix without knowing the key, provided they know or correctly guess the key length used to calculate the glue padding. This is a length extension attack and it breaks many homegrown protocols.

The fix is HMAC or any construction that hides the internal state and breaks the "continue hashing" property.

---

Count bytes in a continuation attack

Suppose the secret key has 8 bytes, the known message has 3 bytes, and the attacker wants a 2-byte suffix. The original hash consumed 11 message bytes, then 53 glue-padding bytes to finish a block. The known digest therefore represents a state after 64 processed bytes, not after 11.

The transmitted forged message has 3+53+2=58 bytes. The verifier prefixes its 8-byte key, so the final SHA-256 length field must count 64+2=66 bytes, or 528 bits. Call SHA256Continue(recoveredState, 64, suffix). Passing 11 as the continuation length or excluding glue from the transmitted message produces a different digest.

The continuation API starts at a complete block boundary (msgLen%64==0); it carries no pending partial block. Glue padding depends on the guessed key-plus-message length. A wrong guess does not reveal the key and generally does not authenticate. Application parsing must also permit the forged byte string for the attack to affect a command; hash extendability alone does not prove that a particular parser accepts padding bytes.

5) HMAC vs "hash + key"

HMAC does:

HMAC = H((key xor opad) || H((key xor ipad) || message))

Here key means the HMAC-normalized, block-sized key: hash an overlong key, then zero-pad it. Although an attacker can mechanically extend a published outer SHA-256 digest, that result is not the HMAC of an extended message. A verifier recomputes a keyed inner hash and hashes its fixed-length digest inside the keyed outer construction; it does not append attacker data after the outer digest. See RFC 2104.

---

6) Merkle trees: paths and their limits

This exercise hashes leaves as H(0x00 || data) and nodes as H(0x01 || left || right). Child hashes are fixed-width 32-byte values. The tags separate leaf and internal-node interpretations; they do not independently bind the original leaf count.

Let a,b,c be the three leaf hashes. Odd-level duplication gives parents u=Node(a,b) and v=Node(c,c), then root Node(u,v). A proof for c contains sibling c on the right, followed by u on the left. Verification must preserve that orientation at each level; sibling hashes without direction do not determine the same ordered tree.

The four-leaf list [a,b,c,c] creates the same parents and root as [a,b,c], with no hash collision. The construction therefore cannot by itself distinguish those original list lengths. This exercise's verifier receives no leaf count or index: it checks path reconstruction against the supplied root, not the original list size, root authenticity, or real-world validity of the leaf. A singleton leaf needs no siblings; its tagged leaf hash is already the root.

A proof has O(log N) hashes for this balanced construction. Changing one fixed-position leaf in a fixed-shape tree should change the root under collision-resistance assumptions; a bare statement that every possible list change changes the root would be false for the duplicate-last convention. Protocols can bind tree size or use a different shape rule; RFC 9162 section 2.1 specifies a different tree split and length-aware proof interfaces for transparency logs.

---

7) Domain separation and encoding

Hash inputs must be unambiguous. If you hash concatenations, you must separate domains and encode field boundaries to avoid identical byte encodings such as:

H("ab" || "c") == H("a" || "bc")

This equality is not a cryptographic hash collision: both sides hash the exact bytes abc.

Use the measure that addresses the ambiguity:

• Prefix with a tag (0x00 for leaf, 0x01 for node) to separate node kinds.
• Include lengths in a fixed-width format.
• Use structured serialization with canonical rules.

---

Serialize and open a commitment

Commit(message, nonce) hashes a protocol-specific byte encoding: 0x43 || uint64be(len(nonce)) || nonce || 0x4d || uint64be(len(message)) || message. For nonce [0xaa] and message OK, the preimage is:

43 | 0000000000000001 | aa | 4d | 0000000000000002 | 4f4b

That is 21 bytes: two tags, two eight-byte lengths, one nonce byte, and two message bytes. Lengths count bytes, not Unicode characters. Verification rebuilds exactly those bytes and compares the digest; field order and endian conventions are part of the commitment.

Binding asks whether someone can open the same commitment to different encoded messages. Hiding asks what an observer can learn before opening. A hash alone does not turn a 20-candidate secret with a public nonce into a large search space: enumerate 20 encodings and compare. A nonce must have sufficient unpredictable secret entropy for the intended hiding claim and is revealed with the message at opening. The API accepts empty nonces for mechanical encoding practice, but this does not make such use hiding.

Complete two boundary traces

For an original key-plus-message length of 60 bytes, derive the glue length and continuation length before adding a 5-byte suffix. Separately, count the commitment encoding bytes for a 2-byte nonce and a 3-byte message.

Reveal the traces

At 60 bytes, padding is 128-60=68 bytes. The continuation starts after 128 bytes; its final length field counts 133 bytes or 1064 bits after the suffix. The commitment encoding has 1+8+2+1+8+3=23 bytes. These lengths describe different layers: SHA padding counts the complete hash preimage; commitment field lengths delimit the application's nonce and message.

Implement SHA block boundaries before continuation, and leaf/node encoding before proof traversal. For transfer, reverse one Merkle sibling direction, change a commitment field boundary, and use a deliberately wrong key-length guess. Explain each rejection without appealing only to “the hashes differ.”

8) Practical pitfalls

• Hashing structured data without canonicalization (e.g., JSON with different key orders).
• Using a raw hash as a MAC (length extension risk).
• Reusing hashes across protocols without domain separation.
• Assuming collision resistance implies preimage resistance (it does not).

---

What you will build

1. SHA-256 from scratch: padding, message schedule, compression, and digest output.
2. Merkle root + proofs: build a tree and verify membership proofs.
3. Length extension attack: forge a MAC without the secret key.
4. Hash commitments: build a binding/hiding commitment with domain separation.

---

Key takeaways

• Hash security is about precise properties and attack costs.
• Merkle-Damgard gives streaming but enables length extension.
• HMAC exists for a reason. Do not roll your own MAC.
• Merkle trees give logarithmic proofs and tamper-evident structure.
• Encoding and domain separation distinguish intended message structures; they do not eliminate finite-output hash collisions.