21. Cryptography: Hash Functions

What this lecture covers

This lecture asks what makes a hash function useful for security rather than for building a dictionary. Where earlier lectures treated hash functions as a way to spread keys across a table quickly, here the goal is the opposite: functions that are deliberately expensive to invert and that make collisions computationally impossible to find. The lecture introduces the "random oracle" as an ideal model, then works through the concrete properties - one-wayness, collision resistance, target collision resistance, and non-malleability - that real hash functions like SHA try to approximate.

The lecture sits at the start of a two-lecture unit on cryptography (the next covers encryption) inside MIT's algorithms course. After watching, you should be able to name which property a given security scheme depends on, and reason about which properties do or don't imply each other.

Key ideas

• Cryptographic hash function: maps an arbitrary-length string to a fixed-length output (D bits) and must be deterministic, public (no secret keys), and behave randomly.
• Random oracle: an idealized hash function modeled as an infinite lookup table filled with true random answers, consistent on repeated queries; it clarifies why the real properties below are hard to achieve but cannot itself be built.
• One-wayness (OW / pre-image resistance): given a hash output Y, it's infeasible to find any input X with H(X) = Y.
• Collision resistance (CR): infeasible to find any two distinct inputs that hash to the same output.
• Target collision resistance (TCR): a weaker property - given a specific X, it's infeasible to find a different X' with the same hash; CR implies TCR but not the other way around.
• Non-malleability (NM): given H(X), it should be infeasible to produce H(X') for a related X' (e.g. X' = X + 1) without knowing X.
• Property independence: the lecture builds explicit counterexamples showing one-wayness does not imply TCR, and TCR does not imply one-wayness - the properties must be checked separately for each application.

Walkthrough

Defining the hash function and the random oracle (2:01)

The lecture sets up the definition: arbitrary-length input, fixed-length output of D bits, computed deterministically and publicly, with output that should look random. Because outputs are far too large to store as a table (on the order of 160 or 256 bits), these functions can't be dictionaries the way earlier hash functions were; they're used purely to compute a digest. The random oracle is introduced as an infinite "book" that answers each new query with a fresh random string and repeats old answers for repeated queries - a model that is deterministic and random by construction but impossible to implement, since it requires infinite storage.

One-wayness, collision resistance, and TCR (16:11)

The lecture defines the core properties one at a time. One-wayness means no one can recover an input from an output. Simple hash functions used for dictionaries, such as x mod p, fail badly here because inverting them is trivial. Collision resistance (CR) forbids finding any colliding pair; target collision resistance (TCR) only forbids finding a collision for a specific given input, making it a strictly weaker requirement. Real deployed functions mentioned include MD4 and MD5 (by Ron Rivest, since broken), SHA-1, and the current SHA-3, with the point that achieving these properties requires many rounds of mixing, unlike constant-time dictionary hashes.

Proving the properties are independent (34:24)

Using constructed examples, the lecture shows CR implies TCR but TCR does not imply CR. It then builds a hash function H' that XORs two extra input bits together before feeding them into a one-way H: this H' stays one-way but has trivial target collisions, showing one-wayness does not imply TCR. A second construction - passing short inputs straight through unhashed while hashing longer ones normally - stays TCR but is not one-way, showing the reverse direction fails too.

Password storage (52:38)

The first application: systems store H(password) instead of the password itself, and compare H(entered password) against it at login. This only requires one-wayness, assuming the password has enough entropy that it can't just be enumerated; the lecture argues that requiring collision resistance here would be over-engineering, since a false-positive collision on a random guess is already vanishingly unlikely and login-attempt limits handle the risk.

File modification detection and digital signatures (57:47)

Storing H(F) securely for a file F lets you detect later tampering by recomputing the hash; this requires TCR, since an adversary is handed a specific file and must find a different one with the same hash. The lecture then turns to digital signatures, where a large message M is hashed before signing for efficiency. Signing H(M) instead of M still needs TCR: an adversary who sees a signed H(M) must not be able to find a different M' with the same hash, since that would let them attach Alice's real signature to fake content.

Commitments and sealed-bid auctions (1:10:11)

The final and most demanding example: Alice submits C(X) = H(X) as a sealed bid, then later opens it to reveal X. This needs one-wayness (so other bidders can't learn X from the sealed commitment), collision resistance (so Alice can't find two bids that hash the same and pick whichever is convenient after seeing others' bids), and non-malleability (so no one can derive C(X+1) from C(X) without knowing X). The lecture closes with a contrived counterexample - a hash that satisfies all three named properties but still leaks the most significant bit of the bid - to show that the formal properties, while necessary, are not always sufficient in practice.

Before you watch

• Be comfortable with basic hash function ideas (collisions, hash tables) from earlier lectures in this course, since this lecture explicitly contrasts them with cryptographic hash functions.
• Some familiarity with modular arithmetic helps follow the x mod p and x^2 mod p examples used to illustrate broken one-wayness.

Check your understanding

1. Why can't the random oracle be implemented in practice, even though it satisfies all the desired properties?
2. Give an example (from the lecture or your own) of a hash function that is one-way but not target collision resistant.
3. Why does password storage only require one-wayness, while file-tamper detection requires target collision resistance?
4. Why does a sealed-bid auction commitment scheme need non-malleability in addition to one-wayness and collision resistance?