🔐 Keyed Hashing

1. What Is Keyed Hashing?

Regular hash functions (e.g., SHA-256) compute fixed-length digests from input messages, and anyone can compute or verify them. But in scenarios where only someone with a secret key should be able to compute or validate a hash, Keyed Hashing is used. It is mainly used for:

✅ MAC (Message Authentication Code): Ensures message integrity and authenticates sender
🎲 PRF (Pseudorandom Function): Produces unpredictable, random-looking outputs

---

2. MAC (Message Authentication Code)

✅ Concept

• MAC(K, M) = T where K is a secret key, M is the message, and T is the tag

• Sender computes the tag with K, and the receiver verifies it with the same K

• Ensures integrity + authenticity

• Widely used in TLS, IPSec, SSH

⚠️ Attack Models

• Forgery: Attacker tries to generate a valid MAC without the key

• Chosen-Message Attack: Attacker can query tags for messages of their choice

• Replay Attack: Reuses previously captured message/tag pairs

---

3. PRF (Pseudorandom Function)

✅ Concept

• PRF(K, M) should output values indistinguishable from random

• Stronger security guarantees than MACs

• Used in TLS, 4G authentication, key derivation functions, etc.

• 🔄 All PRFs are secure MACs, but not all MACs are secure PRFs

---

4. How to Build Keyed Hashes

❌ Secret-Prefix: Hash(K || M)

• Vulnerable to length-extension attacks

• Ambiguity if keys of different lengths result in same K || M

❌ Secret-Suffix: Hash(M || K)

• Can be broken if there's a collision between M1 and M2

✅ HMAC (Hash-based MAC)

• Standard construction used in practice

• Formula: HMAC(K, M) = Hash((K ⊕ opad) || Hash((K ⊕ ipad) || M))

• Secure even if the underlying hash (e.g., SHA-256) supports length extension

• Used in TLS, SSH, IPSec, etc.

---

5. Generic Attacks on Hash-Based MACs

🎯 Birthday Attacks

• For an n-bit hash, ~2^(n/2) queries may produce a collision

⚠️ MAC Forgery via Length-Extension

• Possible if using SHA-256-like hashes with poorly constructed MACs

---

6. Block Cipher–Based MAC: CMAC

✅ CMAC (Cipher-based MAC)

• Safe alternative to CBC-MAC

• Based on block ciphers like AES

• Final block processed with K1 or K2 (depending on padding)

• No IV needed — deterministic output is okay for MACs

---

7. Dedicated MAC Designs

✅ Poly1305

• Extremely fast (used in Google, OpenSSH)

• Based on Universal Hash + PRF (Wegman–Carter MAC)

• Example: Tag = Poly1305(K1, M) + AES(K2, nonce)

• ⚠️ If nonce is reused, security breaks completely

✅ SipHash

• Optimized for short messages (e.g., hash table protection)

• Structure: simple rounds of SipRound → final XOR

• Example: SipHash-2-4 = 2 compression rounds, 4 finalization rounds

• ⚠️ Sponge-based → vulnerable if internal state leaks

---

8. Side-Channel Attacks

🕵️‍♂️ Timing Attacks

• Comparing MAC tags byte-by-byte leaks timing info

• Solution: use constant-time comparison functions

🧠 Sponge Internal State Leaks

• Sponge-based MACs (e.g., SHA-3, SipHash) can be reversed if internal state is leaked

• HMAC & CMAC (compression-based) are safer in such scenarios

---

✅ Recommendations Summary