28-05 — Hash Functions and Digital Signatures

Phase: Cryptography | Subject: 28-05 Prerequisites: 28-04-asymmetric-encryption.md Next subject: 28-06-elliptic-curve-cryptography.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define the three security properties of cryptographic hash functions
2. Explain the Merkle-Damgård construction and the SHA family
3. Describe the birthday attack and its implications for hash lengths
4. Explain how digital signatures work using RSA-PSS and ECDSA
5. Apply hash functions to data integrity, password storage, and blockchain

Core Content

Cryptographic Hash Functions

A hash function $H: {0,1}^* \to {0,1}^n$ maps arbitrary-length input to a fixed-length output (digest).

Three essential security properties:

⚠️ CRITICAL: Collision resistance is the strongest property. If it breaks, second preimage resistance may still hold (as with MD5 initially). But for modern use, all three must hold.

The Birthday Attack

The birthday paradox: with only 23 people, the probability of a shared birthday exceeds 50%.

For hash functions with $n$-bit output, a collision can be found with approximately $2^{n/2}$ random trials (not $2^n$).

Why: When you have $k$ hashes, the number of pairs is $\binom{k}{2} \approx k^2/2$. When $k^2/2 \approx 2^n$, i.e., $k \approx 2^{n/2}$, you expect a collision.

Implication: A hash function needs twice the bit length for collision resistance than for preimage resistance. SHA-256 has 128-bit collision resistance and 256-bit preimage resistance.

The Merkle-Damgård Construction

Most hash functions (MD5, SHA-1, SHA-256) use the Merkle-Damgård construction:

1. Pad input to a multiple of the block size
2. Append length encoding (prevents length extension attacks — partially)
3. Process blocks sequentially through a compression function $f$:

$$h_0 = IV$$ $$h_i = f(h_{i-1}, M_i)$$ $$H(M) = h_k$$

Strengths: simple, collision resistance of $f$ implies collision resistance of $H$.

Weakness: length extension attacks. Given $H(M)$, you can compute $H(M | \text{pad} | X)$ without knowing $M$. SHA-3 fixes this.

The SHA Family

SHA-256 compression: based on 64 rounds of operations on 8 × 32-bit state words, using message schedule, Ch, Maj, Σ functions. The design is ARX (Add-Rotate-XOR) for efficiency.

SHA-3 uses a sponge construction instead of Merkle-Damgård: absorb input, then squeeze output. This resists length extension attacks natively.

Applications of Hash Functions

Digital Signatures

A digital signature provides: authentication (who signed), integrity (content unchanged), and non-repudiation (signer cannot deny).

RSA-PSS (Probabilistic Signature Scheme):

Signing: $s = \text{PSS-Pad}(H(m))^d \bmod n$ Verification: check $\text{PSS-Pad}(H(m)) \equiv s^e \pmod{n}$

PSS padding is critical — it provides randomization per signature.

ECDSA (Elliptic Curve Digital Signature Algorithm):

Standardized curve + parameters. Private key $d$, public key $Q = dG$.

Signing: 1. Compute $e = H(m)$ (hash the message) 2. Choose random nonce $k$, compute $R = kG$, let $r = R_x \bmod q$ 3. Compute $s = k^{-1}(e + r \cdot d) \bmod q$ 4. Signature: $(r, s)$

Verification: 1. Compute $e = H(m)$, $w = s^{-1} \bmod q$ 2. Compute $u_1 = ew \bmod q$, $u_2 = rw \bmod q$ 3. Compute $X = u_1 G + u_2 Q$, verify $X_x \bmod q \equiv r$

⚠️ CRITICAL (ECDSA nonce): The nonce $k$ MUST be random and unique per signature. Sony's PS3 hack exploited ECDSA with a fixed $k$. If $k$ is reused or predictable, the private key is recoverable with two signatures.

EdDSA (Ed25519): deterministic nonce from hash, faster, simpler, no per-signature randomness needed.

Signature vs MAC

• MAC (Message Authentication Code): symmetric. Requires shared key. Both parties can create and verify. Example: HMAC-SHA256.
• Digital Signature: asymmetric. Only one party can create; anyone can verify. Provides non-repudiation.

Key Terms

• Hash Function — any-length input → fixed-length digest
• Preimage Resistance — one-way; given hash, can't find preimage
• Collision Resistance — can't find two inputs with same hash
• Birthday Attack — find collision in $2^{n/2}$ trials for $n$-bit hash
• Merkle-Damgård — iterated construction for hash functions (SHA-2)
• SHA-256 — 256-bit secure hash, 128-bit collision resistance
• Sponge Construction — SHA-3 design; absorb then squeeze
• Digital Signature — asymmetric: sign with private key, verify with public
• ECDSA — elliptic curve variant of DSA
• Nonce — number used once; critical for ECDSA security

Worked Examples

Example 1: Birthday Attack Calculation

How many random hash computations to find an SHA-256 collision with 50% probability?

