Lecture 3 · Tuesday 30 September 2025

MACs and hashing

The third lecture adds authenticity to confidentiality. Message authentication codes are defined by an unforgeability game and Cipher Block Chaining Message Authentication Code (CBC-MAC) is built from the block cipher, then broken across message lengths. Collision-resistant hashing is priced by the birthday bound.

Deck: 01_Crypto_101_Sym.pdf Chapter 1

Before ThisWhere Lecture 2 Left Off

Lecture 2 gave a computational replacement for the one-time pad: AES (Advanced Encryption Standard) supplies a keyed permutation, the modes extend it to long messages and Indistinguishability under Chosen-Plaintext Attack (IND-CPA) says that an adversary with an encryption oracle cannot tell which of two messages was encrypted. The confidentiality game still assumes the eavesdropper Eve only reads. From this lecture on she also writes: she can modify, replay and inject traffic, so the scheme must make every such edit detectable.

This LectureWhat It Adds

The lecture defines a Message Authentication Code (MAC) as a keyed tag with a verification algorithm, then states existential unforgeability under chosen-message attack. Encryption alone gives no authenticity because ciphertexts are malleable. Cipher Block Chaining Message Authentication Code (CBC-MAC) reuses a block cipher as a tag: it is secure for fixed message lengths and forgeable across lengths. The lab runs the two-query forgery and checks the repair that encrypts the final block under an independent key. The lecture closes with preimage, second-preimage and collision resistance, followed by the birthday bound on digest length.

Study PlanWhat to Read, in Lecture Order

  1. Chapter 1 §7: Message authentication codes. The tag oracle, the unforgeability game and the malleability examples that motivate it.
  2. §8: Cipher Block Chaining Message Authentication Code (CBC-MAC), and the variable-length break. The fixed-length theorem, the two-query forgery and the two standard repairs. The lab below the section runs the forgery and the fix.
  3. §9: Collision-resistant hashing. The three resistance notions, their implications and the birthday bound with its digest-length consequence.

PracticeExercises for This Lecture