Researchers in Switzerland and the Netherlands have successfully generated an apparently valid CA certificate, using a ‘collision’ attack on the MD5 hashing algorithm. (A collision is when you find a plaintext of your own choosing which produces the same hash as the genuine plaintext you’re trying to forge…). The report on the ZDNEt website also mentions Arjen Lenstra of the EPFL (Ecole Polytechnique Fédérale de Lausanne), who led the research.
I was lucky enough to hear Arjen speak at the recent HP Colloquium, hosted by the Information Security Group at Royhal Holloway University of London. He was talking on the theme of ‘factorisation methods for large prime numbers’ – and if I say that he made it both instructive (even to a non-mathematician like me) and entertaining, you’ll get some indication of what an engaging speaker he is.
The researchers laced together a bank of more than 200 games consoles to assemble the requisite computing power, though for the time being they decline to publish the algorithms they used to produce the MD5 collision. There’s a quite detailed description of the experiment here, with background details of how MD5 hashing works, how it can be broken and so on. As you’ll see from the details of the attack, this isn’t something just anyone is going to knock up in their garage over the weekend – but neither does it use anything particularly esoteric.
The bad news, from a user perspective, is that there is not a great deal the average punter can do to mitigate the risk which this attack highlights. They will just have to wait for current MD5-using CAs to upgrade their technology and switch to more collision-resisitant hashing algorithms.