MD5 considered harmful today
hal at finney.org
Tue Dec 30 14:51:06 EST 2008
- 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
- 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
- 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
- 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
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography