Hash Function Constructions, Merkle Trees, and Key Derivation

Corresponds to Chapter 8 (collision resistance, birthday attacks, and basic Merkle-Damgård are already covered in message-authentication-and-hash-functions). Joux’s attack shows that finding many multicollisions in an iterated (Merkle-Damgård) hash is much cheaper than the birthday bound might suggest, a structural weakness of the paradigm. Davies-Meyer is the standard way to build a compression function from a block cipher, with its own collision- resistance proof, underlying the SHA256 case study; HMAC builds a MAC from a hash function (secure even assuming only that Davies-Meyer is a secure PRF in the ideal cipher model), and SHA3/SHAKE use the structurally different sponge construction instead of Merkle-Damgård. Merkle trees let a prover commit to a large list and later prove membership/properties of one element efficiently — the basis for authenticated data structures (and, elsewhere in this vault, for hash-based signatures). Key derivation covers turning a weak or non-uniform secret into usable cryptographic key material, via the random oracle model, the leftover hash lemma, and the HKDF standard — and closes with second-preimage and target collision resistance as notions weaker than, but sometimes sufficient instead of, full collision resistance.

Outline (TODO — flesh out each)

• Building a MAC for large messages; birthday attacks (recap)
• Joux’s multicollision attack on Merkle-Damgård
• Building compression functions; Davies-Meyer
• Collision resistance of Davies-Meyer
• Case study: SHA256 and other Merkle-Damgård hash functions
• Case study: HMAC; Davies-Meyer as a secure PRF in the ideal cipher model
• The sponge construction; case study: SHA3, SHAKE128, SHAKE256
• Merkle trees; authenticated data structures
• Key derivation and the random oracle model
• The leftover hash lemma; case study: HKDF
• Second-preimage resistance; target collision resistance
• Fun application: commitments and auctions