06 — Hash, MAC, KDF

Hash functions (one-way, collision-resistant), Message Authentication Codes (MACs), Key Derivation Functions (KDFs). Fundamental components that appear in every protocol.

1. Cryptographic hash functions — properties

\(H: \{0,1\}^* \to \{0,1\}^n\) must satisfy:

For \(n = 256\): a collision costs \(2^{128}\) (≥ AES-128). That is why SHA-256 offers "128 bits of security" against collisions.

Additional useful properties

• Pseudorandomness: output indistinguishable from random.
• Avalanche: 1 bit changes in the input → ~50% of output bits change.
• Length extension resistance (non-MD constructions have it).
• Indifferentiability from RO (sponge construction).

2. Historical hash functions

MD2 (Rivest 1989) ❌

128 bits, 8-bit operations. Slow. Collisions found 1995 (Rogier-Chauvaud). Do not use.

MD4 (Rivest 1990) ❌

128 bits, faster. Broken in 1995 (Dobbertin); collision in 1996, practical in minutes by 2007 (Wang). Still used in NTLM password hashing (Windows) — vulnerable.

MD5 (Rivest 1991) ❌

128 bits, Merkle-Damgård. RFC 1321. The workhorse of the 1990s.

History of breaks:

• 1993: Den Boer + Bosselaers — pseudo-collision.
• 1996: Dobbertin — collision in the compression function.
• 2004: Wang Xiaoyun + Yu — first practical collision (rump session, CRYPTO '04).
• 2005: Lenstra-Wang-Weger — forges X.509 certificates.
• 2008: Marc Stevens et al. — chosen-prefix collision; forges a rogue CA certificate signed by RapidSSL.
• 2012: Flame malware (discovered) uses an MD5 chosen-prefix collision to forge a Microsoft Windows Update certificate. Estimated to have been developed by a government.

Status: collision in seconds on a commodity CPU. Do not use for anything cryptographic. Still OK for non-adversarial checksums (file integrity on a mirror).

SHA-0 (NIST 1993) ❌

160 bits. FIPS 180. Withdrawn in 1995 with no public explanation (suspected NSA fix).

SHA-1 (NIST 1995) ❌

160 bits. FIPS 180-1. Workhorse 1995–2010.

Breaks:

• 2005: Wang+Yin+Yu — 2^{69 operations (below the ideal 2}80).
• 2017: SHAttered (Stevens, Bursztein, Karpman, Albertini, Markov — Google + CWI) — first practical collision with chosen prefix. Cost ~110 GPU-years / US$110k in the cloud. Demo: two distinct PDFs with the same hash.
• 2020: Shambles (Leurent + Peyrin) — practical chosen-prefix collision at ~US$45k. Allows forging GPG/X.509 with an arbitrary identity.

Status: deprecated in any cryptographic context. Removed from TLS 1.3, Chrome/Firefox certs since 2017, OpenSSH since 2020. Acceptable only in HMAC-SHA1 (HMAC survives collisions, but migrate).

SHA-2 family (NIST 2001) ✅

FIPS 180-2 / 180-4. Merkle-Damgård with Davies-Meyer compression. Versions:

Length extension attack: given \(H(m)\) and \(|m|\), an attacker can compute \(H(m \\\| pad \\\| m')\) without knowing \(m\). That is why HMAC uses a specific structure.

Status: SHA-256 and SHA-512 with no practical break in 23 years. The modern standard. Hardware: Intel SHA Extensions (since Goldmont 2016), ARM Crypto Extensions.

SHA-3 / Keccak (NIST 2015) ✅

FIPS 202. Keccak won the NIST SHA-3 competition (2007–2012, 64 candidates). Designers: Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche (STMicroelectronics).

Non-Merkle-Damgård — uses a sponge construction:

1. Absorb: XOR plaintext into the "rate" of the state; permute (Keccak-f[1600]).
2. Squeeze: extract bits from the rate; permute for more.

The Keccak-f[1600] permutation = a 1600-bit state, 24 rounds of θρπχι.

XOF (Extendable Output Function): arbitrary-length output. Used in padding (Kyber, Dilithium), key stretching.

Immune to length extension by design (sponge absorb always XORs-with-padding before the last permutation).

Performance: software ~2× slower than SHA-256 (without hardware accel). Cheap in hardware/ASICs.

BLAKE2 / BLAKE3

BLAKE was a SHA-3 finalist (lost to Keccak). BLAKE2 (Aumasson, Neves, Wilcox-O'Hearn, Winnerlein 2012) — a refinement.

• BLAKE2b: 64-bit ops, output up to 64 bytes.
• BLAKE2s: 32-bit ops, output up to 32 bytes.
• Built-in keyed mode (replaces HMAC); personalization; tree mode.
• ~3× faster than SHA-256 in software, ~1.5× faster than SHA-512.
• RFC 7693.

BLAKE3 (O'Connor, Aumasson, Neves, Wilcox-O'Hearn 2020):

• Tree-based, arbitrary parallelism.
• ~10× faster than SHA-256 on a modern CPU.
• ~SHA-3 internals (ChaCha-like) with tree mode.
• XOF output up to 2^64 bytes.
• Used in recent IPFS, OpenZFS performance forks, age (partially).

RIPEMD-160 / RIPEMD-256 / RIPEMD-320

A European response in the mid-1990s. RIPEMD-160 is still used in Bitcoin addresses (HASH160 = RIPEMD160(SHA256(pubkey))). RIPEMD-128 broken; RIPEMD-160 has no practical attack but only 80 bits of collision security — below SHA-256.

Whirlpool (Rijmen + Barreto 2000)

A 512-bit hash based on an AES-like Miyaguchi-Preneel construction. ISOIEC 10118-3. Little practical use; superseded by SHA-23.

Streebog (GOST R 34.11-2012, Russia)

256/512 bit. A mandatory standard in Russian state systems.

SM3 (China GM/T 0004-2012)

256 bits, Merkle-Damgård. Mandatory in Chinese systems. Similar to SHA-256 in structure.

3. Hash recommendations (2026)

Anti-patterns

❌ MD5, SHA-1 in a cryptographic context. ❌ Truncating SHA-256 below 128 bits without analysis. ❌ Using a hash without salt for password storage (see §KDFs). ❌ Using a cryptographic hash in an internal hashmap (DoS via collision flooding). ❌ Assuming that the hash of a known string is a "secret" (rainbow tables).

4. MACs — Message Authentication Codes

A MAC guarantees integrity + authenticity (but not non-repudiation, because the receiver can forge).

Interface: \(\text{MAC}_k(m) = T\); verification compares the tag.

HMAC (RFC 2104, 1996)

Bellare + Canetti + Krawczyk. The universal standard. FIPS 198-1.

where \(opad = 0x5C5C\dots\), \(ipad = 0x3636\dots\).

• Works with any hash (HMAC-SHA256, HMAC-SHA3-256, HMAC-BLAKE2b).
• Resistant to length extension (double structure).
• Provably secure under the assumption that the hash is a PRF (Bellare 2006).
• HMAC-SHA-1 is still OK because a collision in the hash ≠ an HMAC forge.

KMAC (NIST SP 800-185, 2016)

A native MAC for Keccak/SHA-3. More efficient than HMAC-SHA3 (no double compression).

Poly1305

Bernstein 2005. A polynomial MAC over GF(\(2^{130} - 5\)). One-time MAC — requires a unique nonce. Always used in combination: ChaCha20-Poly1305, AES-GCM-Poly1305 variants. Blazing fast (3 cyclesbyte on ARM, ~1 cyclebyte with VEC).

CMAC (NIST SP 800-38B, RFC 4493)

A CBC-MAC variant with subkeys. AES-CMAC is the standard.

GMAC

The tag-only mode of GCM (no encryption). Used when only authenticity is required.

SipHash (Aumasson + Bernstein 2012)

Not for long messages; optimized for short inputs (up to a few KB). Resists hash flooding (DoS against a hashmap). The default keyed hash in the internal hashmaps of Rust, Python (3.4+), Ruby, Go, Perl, Haskell.

Anti-patterns

❌ MAC truncated below 64 bits. ❌ MAC without a nonce/IV in encrypt-then-MAC. ❌ Non-constant-time comparison (timing leak in verification) — use subtle.ConstantTimeCompare / crypto.timingSafeEqual. ❌ Using the same key for encrypt and MAC (derive via HKDF).

5. KDFs — Key Derivation Functions

KDF for cryptographic keys: HKDF

HKDF (Krawczyk + Eronen, RFC 5869, 2010). Two-phase:

prk = HMAC(salt, ikm)            // Extract
okm = HMAC(prk, info \\\| 0x01)
       \\\| HMAC(prk, okm[0..] \\\| info \\\| 0x02) ...   // Expand

• salt: public, ideally random (but zero is OK).
• ikm: input keying material (DH shared secret, master key).
• info: context binding (a string identifier for the use).
• okm: output, any length.

Used in the TLS 1.3 key schedule, Signal Protocol, Noise, MLS. The modern standard.

Other KDFs

• NIST SP 800-108 — KDF in counter mode, feedback, double pipeline.
• X9.63 KDF — used in legacy ECIES.
• Concat KDF — simple; used in JOSE.

Password-based KDFs (PBKDF)

Passwords have low entropy (human-memorable). An attacker runs a dictionary attack. A password KDF makes this intentionally expensive (memory, CPU).

PBKDF2 (RSA Labs 2000; RFC 8018)

PBKDF2(P, S, c, dkLen) = HMAC(P, S \\\| 1) \\\| HMAC(P, S \\\| 2) ...

• \(c\) = iterations (600k recommended for SHA-256 in 2026; OWASP).
• Easy GPU acceleration → weak against a modern attacker.
• Still OK for legacy compatibility.
• FIPS-approved.

bcrypt (Provos + Mazières 1999)

Based on a modified Blowfish key schedule (expensive to initialize). Memory: ~4 KB (fixed).

• Cost parameter \(\text{cost}\): \(2^{\text{cost}}\) iterations.
• Password limit: 72 bytes (truncation).
• Not FIPS.
• Massive adoption: legacy Linux PAM, Ruby/Rails default, PHP password_hash.

scrypt (Percival 2009; RFC 7914)

Memory-hard: forces the attacker to use memory, not just CPU. Anti-ASIC initially.

• Parameters: \(N\) (CPU/memory cost), \(r\) (block size), \(p\) (parallelism).
• 2026 OWASP: \(N = 2^{17}\), \(r = 8\), \(p = 1\) → ~64 MB memory.
• Taken from Litecoin proof-of-work.

Argon2 (Biryukov + Dinu + Khovratovich 2015)

Winner of the PHC (Password Hashing Competition 2013–2015). RFC 9106.

Variants:

• Argon2d: data-dependent memory access (resistant to TMTO; vulnerable to side-channel).
• Argon2i: data-independent (resistant to side-channel; less resistant to TMTO).
• Argon2id: recommended — hybrid: 1st pass data-independent, then data-dependent.

Parameters: memory \(m\), iterations \(t\), parallelism \(p\).

OWASP 2026 recommendation: Argon2id, \(m = 19\) MiB, \(t = 2\), \(p = 1\) (minimum) — tune for current hardware with a "1 second per verify" limit as the benchmark.

Comparison

6. Related constructions

Merkle trees

A hash tree. Leaves = \(H(\text{leaf}_i)\); nodes = \(H(\text{left} \\\| \text{right})\). The root is a commitment to all the data.

Inclusion proof: \(O(\log n)\) size. Lets you prove that \(x\) is in the set without revealing the whole set.

Applications:

• Git commit hashes (tree of blobs).
• Bitcoin block merkle root.
• Certificate Transparency (Google).
• Verkle trees proposed in Ethereum.
• BitTorrent (BEP 30).

HMAC-based One-Time Password (HOTP, RFC 4226)

Counter-based OTP. Moved on to event-based (Yubikey HOTP) and time-based (TOTP).

TOTP (RFC 6238)

\(\text{TOTP} = \text{HOTP}(k, \lfloor T/30 \rfloor)\). Google Authenticator, Authy, FreeOTP, 1Password, etc.

KDF for SRP, OPAQUE

PAKE (Password-Authenticated Key Exchange) protocols use a specific KDF construction to avoid an offline dictionary attack on the server side.

7. Hashes based on hard problems (RPM-friendly)

• Pedersen commitments: \(\text{Com}(m, r) = g^m h^r\) — perfectly hiding, computationally binding (under DLP). Used in ZK.
• VDF (Verifiable Delay Function): a hash that takes \(T\) sequential seconds (irreducible in parallel). Wesolowski 2019, Pietrzak 2019. Used in Ethereum lottery seeding, Filecoin proof-of-replication.
• VRF (Verifiable Random Function): a hash with a proof; publicly verifiable and deterministic. RFC 9381. Used in DNSSEC (NSEC5), blockchains.

8. Summary table — what to use where

9. Cross-reference

• Block ciphers used in CBC-MAC, GMAC: 04-symmetric.md.
• Hash-based signatures (SLH-DSA, XMSS, LMS): 08-post-quantum.md.
• Side-channel in HMAC (timing): 11-attacks.md.
• Collision attacks (MD5 chosen-prefix, SHA-1 SHAttered): 13-incidents.md.