Security of Hash Functions and MACs

Security of Hash Functions and MACs

1. How Each Breaks (beginner threat map!)

Hash breaks via collisions (birthday $2^{n/2}$!) or length-extension (append + recompute!). MAC breaks via forgery (valid tag for new message!) or key recovery. Brute force baselines: hash $2^{n}$, MAC key $2^{k}$!

2. Attack Table (exam!)

Attack	Targets	Cost / Defence
Birthday collision	hash (any pair!)	$2^{n/2}$ → need $n ≥ 256$!
Length extension	Merkle-Damgård hash (MD5/SHA-256!)	append trick → use HMAC/SHA-3!
Existential forgery	MAC (chosen-message oracle!)	must stay infeasible!
Replay	both (old pair resent!)	nonce/timestamp!
Timing	MAC compare (early exit!)	constant-time compare!

3. Security Levels (exam numbers!)

MD5 (128-bit): collisions in seconds — BROKEN (no security use!)
SHA-1 (160-bit): SHATTERED 2017 — BROKEN!
SHA-256: 128-bit collision strength — SAFE (2026, full 64 rounds unbroken!)
HMAC-SHA256: safe iff key secret + unique (even if hash weak-ish!)
CBC-MAC: safe only fixed-length (variable → extension forgery!)

4. Practice Rules (viva!)

$n ≥ 256$ for hashes, keys ≥ 128 bits, random keys (never password-direct!), rekey periodically, separate keys per purpose (encrypt vs MAC)!

5. Exam Points

• Attack table + levels — 7 marks, very frequent.
• Length-extension + constant-time — 5 marks, favourite traps.