Solution:

SHA-256 output is 256 bits. Collision resistance by birthday bound: $\approx \sqrt{\pi \cdot 2^{256} / 2} \approx 1.25 \cdot 2^{128}$.

That's $\approx 4 \times 10^{38}$ hash computations. For context: if you could compute $10^{12}$ hashes/second, it would take $4 \times 10^{26}$ seconds — far longer than the age of the universe.

Example 2: RSA Signature (simple, no padding)

Sign $m = 42$ with RSA private key $(n=143, d=103)$.

Solution:

Signature $s = 42^{103} \bmod 143$.

This is the same computation as decryption in the earlier RSA example. But since $\gcd(42, 143) \neq 1$ (143=11×13), let's use the fact that $42^{103} \equiv 42 \pmod{143}$... no, that's not right.

Actually, compute: $42 \equiv 9 \pmod{11}$ and $42 \equiv 3 \pmod{13}$.

Using CRT: compute $9^{103} \bmod 11$ and $3^{103} \bmod 13$. Since $103 = 10 \cdot 10 + 3$, $9^{103} \equiv 9^3 = 729 \equiv 729 - 66 \cdot 11 = 729 - 726 = 3 \pmod{11}$.

$3^{103} \bmod 13$: $\varphi(13)=12$, $103 = 8 \cdot 12 + 7$, $3^{103} \equiv 3^7 = 2187$, $2187 \div 13 = 168 \cdot 13 = 2184$, remain $3$.

$s \equiv 3 \pmod{11}$, $s \equiv 3 \pmod{13}$. So $s = 3$.

Verify: $3^7 \bmod 143 = 3^7 = 2187 \bmod 143$. $143 \cdot 15 = 2145$, $2187 - 2145 = 42$. ✓

Example 3: ECDSA Nonce Reuse

Suppose two messages $m_1, m_2$ signed with the same ECDSA nonce $k$, producing signatures $(r, s_1)$ and $(r, s_2)$ (same $r$ because same $k$). Show how the private key is recovered.

Solution:

$s_1 = k^{-1}(e_1 + r \cdot d) \bmod q$ $s_2 = k^{-1}(e_2 + r \cdot d) \bmod q$

Subtract: $s_1 - s_2 = k^{-1}(e_1 - e_2) \bmod q$ Thus: $k = (e_1 - e_2)(s_1 - s_2)^{-1} \bmod q$

Recover $k$, then: $d = r^{-1}(s_1 k - e_1) \bmod q$.

Private key exposed from just two signatures with the same nonce.

Quiz

Q1: What does the concept of Preimage resistance primarily refer to in this subject?

A) The definition and application of Preimage resistance B) A historical anecdote about Preimage resistance C) A computational error related to Preimage resistance D) A visual representation of Preimage resistance

Correct: A)

• If you chose A: Preimage resistance is defined as: the definition and application of preimage resistance. The other options describe different aspects that are not the primary focus. Correct!
• If you chose B: This is incorrect. Preimage resistance is defined as: the definition and application of preimage resistance. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Preimage resistance is defined as: the definition and application of preimage resistance. The other options describe different aspects that are not the primary focus.
• If you chose D: This is incorrect. Preimage resistance is defined as: the definition and application of preimage resistance. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) H: \{0,1\}^ \to \{0,1\}^n B) The inverse operation of the formula in question C) A simplified version of H: \{0,1\}^ \to \{0,1\}^... D) An unrelated formula from a different topic

Correct: A)

• If you chose A: The formula H: \{0,1\}^* \to \{0,1\}^n is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula H: \{0,1\}^* \to \{0,1\}^n is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula H: \{0,1\}^* \to \{0,1\}^n is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula H: \{0,1\}^* \to \{0,1\}^n is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Second preimage resistance?

A) It replaces all other methods in this domain B) It is used to second preimage resistance in mathematical analysis C) It is primarily a historical notation system D) It is used only in advanced research contexts

Correct: B)

• If you chose A: This is incorrect. Second preimage resistance serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: Second preimage resistance serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose C: This is incorrect. Second preimage resistance serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Second preimage resistance serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Collision resistance is TRUE?

A) Collision resistance is not related to this subject B) Collision resistance is a fundamental concept covered in this subject C) Collision resistance is mentioned only as a historical footnote D) Collision resistance is an advanced topic beyond this subject's scope

Correct: B)

• If you chose A: This is incorrect. Collision resistance is a fundamental concept covered in this subject. This subject covers Collision resistance as part of its core content.
• If you chose B: Collision resistance is a fundamental concept covered in this subject. This subject covers Collision resistance as part of its core content. Correct!
• If you chose C: This is incorrect. Collision resistance is a fundamental concept covered in this subject. This subject covers Collision resistance as part of its core content.
• If you chose D: This is incorrect. Collision resistance is a fundamental concept covered in this subject. This subject covers Collision resistance as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) A different result from a common mistake C) An unrelated numerical value D) RSA Signature (simple, no padding)

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is RSA Signature (simple, no padding). The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is RSA Signature (simple, no padding). The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is RSA Signature (simple, no padding). The other options represent common errors.
• If you chose D: The worked examples show that the result is RSA Signature (simple, no padding). The other options represent common errors. Correct!

