Hash Functions

Hash Functions

1. What Is a Hash? (beginner — fingerprint!)

Hash $H(m)$ = fixed-size fingerprint of ANY-length message (SHA-256: always 256 bits!). One-way (can't un-hash!), deterministic (same $m$ → same digest!), avalanche (1-bit flip → half bits flip!).

2. Three Security Properties (exam list!)

Property	Attacker fails to...	Strength needed
Preimage (one-way!)	find $m$ from $H(m)$	$2^{n}$ work!
2nd preimage	find $m' ≠ m$ with same digest	$2^{n}$ work!
Collision	find ANY pair $m₁ ≠ m₂$ same digest	$2^{n/2}$ (birthday!)

3. Birthday Paradox (why half? exam favourite!)

23 people → 50% shared birthday (not 183 — pairs = 253!)
n-bit hash → collision after ≈ 2^{n/2} tries (pairs collide!)
SHA-256 (n=256) → 2¹²⁸ (safe!); MD5 (128) → 2⁶⁴ (broken!); SHA-1 (160) → 2⁸⁰ (broken 2017!)

4. Uses (exam map!)

File integrity (sha256sum!), password storage (salted + slow: bcrypt/scrypt — NEVER plain SHA!), hash-then-sign (sign digest, not full doc!), commitments, blockchains!

5. Exam Points

• Define + 3 properties + birthday math — 7 marks, very frequent.
• SHA-256 vs MD5/SHA-1 status — 3 marks, frequent.
• Never plain-hash passwords — 2-mark viva trap.