Flame malware wielded rare "collision" crypto attack against Microsoft

Flame malware wielded rare “collision” crypto attack against Microsoft

Such real-world exploits are almost unheard of, underscoring Flame’s ingenuity.

Dan Goodin – Jun 5, 2012 2:31 am | 58

Credit: udono

Attackers behind espionage software that infected Iranian computers targeted hard-to-exploit weaknesses in a cryptographic algorithm, a feat that allowed them to counterfeit a Microsoft digital credential, a member of the company’s security team said.

Details of the “cryptographic collision attack,” which came in a blog post published Monday afternoon, are the latest testament to the skill and sophistication that went into engineering the Flame malware. While theoretical, collision exploits in real-world attacks are virtually unheard of. As a 2008 attack on the MD5 cryptographic algorithm demonstrated, collision attacks require huge amounts of computing power, even when exploiting decades-old hashing functions. To pull it off, researchers had to wield the power of 200 PlayStation 3 gaming consoles.

Cryptographic algorithms are used to transform words, documents, or computer files into ciphertext that can never be converted back to their original form. These hash functions are used to digitally sign e-mails, ensure documents haven’t been tampered with, and verify that software and software updates available online originated with a particular person or group. The integrity of the entire system relies on each unique piece of plaintext almost always generating a unique string of ciphertext. The ability for someone to find a collision, in which two different plaintext sources generate the same ciphertext, completely undermines the system, since it relies on the plaintext remaining secret and unique.

The latest disclosure from Microsoft came about 24 hours after members of its security team revealed that the Flame architects exploited weaknesses in an older cryptographic hash in conjunction with weaknesses in its Terminal Server product. The technique allowed the attackers to create a fraudulent intermediate certificate authority that contained the imprimatur of Microsoft’s own root authority certificate. The bogus certificate was used to trick people into installing various Flame software modules by falsely certifying they were produced by Microsoft. The company didn’t elaborate on the algorithm exploit until it published Monday’s post.

“The Flame malware used a cryptographic collision attack in combination with the terminal server licensing service certificates to sign code as if it came from Microsoft,” Mike Reavey, senior director of Microsoft’s Security Response Center, wrote. “However, code-signing without performing a collision is also possible. This is an avenue for compromise that may be used by additional attackers on customers not originally the focus of the Flame malware.”

The statement that a collision attack was used but wasn’t necessary to sign the Flame malware sent cryptographers scrambling to figure out exactly what it meant. Reavey didn’t elaborate.

One possible theory—advanced by Nate Lawson, a cryptographer and principal of security consultancy Root Labs—is that the weaknesses in Terminal Server allowed the attackers to mint the counterfeit Microsoft certificates while the collision attack gave them the ability to hide their identity.

“They could get a cert signed with one identity, then apply the signature to another cert,” Lawson explained. “Especially if Microsoft didn’t log every cert signing request, this would make it hard to determine exactly which customer was used to compromise them.”

To carry out such a feat, the Flame attackers would first have Microsoft sign some innocuous-looking certificate containing data that was known to create a collision. They would then use that data in the malicious certificate.

“Since the collision caused the hashes of both to be equal, the Microsoft signature can be ‘lifted’ from one cert and applied to the other,” Lawson said.

Whatever the motive, practical collision attacks are extremely rare. Microsoft’s claim that Flame was able to pull one off is one more reason to believe that whoever was behind the malware had unlimited resources and some exceptional talent.

Story updated to add the words “almost always” in the third paragraph.