Skip to content
CryptoVault

Chapter III

Hashes and MACs

Fixed-size fingerprints for any data, and how adding a key turns them into tags nobody else can forge.

  1. III.1Hash functions
  2. III.2Three resistances
  3. III.3The birthday bound
  4. III.4Which hash today
  5. III.5MACs and HMAC
  6. 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).

abc3 bytesba7816bf…32 bytesabd3 bytesa52d159f…32 bytesa × 1,000,0001,000,000 bytescdc76e5c…32 bytesSHA-256no way backone letter apart: 122 of 256 bits differ
Try it: change one character

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.

A hash has no key: anyone can compute it, so a digest proves data unchanged only if the digest itself comes from somewhere you trust.

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.

preimageba7816bf…findmwith this digest2n triesSHA-256: 225676792 → ba78after 76,793 triessecond preimageabcfindm′ ≠ abcsame digest2n triesSHA-256: 225676792 → ba78after 76,793 triescollisionnothing givenfindm ≠ m′same digest2n/2 triesSHA-256: 2128157, 251 → c75dafter 252 triesSHA-256 cut to its first 16 bits, trying 0, 1, 2…
Cut to 16 bits, a preimage takes 65,536 tries on average; a collision, two inputs of the attacker’s choosing, about 301.
When a hash is called broken, it almost always means collisions.

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.

0%50%100%0102030405060people in the roomtwo of them share a birthdayone of them shares yours23 people: 50.7%253 pairs to compare5.9%N possible values: a repeat after about √N draws365 → 23birthdays2128 → 264MD52160 → 280SHA-12256 → 2128SHA-256
Collision security is half the digest length: 128-bit security means SHA-256.

Which hash today

MD5 and SHA-1 are broken for collisions. Use SHA-256, SHA-3 or BLAKE2/BLAKE3.

1990200020102020MD5128 bits1992collision, 2004rogue CAFlameSHA-1160 bits1995collision, 2017SHA-2256, 512 bits2001BLAKE2256, 512 bits2012BLAKE3, 2020SHA-3224 to 512 bits2015
In red, from the first published collision on, and the real attacks MD5’s collisions made possible.
Default to SHA-256. MD5 and SHA-1 survive as checksums against accidental corruption, never where an attacker gains from a collision.

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.

SHA-256(key ‖ message)one 64-byte blockkey, 32 bytesuser=mallory&role=guest\x80\x00×6\x01\xb8SHA-256’s paddingIVcompresse65c85fc…the tag, publishedMMallory&role=adminpaddingcompressb9a2c7e4…acceptedHMACkey ⊕ 0x36…user=mallory&role=guestSHA-256key ⊕ 0x5c…5e29d409…inner digest, never publishedSHA-25679b31226…MMalloryextends this tag:rejected
HMAC hashes twice: its tag is not the state left after the message, so resuming from it gives a tag the server never computes.
Try it: forge a tag without the key
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.

Use HMAC-SHA-256, or the MAC built into an AEAD cipher (chapter IV), never a hash with a key glued in front. Compare tags in constant time (chapter VIII).

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.

0b × 22input secret000102…0csalt, publicextractHMAC(salt, secret)077709362c2e32df…PRK, 32 bytesexpandHMAC(PRK, label ‖ i)“client write key”46332297ba72d330…“server write key”0e67eea0a1a70820…
RFC 5869’s first test secret and salt; each label (the info) gives an unrelated key.
PitfallA password is not a strong secret: it needs a slow, salted, memory-hard function such as Argon2id, the subject of storing passwords in chapter VII.

In one breath

  1. Hash functions. Any input in, a fixed-size fingerprint out, and no way to run it backwards.
  2. Three resistances. Preimage, second preimage, collision: the last one is the easiest to break, and the first to go.
  3. The birthday bound. Collisions appear after about √(2ⁿ) tries, not 2ⁿ: 23 people already give even odds of a shared birthday.
  4. Which hash today. MD5 and SHA-1 are broken for collisions. Use SHA-256, SHA-3 or BLAKE2/BLAKE3.
  5. 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.
  6. 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.