Lecture 4 · Thursday 02 October 2025

Merkle-Damgård, Hash-Based Message Authentication Code (HMAC), authenticated encryption

The fourth lecture completes the symmetric toolkit. The Merkle-Damgård transform and sponge construction process arbitrary-length inputs, HMAC keys a hash safely and encrypt-then-MAC achieves Chosen-Ciphertext Attack (CCA) security.

Deck: 01_Crypto_101_Sym.pdf Chapter 1

Before ThisWhere Lecture 3 Left Off

Lecture 3 defined message authentication and priced bare hashing. Cipher Block Chaining Message Authentication Code (CBC-MAC) showed how a block cipher can tag messages, and its variable-length break showed how the chain can be turned against the scheme. Collision resistance was defined and bounded by the birthday argument. What remained was a hash function for arbitrary-length messages, a safe way to put a key into one and a composition of confidentiality with authenticity strong enough to survive a decryption oracle.

This LectureWhat It Adds

Four things. First, the Merkle-Damgård transform: iteration of a compression function with a length block, the collision-resistance theorem and the length-extension property that breaks the naive prefix Message Authentication Code (MAC). The stage on the chapter page continues a chain from a held tag. Second, the sponge: rate and capacity, the absorb and squeeze phases and the reason SHA-3 (Secure Hash Algorithm 3) digests cannot be extended. Third, Hash-Based Message Authentication Code (HMAC): the inner and outer key construction and why the outer hash closes the extension hole. Fourth, Chosen-Ciphertext Attack (CCA) security and authenticated encryption: the decryption-oracle game, the encrypt-then-MAC theorem and the deployed Authenticated Encryption with Associated Data (AEAD) schemes GCM (Galois/Counter Mode) and ChaCha20-Poly1305.

Study PlanWhat to Read, in Lecture Order

  1. Chapter 1 §10: Merkle-Damgård: from fixed to arbitrary length. The transform, the theorem and the length-extension forgery. Run the stage; the final beat shows the tag being extended without the key.
  2. §11: The sponge and SHA-3 (Secure Hash Algorithm 3). Rate and capacity, the Keccak permutation and the capacity-based security bound.
  3. §12: Hash-Based Message Authentication Code (HMAC). The keyed construction, the role of the inner and outer pads and the Pseudorandom Function (PRF) analysis.
  4. §13: Chosen-Ciphertext Attack (CCA) security and authenticated encryption. The Indistinguishability under Chosen-Ciphertext Attack (IND-CCA) game, the encrypt-then-Message Authentication Code (MAC) composition theorem and the Authenticated Encryption with Associated Data (AEAD) schemes in deployment.

PracticeExercises for This Lecture