I am starting the new year by reading about a substantial piece of cryptographic work, a successful attack against a widely used cryptographic method for validating secure Web sites, MD5.
That nothing lasts forever is not surprising, and it was always known that cryptographic methods, however strong, may one day be broken as more powerful computers and more clever algorithms become available. What I find astonishing, however, is that even though this particular vulnerability of MD5 has been known theoretically for years, several of the best known Certification Authorities continued to use this broken method to certify secure Web sites. This is hugely irresponsible, and should a real attack actually occur, I’d not be surprised if many lawsuits followed.
The theory behind this attack is complicated, and the hardware is substantial (200 Playstations used as a supercomputing cluster were required to carry out the attack.) One basic reason why the attack was possible in the first place has to do with the “birthday paradox”: it is much easier to construct a fake certificate that has the same signature as a valid certificate than it is to recover the original cryptographic key used to sign the valid certificate.
This has to do with the probability that two persons at a party have the same birthday. For a greater than 50% chance that another person at a party has your birthday, the party has to be huge, with more than 252 guests. However, the probability that at a given party, you find at least two people who share the same birthday (but not necessarily yours) is greater than 50% even for a fairly small party of just over 22 guests.
This apparent paradox is not hard to understand. When you meet another person at a party, the probability that he has the same birthday as you is 1/365 (I’m ignoring leap years here.) The probability that he does NOT have the same birthday as you, then, is 364/365. The probability that two individuals both do NOT have the same birthday as you is the square of this number, (364/365)2. The probability that none of three separate invididuals has the same birthday as you is the cube, (364/365)3. And so on, but you need to go all the way to 253 before this results drops below 0.5, i.e., that the probability that at least one of the people you meet DOES have the same birthday as you becomes greater than 50%.
However, when we relax the condition and no longer require a guest to have the same birthday as you, only that there’s a pair of guests who happen to share their birthday, we need to think in terms of pairs. When there are n guests, they can form n(n – 1)/2 pairs. For 23 guests, the number of pairs they can form is already 253, and therefore, the probability that at least one of these pairs has a shared birthday becomes greater than 50%.
On the cryptographic front, what this basically means is that even as breaking a cryptographic key requires 2k operations, a much smaller number, only 2k/2 is needed to create a rogue cryptographic signature, for instance. It was this fact, combined with other weaknesses of the MD5 algorithm, that allowed these researchers to create a rogue Certification Authority certificate, with which they can go on and create rogue secure certificates for any Web site.