Communications of the ACM

What’s most remarkable about the Flame malware, say cryptologists, is not the suicide command the code generated to remove it from some infected computers, as has been widely reported. What’s most remarkable is that Flame, which infected more than 600 specific targets, seems to be the first public example of malware “in the wild” using a cryptanalytic attack on digital signatures using the MD-5 hash function.

The signatures are commonly used to check data authenticity.

“It is shocking to see that the Flame malware spread itself--ironically enough--as a security patch through Microsoft’s Windows Update,” says Marc Stevens, a scientific staff member in the Cryptology Group of Centrum Wiskunde & Informatica (CWI) in Amsterdam. “And that Microsoft still used MD5-based signatures at least one year after their own advisory disallowing all certification authorities [CAs] in their CA root program to use MD5-based signatures effective January 15, 2009.”

Until now, the only publicly known chosen-prefix collision attack on MD5 was non-malicious, when Stevens and his six co-authors broke the https security in 2008.

“I made HashClash, my chosen-prefix collision attack software, publicly available in June 2009 for educational purposes,” says Stevens, “which means malware engineers could easily have used it for Flame. But instead, using my new forensic tool, I discovered that whoever created Flame was able and willing to construct new algorithms and methods--an entirely new variant that required world-class cryptanalytic abilities.”

“The big news here is that people behind Flame--which is extremely large, extremely complex, and one of the most sophisticated pieces of malware ever developed--did something mathematically and scientifically new to get this piece of software running on Windows machines, and that tells us a lot about what kind of people were involved in creating it,” says Matthew Green, an assistant research professor of computer science at Johns Hopkins University and a crypto specialist. “There are a lot of organizations that have good coders who could probably develop the malware itself.  But very few organizations have the knowledge to develop new collision attacks. So while it doesn’t tell us why they did it, it tells us that it’s very very likely that this was a state-sponsored attack. And not just any state, but one with considerable resources behind it.”

Microsoft has since issued a security advisory about unauthorized digital certificates, on June 3, with specific recommendations for its customers.

Stevens plans to do further research to recreate Flame’s chosen-prefix collision attack and its still-unknown differential path construction algorithm.  

“No one knows at this point what Flame was doing before it went through its suicide routine,” says Green. “Unlike [earlier malware] Stuxnet that attacked centrifuge controllers, Flame contained all sorts of modules for logging keystrokes and spying, so it could have been doing lots of different things depending on whose machines it was infecting.”

According to CWI’s Stevens, “a big implication here is that MD5 collision attacks were still not taken as a serious threat at some places, despite the many urgent warnings.”

He recommends that his forensic tool be used in operating systems for real-time  protection against possible future collision attacks.

Meanwhile, Green isn’t sure what to recommend. “We can try to make our systems more secure but, once you have governments involved in building malware, it’s a whole new world. It’s very difficult to defend yourself against malware that was developed by a country like, say, the United States. I’m not saying it was; we don’t know that. But if the U.S. government wants to build malware that attacks Windows machines, it has a lot of different ways to make that happen.”