Flame Malware Tapped World Class Crypto

Whoever built the malware known as Flame, Flamer, and Skywiper imbued it with serious stealth capabilities. Just how serious has been revealed over the past few days, as mathematicians have found a previously unknown type of "collision attack" built into the malware.

"[We] have confirmed that Flame uses a yet unknown MD5 chosen-prefix collision attack," noted Marc Stevens and B.M.M. de Weger, in comments that were republished on a cryptography mailing list.

"The collision attack itself is very interesting from a scientific viewpoint and there are already some practical implications," said the pair, who in 2008 helped devise the first-ever collision attack against the MD5 hash function, allowing for the creation of rogue or spoofed digital certificates.

A collision attack on a cryptographic hash involves finding two different inputs that produce the same hash value. According to Microsoft, Flame's creators successfully performed a collision attack against the Microsoft Terminal Services encryption algorithm. After doing so, they were able to give Flame the ability to spoof the Microsoft signing service and install entire copies of the malicious application automatically, using the updating functionality built into all versions of Windows.

[ Some lawmakers accuse the Obama administration of failing to manage its cyber-warfare secrets. See Was U.S. Government's Stuxnet Brag A Mistake? ]

According to Stevens, a crypto-analyst at the Centrum Wiskunde and Informatica (CWI) in Amsterdam, Flame uses a type of attack that's never been seen before. "Flame uses a completely new variant of a 'chosen prefix collision attack' to impersonate a legitimate security update from Microsoft. The design of this new variant required world-class cryptanalysis," he said, in a published analysis.

What do those findings suggest? "I can't think of another example (outside espionage/war) of unpublished cryptanalysis being used in a fielded exploit. ... I think this further bolsters the conclusion that this is a large state actor," tweeted University of Pennsylvania cryptography researcher Matt Blaze. "But I'd expect [intelligence] agencies to be very reluctant to risk exposing a new cryptanalytic technique by embedding it in a piece of malware."

When Flame first appeared, some security experts dismissed it as the equivalent of malicious bloatware, for seemingly including vast quantities of known attacks, as reflected by its massive size--20 MB with all modules installed. But criticism that Flame is "nothing special" appears to be abating. "For some reason, I don't hear anyone claiming that Flame is lame any more," tweeted Mikko Hypponen, chief research officer at F-Secure.

Indeed, ongoing Flame teardowns keep revealing new levels of complexity. "Flamer is not the typical infostealer one would see in a targeted attack--often referred to as advanced persistent threat (APTs)--or one would see in financially motivated threats like banking Trojans," according to a blog post from Symantec. "The sheer breadth of functionality and size sets it apart. Even describing it as an industrial vacuum cleaner does not do it justice."

The latest Flame revelation further suggests that the malware rules of the game are changing. Before, virus writers--whether using Zeus financial malware or Stuxnet--used zero-day vulnerabilities to try and sneak their malicious code onto target devices.

But when it comes to zero days and Flame, the malware didn't need any. "When we first discovered Flame, we started looking in its code for at least one exploit that used a zero-day vulnerability to spread Flame and infect other machines inside the network. Given its sophistication and the fact that it infected fully patched Windows 7 machines, there should have been one," said Alexander Gostev, who heads the global research and analysis team at Kaspersky Lab, in a blog post.

"What we've found now is better than any zero-day exploit. It actually looks more like a 'god mode' cheat code--valid code signed by a keychain originating from Microsoft," he said, referring to the hidden cheat feature built into many videogames which grants players invulnerability.

Once news of Flame surfaced, Microsoft moved rapidly to deliver a Windows patch. Its patching speed is just one measure of how an attacker possessing a Windows Update "god mode" could wreak havoc with the Windows operating system, or any data stored on a targeted PC.

Black Hat USA Las Vegas, the premiere conference on information security, features four days of deep technical training followed by two days of presentations from speakers discussing their latest research around a broad range of security topics. At Caesars Palace in Las Vegas, July 21-26. Register today.