What cryptographic flaw was exploited by Flame, to get its code signed by Microsoft?

Question

Today, Microsoft released a security advisory warning that the "Flame" malware exploited a weakness in a cryptographic algorithm used by Microsoft Terminal Server Licensing Service, and was thereby able to get some of its code signed so it appeared to have come from Microsoft.

Here's what Microsoft wrote:

We have discovered through our analysis that some components of the malware have been signed by certificates that allow software to appear as if it was produced by Microsoft. We identified that an older cryptography algorithm could be exploited and then be used to sign code as if it originated from Microsoft. Specifically, our Terminal Server Licensing Service, which allowed customers to authorize Remote Desktop services in their enterprise, used that older algorithm and provided certificates with the ability to sign code, thus permitting code to be signed as if it came from Microsoft.

See also this blog post from Microsoft.

So, what was the exploitable cryptographic algorithm that was used by Microsoft Terminal Service Licensing Service? What was the cryptographic weakness that was exploited by Flame? Are there any lessons we can learn from this incident?

Answer 1

Update: Microsoft published a report which confirms the guesses in this posting and gives a great level of details.

Certificate Purpose

There are multiple purposes a certificate may be used for. For example it may be used as a proof of identity of a person or webserver. It may be used for code sining or to sign other certificates.

In this case a certificate that was intended to sign license information was able to sign code.

It might be as simple as Microsoft not checking the purpose-flag of customer certificates they signed:

Specifically, when an enterprise customer requests a Terminal Services activation license, the certificate issued by Microsoft in response to the request allows code signing.

MD5 collision attack

The reference to an old algorithm might indicate a collision attack on the signing process: There was a talk at CCC 2008 called MD5 considered harmful today - Creating a rogue CA Certificate

• Website
• Slides
• Video

In that talk the researches explained how to generate two certificates with the same hash.

The generated a harmless looking certification request and submitted it to a CA. The CA signed it and generated the valid certificate for https-servers.

But this certificate had the same hash as another generated certificate which had the purpose CA-certificate. So the CA signature of the harmless certificate was valid for the dangerous one as well.

The researches exploited a weakness in MD5 to generate collisions. In order for the attack to work, they had to predict the information the CA would write into the certificate.

Lessons learned?

• Microsoft already checks that the root of code signing certificates for Windows Update is a Microsoft CA. So certificates signed by other rouge CAs cannot be used.

• Don't forget legacy code and services

• If there is enough motivation even impractical theoretical weaknesses, will be exploited. (The original title of the talk was "Doing the theoretical possible").

Update

Microsoft has confirmed both issues (one issue alone is sufficient for an exploit):

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. However, code-signing without performing a collision is also possible.

Update 2

Microsoft published the details:

• The vulnerability of not checking the certificate purpose properly only effects old versions of Windows.
• The collision attack was used manipulate the certificate extensions, so that current versions of Windows are fooled as well.

Update 3

The researchers of the original md5 collision attack published that the attackers used a new variant of the known md5 chosen prefix attack, which implies that they have very deep knowledge about cryptography.

Answer 2

Nice question :) Not sure if there's an obvious answer.

I didn't think that it was an alogorithm that was broken as such but a stolen cert.

I guess one lesson is that the CA model is broken but then you probably knew that before. So it looks like a real "Microsoft" certificate was used to sign Flame. SANS have posted the following - https://isc.sans.edu/diary.html?storyid=13366. No one currently appears to know how it was stolen etc or who did it yet but would the US govt (who many originally suspected) really steal a Microsoft cert, who knows???

I love the bit in the link you provided where Microsoft say -

"Additionally, most antivirus products will detect and remove this malware."

