9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It also depends on the input. An example is hashing passwords, to break one can use a list or frequently used passwords sorted by usage, see SecLists. $\endgroup$ – zaph May 21 '18 at 6:17
  • $\begingroup$ My apologies for the completely wrong first draft of my answer, which was inexplicably upvoted, and which you accepted. I corrected the mistake and attempted to salvage the lesson contained therein. I hope the first draft didn't lead you too far astray before I realized how foolish it was! $\endgroup$ – Squeamish Ossifrage May 24 '18 at 4:55
10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You may want to mention the trivial HMAC "collision" that comes from $k=\operatorname{MD5}(\text{"a very long string, that is longer than one MD5 block, at least I hope that."})$ and $k'=\text{"a very long string, that is longer than one MD5 block, at least I hope that."}$ which should result in $\operatorname{HMAC-MD5}_k(m)=\operatorname{HMAC-MD5}_{k'}(m)$. $\endgroup$ – SEJPM May 21 '18 at 14:30
  • $\begingroup$ @SEJPM Done, by reference to crypto.stackexchange.com/a/67341. $\endgroup$ – Squeamish Ossifrage Feb 27 at 16:59
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not so! Find a collision $x_0 \ne x_1$ in HMAC-MD5 under an unknown key with ${\sim}2^{64}$ queries to an oracle, find the tag for $x_0 \mathbin\Vert y$, and you can forge the tag for $x_1 \mathbin\Vert y$ without asking the oracle. $\endgroup$ – Squeamish Ossifrage May 24 '18 at 0:58
  • $\begingroup$ This is entirely generic attack. Not a weakness in HMAC md5 beyond the length. Further this requires 2^64 Oracle queries. Which seems rather far fetched . I'm not saying I recommend MD5 for any purpose. But my statements above stand. $\endgroup$ – Meir Maor May 24 '18 at 3:12
  • $\begingroup$ The expected cost of brute force on a 512-bit key $k$ for forgery is $2^{511}$ evaluations of HMAC-MD5. Even if there were an unimaginably large set of $2^{128}$ different keys in a multi-target attack, the expected cost is $2^{383}$ evaluations of HMAC-MD5. The expected cost of a birthday attack on HMAC-MD5 is $2^{64}$ queries. Both are generic for HMAC over an iterated hash. Depending on whether the oracle can be queried in parallel or not, the birthday attack may be feasible, but there are no conditions under which the brute force key attack is within the realm of human feasibility. $\endgroup$ – Squeamish Ossifrage May 24 '18 at 3:20
  • $\begingroup$ Finding the key by brute force over 512 bit space is obviously impossible. However more often than not we will have a better option, such as brute forcing the password which generated the key with or without proper KDF. $\endgroup$ – Meir Maor May 24 '18 at 4:14
  • $\begingroup$ You're moving the goalposts. The question was about finding collisions in HMAC-MD5, not about reversing MD5 password hashes. To forge an HMAC-MD5 tag costs only an expected ${\sim}2^{64}$ queries, which is sometimes feasible; to recover an HMAC-MD5 key costs an expected $2^{511}$ evaluations of HMAC-MD5, which is never feasible. (There may be other parts of your system that make it breakable without forging HMAC-MD5 tags, but that's not what this question was about.) It is wrong that ‘to forge an HMAC your only option is to brute force the key’. $\endgroup$ – Squeamish Ossifrage May 24 '18 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.