Return to Answer

Formally, we define the PRF-advantage of a random algorithm $D$ at distinguishing a family of functions $f_k$ (e.g., $\operatorname{HMAC-MD5}_k$) from uniform random to be: \begin{equation*} \operatorname{Adv}^{\operatorname{PRF}}_f(D) = |\Pr[D(f_k) = 1] - \Pr[D(u) = 1]|, \end{equation*} where $k$ is a uniform random key for the family $f_k$, and $u$ is a uniform random function. We conjecture that for any distinguisher algorithm $D$, $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is small enough we're not worried anyone can exploit it, as long as the computational cost of $D$ is within reason—fewer than $2^{128}$ bit operations, for instance. This formalism will come in handy later, but let's look at distinguishing strategies first.

So if you query the oracle on a whopping $q = 2^{64}$ inputs, with high probability you will find a collision $x_0 \ne x_1$; then to tell whether the oracle is HMAC-MD5 or a uniform random function, pick a suffix $y$, say a single zero bit or a GIF of a funny cat video, and query the oracle at two more inputs: $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$. If they still collide, the evidence is overwhelming in favor of HMAC-MD5 over a uniform random function.^† In particular, the conditional probability that $x_0 \mathbin\Vert y$ and $x_0 \mathbin\Vert y$ collides is 1 for HMAC-MD5, and $2^{-128}$ for a uniform random function. For any number of queries $q$ with this distinguisher, by the birthday paradox, $$\Pr[D(\operatorname{HMAC-MD5}_k) = 1] \approx q^2/2^{128}.$$

It turns out that this generic attack on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5. (There are other distinguishers for HMAC-MD5 from ‘HMAC’ over a uniform random function, but this is not really important for applications like MACs below, and their area*time cost is infeasibly large, well over $2^{128}$.) So the security conjecture for HMAC-MD5 is that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2/2^{128} + c/2^{256}$$ for any random algorithm $D$ making at most $q$ queries with area*time cost at most $c$. And since $2^{256}$ is a very large denominator, you do not have enough spare change rattling around your pocket to afford a computer large enough for long enough to make a dent in it, so we might skip that term altogether and call it $q^2/2^{128}$.^‡

If $f$ is HMAC-MD5 under a uniform random key, the forger succeeds and the distinguisher returns 1 with probability $p$. If $f$ is a uniform random function, the distinguisher returns 1 with probability $1/2^{128}$, because the probability that any fixed 128-bit string $a$ is equal to $f(m)$ when $f$ is a uniform random function is $1/2^{128}$. So we have \begin{align*} \Pr[D(f_k) = 1] &= p = \operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F), \\ \Pr[D(u) = 1] &= 1/2^{128}, \end{align*} from which we find that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = |\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) - 1/2^{128}|.$$ But the security conjecture for HMAC-MD5 is that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is very small for any distinguisher $D$. We can use that to conjecture that the forgery probability must also be very small: $$\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) \leq \operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) + 1/2^{128}.$$

Formally, we define the PRF-advantage of a random algorithm $D$ at distinguishing a family of functions $f_k$ (e.g., $\operatorname{HMAC-MD5}_k$) from uniform random to be: \begin{equation*} \operatorname{Adv}^{\operatorname{PRF}}_f(D) = \lvert\Pr[D(f_k) = 1] - \Pr[D(u) = 1]\rvert, \end{equation*} where $k$ is a uniform random key for the family $f_k$, and $u$ is a uniform random function. We conjecture that for any distinguisher algorithm $D$, $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is small enough we're not worried anyone can exploit it, as long as the computational cost of $D$ is within reason—fewer than $2^{128}$ bit operations, for instance. This formalism will come in handy later, but let's look at distinguishing strategies first.

So if you query the oracle on a whopping $q = 2^{64}$ inputs, with high probability you will find a collision $x_0 \ne x_1$; then to tell whether the oracle is HMAC-MD5 or a uniform random function, pick a suffix $y$, say a single zero bit or a GIF of a funny cat video, and query the oracle at two more inputs: $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$. If they still collide, the evidence is overwhelming in favor of HMAC-MD5 over a uniform random function.^† In particular, the conditional probability that $x_0 \mathbin\Vert y$ and $x_0 \mathbin\Vert y$ collides is 1 for HMAC-MD5, and $2^{-128}$ for a uniform random function. For any number of queries $q$ with this distinguisher, by the birthday paradox, $$\Pr[D(\operatorname{HMAC-MD5}_k) = 1] \approx q^2\!/2^{128}.$$

It turns out that this generic attack on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5. (There are other distinguishers for HMAC-MD5 from ‘HMAC’ over a uniform random function, but this is not really important for applications like MACs below, and their area*time cost is infeasibly large, well over $2^{128}$.) So the security conjecture for HMAC-MD5 is that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2\!/2^{128} + c/2^{256}$$ for any random algorithm $D$ making at most $q$ queries with area*time cost at most $c$. And since $2^{256}$ is a very large denominator, you do not have enough spare change rattling around your pocket to afford a computer large enough for long enough to make a dent in it, so we might skip that term altogether and call it $q^2\!/2^{128}$.^‡

