MD5 considered harmful today

[Hal Finney]

Re: http://www.win.tue.nl/hashclash/rogue-ca/

Key facts:

 - 6 CAs were found still using MD5 in 2008: RapidSSL, FreeSSL, TC
   TrustCenter AG, RSA Data Security, Thawte, verisign.co.jp. "Out of the
   30,000 certificates we collected, about 9,000 were signed using MD5,
   and 97% of those were issued by RapidSSL." RapidSSL was used for the
   attack.

 - The attack relies on cryptographic advances in the state of the art for
   finding MD5 collisions from inputs with different prefixes. These advances
   are not yet being published but will presumably appear in 2009.

 - The collision was found using Arjen Lenstra's PlayStation Lab and used
   200 PS3s with collectively 30 GB of memory. The attack is in two parts,
   a new preliminary "birthdaying" step which is highly parallelizable and
   required 18 hours on the PS3s, and a second stage which constructs the
   actual collision using 3 MD5 blocks and runs on a single quad core PC,
   taking 3 to 10 hours.

 - The attack depends on guessing precisely the issuing time and serial
   number of the "good" certificate, so that a colliding "rogue"
   certificate can be constructed in advance. The time was managed
   by noting that the cert issuing time was reliably 6 seconds after
   the request was sent. The serial number was managed because RapidSSL
   uses serially incrementing serial numbers. They guessed what serial
   number would be in use 3 days hence, and bought enough dummy certs
   just before the real one that hopefully the guessed serial number would
   be hit.

 - The attacks were mounted on the weekend, when cert issuance rates are
   lower. It took 4 weekends before all the timing and guessing worked right.
   The cert was issued November 3, 2008, and the total cert-purchase cost was
   $657.

 - The rogue cert, which has the basicConstraints CA field set to TRUE, was
   intentionally back-dated to 2004 so even if the private key were stolen,
   it could not be misused.

My take on this is that because the method required advances in
cryptography and sophisticated hardware, it is unlikely that it could
be exploited by attackers before the publication of the method, or
the publication of equivalent improvements by other cryptographers. If
these CAs stop issuing MD5 certs before this time, we will be OK. Once
a CA stops issuing MD5 certs, it cannot be used for the attack. Its old
MD5 certs are safe and there is no danger of future successful attacks
along these lines.  As the paper notes, changing to using random serial
numbers may be an easier short-term fix.

Therefore the highest priority should be for the six bad CAs to change
their procedures, at least start using random serial numbers and move
rapidly to SHA1. As long as this happens before Eurocrypt or whenever
the results end up being published, the danger will have been averted.
This, I think, is the main message that should be communicated from this
important result.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com