I think the Flame incident is further evidence that the AV industry is completely reactionary, very much marketing driven and no longer effective (even Mikko Hyponnen said it was a failure in Wired over the weekend - http://www.wired.com/threatlevel/2012/06/internet-security-fail/ ).

Hyponnen posted a picture of what the stolen certs used in Flame would look like in Windows 7 prior to revoking them - http://t.co/M7phmvAu.

Someone who knows a lot more than me about certs etc (Moxie Marlinspike) did a great post on that topic last year - http://blog.thoughtcrime.org/ssl-and-the-future-of-authenticity. I've been playing a little with Convergence (http://convergence.io) and I'll probably look into it more, though it's essentially for browsing and won't help here unfortunately. The vast majority of users don't know how to check for certs in their browser or understand how it works, let alone looking at driver certs. I guess it's another example in the importance of truly understanding what you (or your users) are running, doing and what is normal traffic. Building a policy allowing known, good traffic and denying anything not explicitly allowed (to the Internet) helps reduce the attack surface and capabilities.

Answer 3

This advice is for those who require the highest security, and not for the casual web user

A lesson we can learn is to reduce the surface area of public trust. I don't know what specific root hierarchy was compromised, but in general the out-of-the-box public PKI trust is too broad in my opinion.

I would suggest removing all non-essential root certificates from your hosts except for those listed here:

Issued to                              Issued by                            Serial number                   Expiration date Intended purposes   Friendly name                        Status
Microsoft Root Authority               Microsoft Root Authority         00c1008b3c3c8811d13ef663ecdf40  12/31/2020  All                     Microsoft Root Authority                R
Thawte Timestamping CA                 Thawte Timestamping CA           00                              12/31/2020  Time Stamping           Thawte Timestamping CA                  R
Microsoft Root Certificate Authority   Microsoft Root Certificate Authority 79ad16a14aa0a5ad4c7358f407132e65 5/9/2021   All                     Microsoft Root Certificate Authority    R

Then petition Microsoft to constrain those trusted roots to the minimum EKU's necessary such as code signing, etc. Even the constrained list of 3 certificates have too much permission.

Casual users who insist on removing root certificates should look through this answer regarding why the CAs were placed there, the methodology, and the security requirements of each root ca.

Answer 4

There are two vulnerabilities here:

• Unrestricted code signing. Microsoft gave users of Terminal Services the ability to get a signing cert that chains up to the Microsoft Root. They inadvertently allowed this cert to be used for signing code. Therefore, users could sign any code they liked and make it look like it was approved by Microsoft. Yikes! Very bad.

  This vulnerability is exploitable on systems before Windows Vista (e.g., on Windows XP). However, due to new hardening measures introduced in Vista, this vulnerability is no longer exploitable for code signing on Windows Vista or later, on its own.

• Collision attacks. One of the certs in the chain uses MD5. MD5 is known to be vulnerable to collision attacks, and it is known how to use these attacks to exploit any certificate authority who uses MD5. This made it possible for the attacker to get any code of their choosing signed, in a way that makes it look like it was approved by Microsoft. (See @Hendrik's answer for more.) This is also very bad.

  This vulnerability enabled them to bypass the Vista-related hardening. Thus, the combination of these two vulnerabilities allowed the attackers to attack all Windows operating systems successfully: they were able to get their malicious code signed so it looked like it came from Windows.

These are two separate (but related) vulnerabilities. Flame uses the two in combination, enabling Flame to successfully attack all Windows platforms. These vulnerabilities have been present for many years. Someone could have just as easily exploited the former vulnerability, though it would have only be successful against pre-Vista platforms.

Resources for further reading:

• An excellent blog post that explains all of this in more detail: http://rmhrisk.wpengine.com/?p=52

• Microsoft wrote:

  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. However, code-signing without performing a collision is also possible.

• Microsoft also wrote:

  by default the attacker’s certificate would not work on Windows Vista or more recent versions of Windows. They had to perform a collision attack to forge a certificate that would be valid for code signing on Windows Vista or more recent versions of Windows. On systems that pre-date Windows Vista, an attack is possible without an MD5 hash collision.

• The collision attack apparently involved development of a novel collision attack on MD5, different from the ones that were previously known in the open research literature. See Ars Technica's reporting (Crypto breakthrough shows Flame was designed by world-class scientists) and analysis from Marc Stevens.