MD2: reply to comments


Glad to see a comment from Dan Kaminksy on the last post about the severity of MD2 issues.

Follow-ups:

  • There is no denying the problem with MD2. Discontinuing its use (eg rejecting certificates signed with MD2, as OpenSSL already has and t he upcoming MSFT patch will implement) is the right response.
  • Point argued in the post is  that severity and urgency of the problem is low.  Compared to other X509 problems disclosed by Dan Kaminsky and Moxie Marlinspike — including the null handling, OID confusions and even more deadly remote code execution in NSS– MD2 issue is a distant second. The sky is not (yet) falling.
  • It’s not clear  the MD5 parallel holds: When Wang and her colleagues found actual collisions people were widely using MD5 for new signatures. In fact the forgery of an intermediate CA cert in December 2008 proved some certificate authorities are so clueless that they continued using MD5 for new signatures after 4 years and several improved attacks. (The fact that SSL CAs are bound to be incompetent and clueless as the expected competitive outcome deserves its own blog post.) MD2 has long been retired for new signatures, leaving only past signatures to exploit.
  • Basic birthday attacks are enough to exploit new signatures. Advances in the types of collisions possible– such as controlling the prefix– only improve the odds. But leveraging  past signatures in a hash function that is no longer used requires a second pre-image attack. Nobody has managed to produce even a single one for MD2.
  • As of this writing, best second preimage attacks have time complexity comparable to 2**73 MD2 invocations and storage complexity of 2**73. And that second number makes this attack impractical . Eight billion terabytes– an awful lot of spare disk drives. (As an aside– Daniel Bleichenbacher looked into this and did not see any low-hanging improvements to the storage requirement either.)

Bottom line: yes there is a problem with MD2. It never presented an immediate danger. Cryptographic attacks are fascinating but the more mundane X509 parsing bugs disclosed around the same time– and continuing tradition of CA incompetence– are far more fatal to PKI.

CP

2 thoughts on “MD2: reply to comments

  1. dakami says:

    Ah, but you contradict yourself. Active use of MD5 mattered because our attacks depended on having fresh invocations of the hash function. Second preimages meant that we didn’t *need* fresh invocations — the use in 1996 was enough to put systems at risk in 2009.

    You’re absolutely right that the immediate risk was nil, because our best attacks were completely infeasible. But you know, our best attacks against MD5 were completely infeasible for a very long time too, but we all knew it was a weak construction that would eventually fail catastrophically.

    This is sort of a meta-argument, but being nitpicky about exactly what constitutes a break in a hash function is precisely why MD5 wasn’t successfully decommissioned when Dobbertin broke it in the mid 90’s, or when Wang broke it in 2005. I’m OK with making a systematic crypto change before the huge damage comes. Isn’t that far better than what we saw (and ultimately will see) with MD5?

    In other words, how can you insult the CA’s as clueless for using MD5, when they almost certainly used similar arguments internally as you are using against MD2?

  2. Not quite following the point about contradiction.

    MD5 was in active use in 2004 when birthday collisions were demonstrated. In fact CAs were slow to respond even in the presence of a smoking-gun. That is a problem.

    MD2 past signatures are honored today (including on certificates) and if a second-preimage attack were feasible, that would be a problem. We appear to be in agreement that such an attack does not exist. In fact it is not even close: throwing more distributed cracking efforts will not solve the problem. It takes a cryptographic breakthrough to shave the time/space requirements.

    In other words there is a margin of safety in current MD2 uses– albeit a shrinking one– that we did not have for MD5 since 2004.

    Theoretical results against SHA1 have been known since 2005 that estimate birthday collisions in 2**63 effort. But you will notice there is no crash-program to migrate the world away from SHA1. No one is disputing that it’s is time to pick something better for the future, preferably starting from scratch given MD5/SHA1/SHA256 all share similar design. NIST is spearheading that effort and migration is inevitable, but sky is not falling either.

    Same point applies to MD2. (Consider the leisurely schedule of the MSFT patch.)

    CP

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s