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][5].
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(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.
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.
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.<sup>*</sup>
**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.<sup>†</sup> 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][1] on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5. (There are [other distinguishers][2] 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}$.<sup>‡</sup>
**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) = |\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}.$$
**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.
---
<sub><sup>*</sup> 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!</sub>
<sub><sup>†</sup> 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.</sub>
<sub><sup>‡</sup> 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$][3], and, if the oracle allows, can be parallelized to run _faster_ (at the same total cost) with the [van Oorschot–Wiener algorithm][4].</sub>
[1]: https://link.springer.com/chapter/10.1007/3-540-44750-4_1 "Bart Preneel and Paul C. van Oorschot, ‘MDx-MAC and Building Fast MACs from Hash Functions’, in Don Coppersmith, ed., Proceedings of Advances in Cryptology, CRYPTO 1995, Springer LNCS 963, pp. 1–14."
[2]: https://www.iacr.org/archive/eurocrypt2009/54790122/54790122.pdf "Xiaoyun Wang, Hongbo Yu, Wei Wang, Haina Zhang, and Tao Zhan, ‘Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC’, in Antoine Joux, ed., Proceedings of EUROCRYPT 2009, Springer LNCS 5479, pp. 121–133."
[3]: https://doi.org/10.1007%2Fbf01933667 "J.M. Pollard, ‘A monte carlo method for factorization’, BIT Numerical Mathematics 15(3), September 1975, pp. 331–334."
[4]: http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf "Paul C. van Oorschot and Michael J. Wiener, ‘Parallel Collision Search with Cryptanalytic Applications’, full paper for preliminary results published in ACM CCS and CRYPTO'96, 1996-09-23."
[5]: https://crypto.stackexchange.com/a/25591/49826 "François Grieu, Answer to ‘Is HMAC-MD5 still secure for commitment or other common uses?’, crypto.stackexchange.com, 2015-05-12."