“If they did it the same way we did in 2008, that would be the cost,” he explained. “It’s also possible they had a faster and more efficient way to compute these collisions and this is something you would get by doing cryptographic research.”
The Flame malware, which was recently discovered infecting computers in Iran and other Middle Eastern countries, was able to spread from one computer to another inside targeted networks by setting up a fake Windows Update server. For the attack to work, the fake update had to be digitally signed by a source that ultimately led back to Microsoft’s root authority key. A licensing mechanism in the Microsoft Terminal Server allowed the attackers to generate certificates that worked against machines running Windows XP, but they didn’t work on newer versions of the operating system. To get around this limitation, the Flame attackers used collision attacks on the MD5 algorithm to construct certificates that would be trusted by operating systems that succeeded XP, too. Collision attacks rely on weaknesses that allow two different sources of plaintext to generate identical cryptographic hashes.
Sotirov said the collision attacks observed in Flame could have been prevented if Microsoft had stopped employing MD5 sooner.
“We believed at the time that by exposing the vulnerability and by bringing so much public attention to it, we were hoping that this problem would be totally eradicated and everyone else who was running a certificate authority would switch away from MD5 and start using SHA1,” he said. “It turned out that Microsoft still had the certificate authority that they used for Terminal Services licensing which still used MD5. It was targeted by Flame.” Microsoft was using MD5 for Terminal Server licensing as recently as last year, he added.
Microsoft recently revamped its key management process to prevent similar attacks from working in the future. But it has yet to say why it employed such a vulnerable system in the first place, or why it continued to rely on MD5 for so long.
Slides from Sotirov’s presentation are here.