Chapter III
Hashes and MACs
Fixed-size fingerprints for any data, and how adding a key turns them into tags nobody else can forge.
- III.1Hash functions
- III.2Three resistances
- III.3The birthday bound
- III.4Which hash today
- III.5MACs and HMAC
- III.6Key derivation
Hash functions
Any input in, a fixed-size fingerprint out, and no way to run it backwards.
The digest stands in for the data: same input, same digest. A cryptographic hash adds two demands: no way back except guessing, and no near misses, one changed bit flipping about half the output (the avalanche effect).
Aba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
Ba52d159f262b2c6ddb724a61840befc36eb30c88877a4030b65cbe86298449c9
122 of 256 bits differA coin toss per bit would give about 128.
Each square is one output bit, dark where the two digests disagree.
Three resistances
Preimage, second preimage, collision: the last one is the easiest to break, and the first to go.
Three things an attacker may look for, and the generic cost for an n-bit digest. Collisions are cheapest because both inputs are free: each new digest can match any earlier one.
The birthday bound
Collisions appear after about √(2ⁿ) tries, not 2ⁿ: 23 people already give even odds of a shared birthday.
What matters is whether any two people match, not whether someone matches you, and pairs grow with the square.
Which hash today
MD5 and SHA-1 are broken for collisions. Use SHA-256, SHA-3 or BLAKE2/BLAKE3.
MACs and HMAC
A checksum computed with a secret key: only key holders can produce or check the tag. HMAC builds one from a hash.
A MAC adds a secret key: the receiver recomputes the tag and compares. The obvious SHA-256(key ‖ message), ‖ meaning concatenation, is broken: the digest is SHA-256’s final internal state, and anyone can resume hashing from it.
- Server key
- b488beaafabb1afb3f81c8c239e76888b30d3146e92dce8c70a8096ee24df406
- Mallory’s token
- user=mallory&role=guest
- Its tag
- e65c85fc134f9c8b0f51fd75e1341372e36c48639aa934d88cea2c1202e6a31b
- Forged token
- user=mallory&role=guest\x80\x00×6\x01\xb8&role=admin
- Forged tag
- b9a2c7e4d8146d7d562561474cef1cf4faae1085b51a13286a7c72ac1f049d38
Forgery acceptedThe server recomputes the tag with its key: it matches.
Mallory resumed SHA-256 from the old tag. The bytes \x80\x00×6\x01\xb8 (×6 repeats the zero byte) are the padding SHA-256 itself added after the 55 bytes of key and token. She never saw the key; she only needed its length, which she can find by trying 1, 2, 3… until the server accepts.
Key derivation
HKDF turns one strong secret into as many independent keys as you need. Passwords are weak secrets and need a slow hash instead.
A key exchange (chapter V) leaves one shared secret; a protocol needs one key per job. TLS 1.3 derives all its keys this way.
In one breath
- Hash functions. Any input in, a fixed-size fingerprint out, and no way to run it backwards.
- Three resistances. Preimage, second preimage, collision: the last one is the easiest to break, and the first to go.
- The birthday bound. Collisions appear after about √(2ⁿ) tries, not 2ⁿ: 23 people already give even odds of a shared birthday.
- Which hash today. MD5 and SHA-1 are broken for collisions. Use SHA-256, SHA-3 or BLAKE2/BLAKE3.
- MACs and HMAC. A checksum computed with a secret key: only key holders can produce or check the tag. HMAC builds one from a hash.
- Key derivation. HKDF turns one strong secret into as many independent keys as you need. Passwords are weak secrets and need a slow hash instead.