Q6: How are Collision resistance and Data integrity related?

A) Collision resistance and Data integrity are closely related concepts B) Collision resistance is the inverse of Data integrity C) Collision resistance and Data integrity are completely unrelated topics D) Collision resistance is a special case of Data integrity

Correct: A)

• If you chose A: Both Collision resistance and Data integrity are covered in this subject as interconnected topics. Correct!
• If you chose B: This is incorrect. Both Collision resistance and Data integrity are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Collision resistance and Data integrity are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Collision resistance and Data integrity are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Password storage?

A) A common mistake is confusing Password storage with a similar concept B) Password storage is always computed the same way in all contexts C) The main error with Password storage is using it when it is not needed D) Password storage has no common misconceptions

Correct: A)

• If you chose A: Students often confuse Password storage with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose B: This is incorrect. Students often confuse Password storage with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: This is incorrect. Students often confuse Password storage with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse Password storage with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Digital signatures?

A) Use Digital signatures only in pure mathematics contexts B) Avoid Digital signatures unless explicitly instructed C) Digital signatures is not practically useful D) Apply Digital signatures to solve problems in this subject's domain

Correct: D)

• If you chose A: This is incorrect. Digital signatures is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. Digital signatures is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. Digital signatures is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: Digital signatures is a practical tool used throughout this subject to solve relevant problems. Correct!

Practice Problems

1. How many trials to find a preimage for SHA-256?
   

   Click for answer

   $2^{256}$ trials expected (brute force). Preimage resistance is 256 bits (full output length).

2. If $H$ is 64-bit output, how many random hashes for a birthday collision (~50%)?
   

   Click for answer

   ~$2^{32} \approx 4.3 \times 10^9$ hashes. This is very feasible — 64-bit hashes are insecure against collisions.

3. In RSA signing, why do we sign $H(m)$ rather than $m$ directly?
   

   Click for answer

   (1) Efficiency — hash is fixed-size, fast; (2) Security — prevents existential forgery attacks on raw RSA; (3) The hash reduces the message to the modulus size.

4. What problem does a salt solve in password hashing?
   

   Click for answer

   Without salt, identical passwords produce identical hashes (rainbow table attack). A salt makes each hash unique, forcing an attacker to crack each password individually.

5. Why is HMAC secure even when built on MD5 (which has collisions)?
   

   Click for answer

   HMAC security relies on the compression function's pseudorandomness, not on collision resistance directly. HMAC-MD5 remained secure long after MD5 collisions were found (though it's still discouraged today).

Summary

Key takeaways:

• Hash functions require preimage resistance (256-bit for SHA-256), but only 128-bit collision resistance
• Birthday attacks halve the effective security for collision resistance
• SHA-2 (Merkle-Damgård) and SHA-3 (sponge) are both secure; MD5/SHA-1 are broken
• Digital signatures = hash the message, then apply asymmetric operation
• ECDSA requires a unique random nonce per signature; EdDSA avoids this with deterministic nonces

Pitfalls

• Confusing collision resistance with preimage resistance. Collision resistance (hard to find any $x_1 \neq x_2$ with $H(x_1)=H(x_2)$) only requires $2^{n/2}$ work via the birthday attack. Preimage resistance (given $y$, find $x$ with $H(x)=y$) requires $2^n$ work. A 256-bit hash has 128-bit collision resistance, not 256-bit.
• Storing passwords with fast hashes like SHA-256. Fast hash functions let attackers test billions of passwords per second. Password storage requires slow, memory-hard functions (bcrypt, scrypt, Argon2) with a unique random salt per password to prevent rainbow table attacks.
• Reusing the ECDSA nonce $k$. Two signatures with the same $k$ produce the same $r$ value. From $(r, s_1)$ and $(r, s_2)$, an attacker can recover $k = (e_1-e_2)(s_1-s_2)^{-1} \bmod q$ and then the private key $d$. This is how Sony's PS3 signing keys were extracted.
• Thinking SHA-256 resists length extension attacks. Merkle-Damgård hashes (SHA-2, MD5) are vulnerable to length extension: given $H(M)$, an attacker can compute $H(M | \text{pad} | X)$ without knowing $M$. Use HMAC for MAC constructions, or SHA-3 which is immune.
• Assuming a digital signature encrypts the message. Signing is not encryption with the private key. RSA signing uses a hash and padding (PSS); ECDSA is entirely distinct from encryption. Signing provides authentication and integrity, not confidentiality.

Next Steps

Next up: 28-06-elliptic-curve-cryptography.md — smaller keys, same security, the future of asymmetric crypto.