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.
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.
If you evaluate the oracle at $2^{64}$ different inputs, you would probably find a collision. But that is true for HMAC-MD5 under a uniform random key and true for a uniform random function, so it doesn't help to distinguish them, and thus doesn't break HMAC-MD5. 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$ such that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = q/2^{512}$, where $q$ is the number of times $D$ queries the oracle. (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.)
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. The forger could submit $2^{64}$ queries to the oracle and probably find a collision, but they wouldn't succeed because that doesn't help to find an authenticator on a message they didn't send to the oracle. 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, you can find a collision in about $2^{64}$ trials by the birthday paradox, but that doesn't matter for the standard applications of HMAC-MD5. 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. Does a collision break your application? That depends on how your application uses it!