How many trials does it take to break HMAC-MD5?

Question

I know that you can find collision in MD5 with $2^{64}$ trials using Birthday paradox. Now everyone is saying that HMAC-MD5 is significantly more secure. How can I quantify this security? My question is how many trials does it take to find a collision in HMAC-MD5?

Answer 1

You can find a collision in MD5 at much lower cost than $2^{64}$ evaluations of MD5. You could do the same for HMAC-MD5, if you knew the key, which renders it unfit for unusual applications such as commitments.

But the standard security conjecture of HMAC-MD5 is that it is a pseudorandom function family, which assumes the adversary doesn't know the key. Any program the adversary writes which takes a function as a parameter and evaluates it as an oracle at arbitrary messages of its choice won't behave much differently whether you feed it (a) HMAC-MD5 under a uniform random choice of key, or (b) a uniform random choice of function.

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.

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.

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.^*

What about collisions? If you evaluate the oracle at $2^{64}$ different inputs, you would probably find a collision. That is true for HMAC-MD5 under a uniform random key and true for a uniform random function, so a priori, finding a collision doesn't break the security of a PRF by distinguishing them on its own. However, MD5 also has the property that if $x_0 \ne x_1$ collide under MD5, with $\operatorname{MD5}(x_0) = \operatorname{MD5}(x_1)$, then so do $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$ for any common suffix $y$, as long as $x_0$ and $x_1$ have the same length.

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}$.^‡

What about using HMAC-MD5 in an application, for instance as a message authentication code? It turns out that any pseudorandom function family makes a good message authentication code. The security goal for a message authentication code is unforgeability: an adversary wins if, after querying an oracle to learn the authenticators on for $q$ messages of their choice, they can forge an authenticator on a message not previously sent to the oracle.

def forger(mac):
    y0 = mac('hello world')
    y1 = mac('The Magic Words are Lightning Sloth Race')
    ...
    return (authenticator, 'another message')

The MAC is secure if the forger has negligible probability of winning, which we formally define to be the MAC-advantage of a random algorithm $F$ at forging authenticators: $$\operatorname{Adv}^{\operatorname{MAC}}_f(F) = \Pr[(a, m) = F(f_k), f_k(m) = a],$$ for any random algorithm $F$ that returns a message it didn't send to the oracle. As above, the forger could submit $2^{64}$ queries to the oracle and probably find a collision $x_0 \ne x_1$; then query the oracle to find the authenticator for $x_0 \mathbin\Vert y$, and forge it as the authenticator for the message $x_1 \mathbin\Vert y$. Is this the only way? We could study strategies for forging HMAC-MD5 directly, but there's a simpler way to understand the MAC security of HMAC-MD5 if we accept the PRF security of HMAC-MD5, using the formalism above.

Suppose we had a successful forger subroutine which and succeeds with probability $p$. Then we can define a distinguisher:

def make_distinguisher(forger):
    def distinguisher(f):
        a, m = forger(f)
        return 1 if f(m) == a else 0
    return distinguisher

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}.$$

So, what does it cost to find HMAC-MD5 collisions? Without knowledge of the key, an adversary can find a collision in about $2^{64}$ trials by the birthday paradox. With knowledge of the key, it's a parlor trick, but if you tell the adversary your key, you're violating the security contract of HMAC-MD5. I recommend avoiding HMAC-MD5 for any applications with anywhere near $2^{64}$ messages under a single key! I also recommend not telling the adversary your key.

---

_{^* 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!}

_{^† Of course, exactly the same strategy will distinguish any iterated hash function from a uniform random function, but won't distinguish between two different iterated hash functions! It could just as well be HMAC-HAVAL128 or anything else with a 128-bit state. That's not the concern of the pseudorandom function family's security claim, which is only about distinguishing the family in question (HMAC-MD5) from a uniform random function of the same domain and codomain.}

_{^‡ It may sound like there is a high cost $c$ to storing all the outputs of the oracle to search among them for a collision, but actually the collision search can be done with negligible additional computation and storage using Pollard's $\rho$, and, if the oracle allows, can be parallelized to run faster (at the same total cost) with the van Oorschot–Wiener algorithm.}

Answer 2

We can find collisions in MD5 much easier than via a generic birthday attack, due to flaws discovered in it's construction. However no practical preimage attack is known, and no practical attack on MD5 HMAC. So to forge an HMAC your only option is to brute force the key.