Hash Functions & Merkle Structures

• Hash properties: preimage, second preimage, collision
• Merkle-Damgard construction
• Padding and length encoding
• Length extension attacks
• Merkle trees and proofs
• Domain separation and encoding

Hash security goals

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

Collision resistance is weaker

Merkle-Damgard

• Pad message to block size
• Iterate compression function
• Final chaining value is digest

Streaming but length extension exists

Padding

• Append 0x80
• Zeros until length mod 64 == 56
• Append 64-bit bit length

Padding is part of the message

Length extension

• MAC = H(key || msg) is unsafe
• Attacker can append data and forge MAC
• Fix: HMAC or AEAD

HMAC intuition

• Inner hash and outer hash are both keyed
• Breaks the continuation property
• Safe against length extension

Merkle trees

• Leaves hashed, nodes hash children
• Root commits to all leaves
• Proof size O(log N)

Domain separation

• Tag inputs: leaf vs node
• Encode lengths or use canonical formats
• Avoid ambiguous concatenation

Pitfalls

• Raw hash as MAC
• No domain separation
• Non-canonical encodings
• Assuming collision resistance implies preimage

What you will build

• SHA-256 from scratch
• Merkle root + proofs
• Length extension attack
• Hash commitments