1️⃣ What is a cryptographic hash function? List three main characteristics (slides 4–5).
✅ fixed output, deterministic, one‑way
Maps arbitrary-size input to fixed-size output (e.g., 256 bits).
Deterministic: same message → same hash.
One‑way: infeasible to reverse (find input from hash).
2️⃣ Explain what it means that a hash function is deterministic. How does the word "over" example (slide 6) illustrate this?
✅ same input → same hash; small change → completely different
Deterministic: the same message always yields the same hash.
The illustration shows that even a tiny change (like "over") drastically changes the output (avalanche effect).
3️⃣ Define the three core security properties: hiding (pre‑image resistance), second pre‑image resistance, collision resistance (slide 8).
✅ pre‑image, 2nd pre‑image, collision
Hiding (pre‑image): given H(x), infeasible to find x.
Second pre‑image: given x, infeasible to find y≠x with H(x)=H(y).
Collision resistance: infeasible to find any distinct x,y with H(x)=H(y).
4️⃣ What is the difference between second pre‑image resistance and collision resistance? Which is easier for an attacker? (slide 12)
✅ 2nd pre‑image: fixed x; collision: choose both – collision easier
Second pre‑image: attacker is given a specific x and must find a different y with same hash.
Collision: attacker can choose any x and y – easier due to birthday paradox.
5️⃣ For a 128‑bit hash, how many attempts on average does it take to break pre‑image resistance by brute force? (slide 13)
✅ ~2¹²⁷ attempts
Total possibilities 2¹²⁸; average case you find it halfway → 2¹²⁷.
6️⃣ Why does a hash function not always provide hiding when the message space is small? How can we fix it? (slide 14)
✅ solution: add random r (uniform) before hashing
If only few possible messages, attacker can hash all and compare.
Fix: choose a random r (uniform) and compute H(r | x); then given H(r|x), x remains hidden.
7️⃣ Do collisions exist for cryptographic hash functions? If yes, why can't we find them easily? (slides 16–17)
✅ collisions exist (pigeonhole); finding them is infeasible
Input space is infinite (or huge), output space fixed. By pigeonhole principle, collisions must exist.
But hash is designed so that finding them is computationally infeasible.
8️⃣ Explain the birthday paradox in the context of hash functions. How many people (birthdays) correspond to 23? (slide 20)
✅ sqrt(N) gives 50% collision chance
With N possible outputs, about sqrt(N) random inputs yield a 50% probability of a collision.
For birthdays (N=365), sqrt(365)≈23 people gives 50% chance two share a birthday.
9️⃣ For a 128‑bit hash, how many trials to find a collision with ~50% probability? How does this compare to pre‑image? (slide 21)
✅ ~2⁶⁴ trials (birthday bound); pre‑image ~2¹²⁷
Collision resistance strength ≈ 2^(m/2). 128‑bit → 2⁶⁴ attempts; pre‑image requires ~2¹²⁷. Collision is easier.
🔟 What does n‑bit security level mean? Does a 256‑bit hash provide 256‑bit collision security? (slide 23)
✅ 2ⁿ ops to break; collision gives only n/2‑bit security
n‑bit security = attacker needs 2ⁿ operations. For hash, collision resistance is ~2^(n/2) due to birthday paradox, so 256‑bit hash gives ~128‑bit collision security.
1️⃣1️⃣ List four real hash functions from slide 24. Which ones are considered broken or weak for collision resistance?
✅ MD5, SHA1, SHA2, SHA3; MD5 & SHA1 broken
MD5 (128‑bit) – collisions in ~2²¹ (broken).
SHA1 (160‑bit) – collisions in ~2⁶¹ (deprecated).
SHA2 (224–512‑bit) – still secure.
SHA3 – newest NIST standard, no known attacks.
1️⃣2️⃣ List at least five applications of cryptographic hash functions from slide 25.
✅ integrity, MAC, passwords, commitment, blockchain
Integrity – detect changes in files.
MAC – message authentication code.
Password storage – store hash instead of plaintext.
Commitment – e.g., online auctions.
Blockchain – chaining blocks using hashes.
1️⃣3️⃣ What is a Message Authentication Code (MAC)? Which two security services does it provide? (slide 26)
✅ MAC = hashing with key → authenticity + integrity
MAC uses a secret key to produce a tag; only someone with the key can verify.
Provides message authenticity (source verification) and integrity (detect changes).
1️⃣4️⃣ What does HMAC stand for? Give the high‑level formula from slide 28.
✅ Hash‑based MAC: H(k'' || H(k' || m))
HMAC = H( k'' | H( k' | message ) ), where k' and k'' are derived from the original key using ipad/opad.
1️⃣5️⃣ Why must collisions exist for any hash function with fixed output size? (pigeonhole principle) (slide 17)
✅ infinite inputs → finite outputs → collisions inevitable
The input space is arbitrarily large (or infinite), while output space is fixed (e.g., 2¹²⁸). By pigeonhole principle, at least two inputs must map to the same output.
1️⃣6️⃣ What is the rule of thumb for the number of random items needed for a 50% collision probability when there are N possibilities? (slide 20)
✅ approximately √N
If there are N different outputs, about √N randomly chosen inputs yield a 50% chance of a collision.
📐 FORMAL CONCEPTS – WEEK04 L2 (HASH FUNCTIONS)
🔁 Core properties
Pre‑image (hiding): given H(x), hard to find x
2nd pre‑image: given x, hard to find y≠x with H(x)=H(y)
Collision: hard to find any x≠y with H(x)=H(y)
⚡ Pre‑image brute force
128‑bit hash → average attempts = 2¹²⁷
m‑bit hash → average ≈ 2^(m‑1)
🎂 Birthday bound (collision)
For m‑bit hash, 50% collision after ~2^(m/2) trials
128‑bit → 2⁶⁴, 256‑bit → 2¹²⁸
📏 n‑bit security
Attacker needs 2ⁿ operations
Hash collision provides only n/2‑bit security
🧮 HMAC construction
HMAC = H(k'' || H(k' || m))
k' = key ⊕ ipad, k'' = key ⊕ opad
📦 Real hash examples
MD5 – 128‑bit (broken, 2²¹ collision)
SHA1 – 160‑bit (2⁶¹ collision, deprecated)
SHA2 – 224/256/384/512‑bit (secure)
SHA3 – 224/256/384/512‑bit (NIST standard)
🔐 MAC definition
Message Authentication Code
Provides authenticity + integrity
Uses a secret key
📉 Hiding fix (small space)
Add random r (uniform): H(r | x)
Given H(r|x), x remains hidden
🕊️ Applications
integrity checks · MAC · password storage
commitment schemes · blockchain
🧠 Pigeonhole principle
Inputs > outputs → collisions must exist
ACADEZI 2026