Randomness and Pseudorandomness

Length Extension Attacks

Overview

• Merkle-Damgard hash functions are susceptible to length extension attacks
  • given $y=H(x)$ for some unknown $x$, attackers can calculate $z=H(x \text{ || padding || } s)$ for arbitrary $s$
  • that is, given: $y = \text{SHA-256}(???)$an attacker can produce: $z = \text{SHA-256}(\text{??? || original padding || suffix})$
  • this doesn’t violate preimage, second-preimage, or collision resistance

Why This Matters

• suppose Alice and Bob use this as a verifier: $v := \text{SHA-256}(k \text{ || } m)$

  graph LR
  A["Alice"] -- m,v --> B["Mallory"] -- m',v' --> C["Bob"]

1. Alice sends $m = \text{"Please go to the bank."}$
2. Mallory doesn’t know $k$, but can apply length extension to $(m,v)$ to calculate $v'$ for: m' = \text{"Please go to the bank. [original pad] Then transfer \10,000 to Mallory.”}$
3. Since $v'$ is the correct verifier for $m'$, Bob will accept the modified message as valid

Illustration

$H(\text{S || "Please go to the bank."}) :=$

1. let $b_0 = \text{S || "Please go to the bank." || [original padding]}$
2. let $S$ be a 256-bit secret key
3. run:

   graph LR
   A["$$b_0$$"] --> B["h"]
   C["$$\text{constant }y_0$$"] --> B
   B --> D["$$y_1 = H(\text{S || ``Please go to the bank.``})$$"]
   

H(\text{"Please go to the bank." || [original padding] || "Then transfer \10,000 to Mallory.”}) :=$

1. let $b_0 = \text{S || "Please go to the bank." || [original padding]})$
2. let b_1 = \text{"Then transfer \10,000 to Mallory.” || [new padding]}$
3. run:

   graph LR
   A["$$b_0$$"] --> B["h"]
   C["$$\text{constant }y_0$$"] --> B
   B --> D["$$y_1$$"]
   E["$$b_1$$"] --> F["$$h$$"]
   D --> F
   F --> G["$$y_2 = \text{H(S || ``Please go to the bank.`` || [original padding] || ``Then transfer \$10,000 to Mallory.``)}$$"]
   

Solution: HMAC

• Message Authentication Code (MAC) - secure verifier:

  • inputs: key, arbitrary length data
  • output: fixed-size digest (n bits)

• HMAC construction turns any secure hash function $H()$ into a MAC: $\text{HMAC}_k(m) = H(k \oplus c_1 \mathbin{\|} H(k \oplus c_2 \mathbin{\|} m))$ where $c_1 = 363636 \dots$ and $c_2 = 5c5c5c \dots$

  • this design protects against length extension

• Alice and Bob can use this for protecting message integrity: $v := \text{HMAC-SHA-256}_k(m)$

  graph LR
  A["Alice"] -- m,v --> B["Mallory"] -- m',v' --> C["Bob"]
  

  • Alice computes and sends $v := \text{HMAC-SHA-256}_k(m)$
  • Bob rejects if $v' \neq \text{HMAC-SHA-256}_k(m')$

Choosing a “secret” Key $k$

• select a uniform random value
• true randomness - output of a physical process that is inherently unpredictable
  • inherent in all physical systems (Heisenberg)
  • absent in simplest abstract Turing machine
• can’t determine a process is random by looking at the output
• requires assessing the generation procedure
• true randomness is expensive; we often want to take a small amount of it and create a longer sequence that’s “as good as random”

Pseudorandom Generator (PRG)

Pseudorandom Function (PRF):

- $f_k : \{0,1\}^m \rightarrow \{0,1\}^n$
- $m$-bit input and $n$-bit output
- cannot practically distinguish $f_k(x)$ from random function without knowing $k$

Pseudorandom Generator (PRG):

- $g_k : \perp \rightarrow \{0,1\}^n \text{ for } n = \text{poly}(|k|)$
- $k$ is a truly random seed
- no other inputs
- output is much larger than the input (can think of output as stream of bits)
- cannot practically distinguish $g_k()$ from a random stream of bits without knowing $k$

Security Definition (testing the effectiveness of PRF $f_k()$):

1. choose secret $k$ and an RF $g()$
2. flip a coin to get bit $b$
3. if $b=0$, let $h() := g()$ if $b=1$, let $h() := f_k()$
4. Mallory chooses $x$; we announce $h(x)$ repeat as many times as Mallory likes
5. Mallory guesses $b$ in polynomial time

• we say PRF $f()$ is a secure if Mallory can’t do meaningfully better than random at guessing if it’s a PRF or RF
• note that Mallory can always determine if a function is a PRF given infinite time via a brute force attack