Solution Week 12

1. Birthday Attack on 80-bit Hash Function

• Second Pre-image Resistance: As defined on pages 4 and 5 (property 5), second pre-image resistance means: given an input $x_1$ and its hash $h(x_1)$, it should be computationally infeasible to find a different input $x_2$ such that $h(x_1)=h(x_2)$.

  • A brute-force attack to find a second pre-image involves taking the known hash $h(x_1)$ and trying many different inputs $x_2$ until one produces the same hash value.
  • For an $n$-bit hash function, there are $2^n$ possible output values. On average, you would expect to try $2^n$ different inputs $x_2$ to find one that hashes to the specific target value $h(x_1)$.
  • Therefore, for an 80-bit hash function ($n=80$), finding a second pre-image requires checking approximately $2^{80}$ messages.

• Collision Resistance & Birthday Attack: As defined on pages 4 and 5 (property 6), collision resistance means it should be computationally infeasible to find any pair of distinct inputs $x_1,x_2$ such that $h(x_1)=h(x_2)$. Finding such a pair is generally easier than finding a second pre-image due to the Birthday Attack (explained on pages 6-9).

• Proof using Birthday Attack:

  1. Goal: Find any two distinct messages $x_i,x_j$ that hash to the same value.
  2. Method: The attacker generates a sequence of distinct messages $x_1,x_2,x_3,...,x_t$ and computes their corresponding hash values $h(x_1),h(x_2),h(x_3),...,h(x_t)$.
  3. Collision Check: After computing each new hash $h(x_k)$, the attacker checks if this value matches any of the previously computed hash values ($h(x_1)$ to $h(x_{k-1})$).
  4. Probability: The probability of finding a collision increases as more messages are hashed. The Birthday Paradox shows that a surprisingly small number of messages are needed to have a high probability of collision.
  5. Calculation: For an $n$-bit hash function, there are $N=2^n$ possible hash outputs. The number of messages $t$ needed to find a collision with a certain probability $\lambda$ (e.g., $\lambda =0.5$ or 50%) is approximated by the formula derived on page 9: $t\approx \sqrt{2^{n+1}\ln (1/(1-\lambda ))}$ For a probability of 50% ($\lambda =0.5$), $\ln (1/(1-0.5))=\ln (2)\approx 0.693$. $t\approx \sqrt{2^{n+1}\ln (2)}\approx \sqrt{2\ln (2)}\times \sqrt{2^n}\approx 1.177\times 2^{n/2}$ The most important consequence (page 9) is that $t$ is roughly proportional to the square root of the number of possible outputs: $t\approx \sqrt{N}=\sqrt{2^n}=2^{n/2}$.
  6. Applying to n=80: For an 80-bit hash function, $n=80$. The number of messages needed to find a collision via the birthday attack is approximately: $t\approx 2^{80/2}=2^{40}$ (Page 9 gives a slightly more precise estimate of $2^{40.2}$ for 50% probability).

• Conclusion: While finding a second pre-image for an 80-bit hash requires approximately $2^{80}$ operations (computationally infeasible), finding any collision using the birthday attack only requires approximately $2^{40}$ operations. This is significantly less effort and demonstrates why collision resistance requires roughly twice the number of bits compared to pre-image resistance for the same security level against brute-force/birthday attacks.

2. Time to Find Second Pre-image for 64-bit Hash

• Effort Required: As established in Q1, finding a second pre-image for an $n$-bit hash function requires approximately $2^n$ tests (hash computations).

• Given:

  • Hash output length $n=64$ bits.
  • Attacker speed = $2^{20}$ tests per second.

• Calculation:

  • Total tests needed $\approx 2^{64}$.
  • Time = (Total Tests) / (Tests per Second)
  • Time $\approx \frac{2^{64}}{2^{20}}$ seconds
  • Time $\approx 2^{64-20}$ seconds
  • Time $\approx 2^{44}$ seconds

• Converting to Years (Optional but helpful for scale):

  • Seconds per year = $365.25\times 24\times 60\times 60\approx 31,557,600$ seconds.
  • This is roughly $2^{25}$ seconds/year (since $2^{25}=33,554,432$).
  • Time in years $\approx \frac{2^{44}}{2^{25}}$ years
  • Time in years $\approx 2^{44-25}$ years
  • Time in years $\approx 2^{19}$ years
  • $2^{19}=524,288$ years.

• Answer: It would require approximately $2^{44}$ seconds (or roughly half a million years) to find the second pre-image for a 64-bit hash function at the given attacker speed.

3. SHA-512 Padding

• Context: SHA-512 processes data in 1024-bit blocks. Before hashing, the message $M$ is padded to ensure its total length is a multiple of 1024 bits after appending a 128-bit length field.

• Padding Rule: The total length after padding and adding the length field must satisfy: $(|M|+|P|+128)\equiv 0(\mathrm{mod}1024)$ where $|M|$ is the original message length, $|P|$ is the padding length, and 128 is the length of the length field.

• The padding $P$ consists of a single ‘1’ bit followed by zero or more ‘0’ bits. This means $|P|\ge 1$.

• An equivalent formula for $|P|$ is: $|P|\equiv (-|M|-128)(\mathrm{mod}1024)$ The actual value of $|P|$ is the smallest positive integer satisfying this congruence.

• (i) Number of padding bits for |M| = 2590 bits:

  • $|M|=2590$
  • $|P|\equiv (-2590-128)(\mathrm{mod}1024)$
  • $|P|\equiv (-2718)(\mathrm{mod}1024)$
  • To find the positive remainder, we can add multiples of 1024:
    • $-2718+3\times 1024=-2718+3072=354$
  • So, $|P|\equiv 354(\mathrm{mod}1024)$.
  • The smallest positive integer value for $|P|$ is 354.
  • Check: $(|M|+|P|+128)=(2590+354+128)=3072$. Since $3072=3\times 1024$, $3072\equiv 0(\mathrm{mod}1024)$. The condition holds.
  • Answer (i): The number of padding bits is $|P|=354$ bits.

• (ii) Padding needed if |M| is a multiple of 1024 bits:

  • Let $|M|=k\times 1024$ for some non-negative integer $k$.
  • Substitute into the congruence: $(k\times 1024+|P|+128)\equiv 0(\mathrm{mod}1024)$
  • Since $k\times 1024\equiv 0(\mathrm{mod}1024)$, this simplifies to: $(|P|+128)\equiv 0(\mathrm{mod}1024)$
  • $|P|\equiv -128(\mathrm{mod}1024)$
  • $|P|\equiv -128+1024(\mathrm{mod}1024)$
  • $|P|\equiv 896(\mathrm{mod}1024)$
  • The smallest positive integer value for $|P|$ is 896.
  • Since $|P|$ must be at least 1 (padding always starts with a ‘1’ bit) and the calculation yields $|P|=896$, padding is indeed required.
  • Reasoning: Even if the original message length aligns perfectly with the block boundary (like $|M|=1024$), we still need to append the 128-bit length field. To make the total length (Message + Padding + Length Field) a multiple of 1024, padding is necessary. In this specific case, 896 bits of padding (a ‘1’ followed by 895 ‘0’s) are added.
  • Answer (ii): Yes, padding is always needed. If the original message length $|M|$ is a multiple of 1024, 896 bits of padding are required.