The cryptographic attack that Flame engineers used to hijack Microsoft's Windows Update process was so computationally demanding, it would have required the equivalent of $200,000 worth of computing time from Amazon's EC2 Web service for most people to carry it out.
That estimate was delivered over the weekend at the SummerCon conference by Alex Sotirov, a co-founder and chief scientist of New York-based security firm Trail of Bits. One of seven researchers behind a 2008 "collision" attack that generated an SSL certificate authority trusted by all major operating systems and browsers, Sotirov said the exploit required the equivalent of about $20,000 worth of computing time from EC2. The cost is because the precise window in which a fraudulent certificate could be constructed was just one second. That required him to try minting the certificate four times before he was successful. Rather than use the Amazon service, Sotirov's team used a cluster of 200 PlayStation 3 consoles, which over a weekend delivered an equivalent amount of computing resources.
"Based on my analysis of Flame so far, the timing precision that they needed for Flame was one millisecond," Sotirov told Ars on Monday. "That's one-thousandth of a second, which is quite a bit more difficult to achieve than our work in 2008. Because of this timing issue, I'm speculating that the Flame authors had to try their attack many times, probably many more than the four I needed in 2008."
As Ars reported last week, the people designing Flame achieved mathematical breakthroughs that could only have been accomplished by world-class cryptographers. Specifically, the "chosen-prefix collision attack" that was used to digitally sign malicious Flame components was an entirely new variant of the technique that researchers had never seen before. Sotirov said the $200,000 estimate is likely the maximum cost of the computing power that would have been required when Flame was likely being designed. He held out the possibility that the collision attack may have cost much less if the researchers figured out techniques that were less computing intensive.
"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.
Listing image by Alex Sotirov
reader comments
30