If $f$ is HMAC-MD5 under a uniform random key, the forger succeeds and the distinguisher returns 1 with probability $p$. If $f$ is a uniform random function, the distinguisher returns 1 with probability $1/2^{128}$, because the probability that any fixed 128-bit string $a$ is equal to $f(m)$ when $f$ is a uniform random function is $1/2^{128}$. So we have \begin{align*} \Pr[D(f_k) = 1] &= p = \operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F), \\ \Pr[D(u) = 1] &= 1/2^{128}, \end{align*} from which we find that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = \lvert\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) - 1/2^{128}\rvert.$$ But the security conjecture for HMAC-MD5 is that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is very small for any distinguisher $D$. We can use that to conjecture that the forgery probability must also be very small: $$\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) \leq \operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) + 1/2^{128}.$$

f0_memo = {}
def f0(x):
    if x not in f0_memo:
        f0_memo[x] = os.urandom(16)
    return f0_memo[x]

k = os.urandom(64)
def f1(x):
    return hmac_md5(k, x)

def distinguisher(prf):
    y0 = prf('hello world')
    y1 = prf('query query quite contrary how does your crypto grow')
    ...
    return 1 if i_predict_it_was_f1 else 0

# Then the probability that distinguisher(f0) = 1 is not much different
# from the probability that distinguisher(f1) = 1.

f0_memo = {}
def f0(x):
    if x not in f0_memo:
        f0_memo[x] = os.urandom(16)
    return f0_memo[x]

k = os.urandom(32)
def f1(x):
    return hmac_md5(k, x)

def distinguisher(prf):
    y0 = prf('hello world')
    y1 = prf('query query quite contrary how does your crypto grow')
    ...
    return 1 if i_predict_it_was_f1 else 0

# Then the probability that distinguisher(f0) = 1 is not much different
# from the probability that distinguisher(f1) = 1.

You could try to guess $k$ and see if evaluating the oracle at some message $x$ yields $\operatorname{HMAC-MD5}_k(x)$, but there are $2^{512}$ possibilities for $k$, rendering that strategy computationally impossible—though formally we can conclude that there exists a distinguisher $D$ that queries the oracle only once such that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = c/2^{512}$, where $c$ is the number of times $D$ can afford to compute HMAC-MD5.^*

It turns out that this generic attack on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5. (There are other distinguishers for HMAC-MD5 from ‘HMAC’ over a uniform random function, but this is not really important for applications like MACs below, and their area*time cost is infeasibly large, well over $2^{128}$.) So the security conjecture for HMAC-MD5 is that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2/2^{128} + c/2^{512}$$ for any random algorithm $D$ making at most $q$ queries with area*time cost at most $c$. And since $2^{512}$ is a very large denominator, you do not have enough spare change rattling around your pocket to afford a computer large enough for long enough to make a dent in it, so we might skip that term altogether and call it $q^2/2^{128}$.^‡

_{^* If $D$ tried 1000 keys, it would obviously have a higher chance of success than if it tried only 1, but there is a higher cost to trying 1000 keys, whether you try them on one computer sequentially or a thousand computers in parallel. Note that multi-target attacks against $n$ targets at once may be cheaper than $n$ single-target attacks separately, but for a 512-bit key the difference doesn't matter for all imaginable numbers of targets $n$ in human existence. But beware using HMAC-MD5 with 128-bit keys!}

Let's suppose $k$ is 256 bits long. It could be as long as 512 bits for MD5 and fill an entire block, or technically longer, but there are problems with using keys that fill or exceed a block in HMAC, and 256 bits is perfectly adequate for serious security.

You could try to guess $k$ and see if evaluating the oracle at some message $x$ yields $\operatorname{HMAC-MD5}_k(x)$, but there are $2^{256}$ possibilities for $k$, rendering that strategy computationally impossible—though formally we can conclude that there exists a distinguisher $D$ that queries the oracle only once such that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = c/2^{256}$, where $c$ is the number of times $D$ can afford to compute HMAC-MD5.^*

It turns out that this generic attack on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5. (There are other distinguishers for HMAC-MD5 from ‘HMAC’ over a uniform random function, but this is not really important for applications like MACs below, and their area*time cost is infeasibly large, well over $2^{128}$.) So the security conjecture for HMAC-MD5 is that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2/2^{128} + c/2^{256}$$ for any random algorithm $D$ making at most $q$ queries with area*time cost at most $c$. And since $2^{256}$ is a very large denominator, you do not have enough spare change rattling around your pocket to afford a computer large enough for long enough to make a dent in it, so we might skip that term altogether and call it $q^2/2^{128}$.^‡

_{^* If $D$ tried 1000 keys, it would obviously have a higher chance of success than if it tried only 1, but there is a higher cost to trying 1000 keys, whether you try them on one computer sequentially or a thousand computers in parallel. Note that multi-target attacks against $n$ targets at once may be cheaper than $n$ single-target attacks separately, but for a 256-bit key the difference doesn't matter for all imaginable numbers of targets $n$ in human existence. But beware using HMAC-MD5 with 128-bit keys!}