Skip to main content
MSRC

Flame malware collision attack explained

Since our last MSRC blog post, we’ve received questions on the nature of the cryptographic attack we saw in the complex, targeted malware known as Flame. This blog summarizes what our research revealed and why we made the decision to release Security Advisory 2718704 on Sunday night PDT. In short, 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. This certificate and all certificates from the involved certificate authorities were invalidated in Security Advisory 2718704. We continue to encourage all customers who are not installing updates automatically to do so immediately.

Mysterious Missing Extensions

When we first examined the Flame malware, we saw a file that had a valid digital signature that chained up to a Microsoft Root authority. As we reviewed this certificate, we noticed several irregularities. First, it had no X.509 extension fields, which was not consistent with the certificates we issued from the Terminal Server licensing infrastructure. We expected to find a Certificate Revocation List (CRL) Distribution Point (CDP) extension, an Authority Information Access (AIA) extension, and a “Microsoft Hydra” critical extension. All of these were absent.

When we examined the certificate with the Windows utility certutil.exe we saw a different story emerge.

> certutil.exe  -dump MS.cer

X509 Certificate:
Version: 3
Serial Number: 1b7e
Signature Algorithm:
    Algorithm ObjectId: 1.3.14.3.2.3 md5RSA
    Algorithm Parameters:
    05 00
Issuer:
    CN=Microsoft LSRA PA
    DC=partners
    DC=extranet
    DC=microsoft
    DC=com

 NotBefore: 2/19/2010 2:48 PM
 NotAfter: 2/19/2012 2:48 PM

Subject:
    CN=MS

Public Key Algorithm:
    Algorithm ObjectId: 1.2.840.113549.1.1.1 RSA (RSA_SIGN)
    Algorithm Parameters:
    05 00
Public Key Length: 2048 bits
Public Key: UnusedBits = 0
    0000  30 82 01 0a 02 82 01 01  00 a6 89 43 6f c6 ca 9d
    0010  42 ad bd 28 d5 46 49 e0  55 f2 cc 38 e0 3d c0 7c
    0020  ba 1d ca bb 92 c4 be 4c  5f 1a f9 d6 42 4b 34 0b
    0030  2f 8a ac cb 97 31 ef 76  2f c3 85 af 95 93 47 46
    0040  f6 ff 7c ca df c8 f9 d0  6a ec df 0e 91 55 23 ab
    0050  64 06 90 d3 37 83 a8 0e  3e 5e 7f 77 35 66 74 20
    0060  87 42 1f 25 17 8a d5 28  05 38 05 c8 48 6d 63 76
    0070  3e fd 5a 11 67 07 09 6d  98 a3 08 4a f1 11 7f 80
    0080  a7 4e 37 d4 f0 0e 34 7a  d5 ba 83 ad 60 1e 57 44
    0090  65 50 72 cd af 1e d0 1e  30 c2 eb 6a 51 e2 aa 54
    00a0  85 57 fa 9c b1 59 e8 24  5e d4 38 d3 56 81 68 d5
    00b0  05 8b 48 25 92 a2 11 1b  e8 51 54 d9 d9 04 60 ee
    00c0  1c fb 6a ec f0 6e 38 bb  ad da 35 87 63 74 86 ef
    00d0  1f cd 80 92 a2 98 3a 97  9a bd 35 d1 7d 2e 3a 47
    00e0  04 48 17 74 db a3 67 d9  82 78 e0 77 2c cc ac 39
    00f0  61 a6 d8 9d aa fc de 6f  60 4c 7c 73 07 31 93 2f
    0100  67 28 4a 7e d1 ae 4c 42  dd 02 03 01 00 01
<span style="color: #ff0000;">Issuer Unique Id: </span>
<span style="color: #ff0000;"> 0000 6a 4c e0 1f f5 91 69 b2 74 36 f0 7f 7b 4b 7b c6 jL....i.t6..{K{. <br> 0010 be eb 3f 9f 98 3d a3 84 87 54 7e 72 87 71 25 4b ..?..=...T~r.q%K<br> 0020 68 35 ae 65 bd 6c 8f dc 8d ac c4 e8 98 92 de dc h5.e.l.......... <br> 0030 53 62 f5 72 6a 25 27 a3 12 46 eb 7f 6d 58 cd 30 Sb.rj%'..F..mX.0<br> 0040 83 d7 7a 85 b8 48 e6 0e 01 11 68 65 7d 53 38 0b ..z..H....he}S8.<br> 0050 40 f4 3b 68 43 59 c1 3c 05 c3 40 26 9d 51 97 e2 @.;hCY....@..Q..<br> 0060 eb 2e b8 c2 19 6e 4e 94 46 3b d8 d4 fd 0d 00 d1 .....nN.F;......<br> 0070 68 fa df f3 fa 18 8a 7c 65 9b da 23 11 9f 16 a6 h......|e..#....<br> 0080 8b 23 24 88 87 22 69 19 c2 11 ea 9d 36 81 ad fb .#$.."i.....6...<br> 0090 e8 8b d2 d0 eb 06 f2 1a 86 8d c6 84 f3 88 c5 e0 ................<br> 00a0 d9 64 c6 48 95 d4 be d3 54 48 91 e6 6c e9 1e 33 .d.H....TH..l..3<br> 00b0 97 15 42 ee b4 6d 1f 15 0b 27 dd 08 bb 81 de b6 ..B..m...'......<br> 00c0 96 16 39 d9 26 44 6a 5f d1 6b 3f 12 71 dc f0 99 ..9.&Dj_.k?.q...<br> 00d0 62 d2 43 14 58 f8 6e f8 22 35 d2 90 f7 fd 93 6a b.C.X.n."5.....j<br> 00e0 c4 49 b8 cb 0c e9 65 a8 f7 22 b5 f2 05 19 20 ef .I....e..".... .<br> 00f0 25 63 c7 b3 97 4a 82 3e b2 e3 ee b4 5e cb 1d b3 %c...J.>....^...<br> 0100 59 8f 8d f4 79 01 b1 b6 68 89 14 b4 8f 9d 60 d7 Y...y...h.....`.<br> 0110 71 a5 3d 95 02 03 01 00 01 <span style="background-color: #ffff00;">a3 82</span> 02 5a 30 82 02 q.=.........Z0..<br> 0120 56 30 1d 06 03 55 1d 0e 04 16 04 14 9a 9a 5d 77 V0...U........]w<br> 0130 bd 84 66 a4 f1 de 18 10 1b 6e 67 a5 97 c1 14 87 ..f......ng.....<br> 0140 30 1f 06 03 55 1d 23 04 18 30 16 80 14 75 e8 03 0...U.#..0...u..<br> 0150 58 5d fb 65 e4 d9 a6 ac 17 b6 03 7e 47 ad 2e 81 X].e.......~G...<br> 0160 af 30 81 c2 06 03 55 1d 1f 04 81 ba 30 81 b7 30 .0....U.....0..0<br> 0170 81 b4 a0 81 b1 a0 81 ae 86 56 68 74 74 70 3a 2f .........Vhttp:/<br> 0180 2f 74 6b 78 70 61 73 72 76 33 36 2e 70 61 72 74 /tkxpasrv36.part<br> 0190 6e 65 72 73 2e 65 78 74 72 61 6e 65 74 2e 6d 69 ners.extranet.mi<br> 01a0 63 72 6f 73 6f 66 74 2e 63 6f 6d 2f 43 65 72 74 crosoft.com/Cert<br> 01b0 45 6e 72 6f 6c 6c 2f 4d 69 63 72 6f 73 6f 66 74 Enroll/Microsoft<br> 01c0 25 32 30 4c 53 52 41 25 32 30 50 41 2e 63 72 6c %20LSRA%20PA.crl<br> 01d0 86 54 66 69 6c 65 3a 2f 2f 5c 5c 74 6b 78 70 61 .Tfile://\\tkxpa<br> 01e0 73 72 76 33 36 2e 70 61 72 74 6e 65 72 73 2e 65 srv36.partners.e<br> 01f0 78 74 72 61 6e 65 74 2e 6d 69 63 72 6f 73 6f 66 xtranet.microsof<br> 0200 74 2e 63 6f 6d 5c 43 65 72 74 45 6e 72 6f 6c 6c t.com\CertEnroll<br> 0210 5c 4d 69 63 72 6f 73 6f 66 74 20 4c 53 52 41 20 \Microsoft LSRA <br> 0220 50 41 2e 63 72 6c 30 82 01 31 06 08 2b 06 01 05 PA.crl0..1..+...<br> 0230 05 07 01 01 04 82 01 23 30 82 01 1f 30 81 8e 06 .......#0...0...<br> 0240 08 2b 06 01 05 05 07 30 02 86 81 81 68 74 74 70 .+.....0....http<br> 0250 3a 2f 2f 74 6b 78 70 61 73 72 76 33 36 2e 70 61 ://tkxpasrv36.pa<br> 0260 72 74 6e 65 72 73 2e 65 78 74 72 61 6e 65 74 2e rtners.extranet.<br> 0270 6d 69 63 72 6f 73 6f 66 74 2e 63 6f 6d 2f 43 65 microsoft.com/Ce<br> 0280 72 74 45 6e 72 6f 6c 6c 2f 74 6b 78 70 61 73 72 rtEnroll/tkxpasr<br> 0290 76 33 36 2e 70 61 72 74 6e 65 72 73 2e 65 78 74 v36.partners.ext<br> 02a0 72 61 6e 65 74 2e 6d 69 63 72 6f 73 6f 66 74 2e ranet.microsoft.<br> 02b0 63 6f 6d 5f 4d 69 63 72 6f 73 6f 66 74 25 32 30 com_Microsoft%20<br> 02c0 4c 53 52 41 25 32 30 50 41 2e 63 72 74 30 81 8b LSRA%20PA.crt0..<br> 02d0 06 08 2b 06 01 05 05 07 30 02 86 7f 66 69 6c 65 ..+.....0...file<br> 02e0 3a 2f 2f 5c 5c 74 6b 78 70 61 73 72 76 33 36 2e ://\\tkxpasrv36.<br> 02f0 70 61 72 74 6e 65 72 73 2e 65 78 74 72 61 6e 65 partners.extrane<br> 0300 74 2e 6d 69 63 72 6f 73 6f 66 74 2e 63 6f 6d 5c t.microsoft.com\<br> 0310 43 65 72 74 45 6e 72 6f 6c 6c 5c 74 6b 78 70 61 CertEnroll\tkxpa<br> 0320 73 72 76 33 36 2e 70 61 72 74 6e 65 72 73 2e 65 srv36.partners.e<br> 0330 78 74 72 61 6e 65 74 2e 6d 69 63 72 6f 73 6f 66 xtranet.microsof<br> 0340 74 2e 63 6f 6d 5f 4d 69 63 72 6f 73 6f 66 74 20 t.com_Microsoft <br> 0350 4c 53 52 41 20 50 41 2e 63 72 74 30 1a 06 08 2b LSRA PA.crt0...+<br> 0360 06 01 04 01 82 37 12 01 01 ff 04 0b 16 09 54 4c .....7........TL<br> 0370 53 7e 42 41 53 49 43 S~BASIC<br></span>
Certificate Extensions: 0
Signature Algorithm:
    Algorithm ObjectId: 1.2.840.113549.1.1.4 md5RSA
    Algorithm Parameters:
    05 00
Signature: UnusedBits=0
    0000  96 b9 a2 43 a1 dd 17 48  b9 d6 ec a7 b7 71 a0 01
    0010  63 0f f4 bc e7 c3 03 d3  c2 48 72 7f 85 90 b3 70
    0020  17 d1 50 20 f7 8c ce aa  d1 fe 68 fa 64 b3 8d 00
    0030  b5 38 4a c9 0d 96 1f 6b  42 1f a9 44 05 c5 12 b1
    0040  24 26 fd 19 bb 74 6f bf  16 ef 35 5c 4c d1 dd 30
    0050  ac 64 3c e7 4f 10 14 49  d7 0e 20 c8 ac 36 af 01
    0060  ca 80 ff 04 fb 9d 79 56  4b 8a 7b 11 4e d8 e2 97
    0070  7e 1d 87 cd e5 e1 b1 3e  e6 5f d0 9c 62 6d f6 8c
    0080  dc ca e3 4a f2 e5 5c 29  bb 49 66 68 17 02 75 70
    0090  71 7c f1 78 64 d6 ed db  85 f3 67 ee fb e8 57 50
    00a0  35 94 7b 71 4d f7 b5 12  e5 bb e8 2b 40 de ec 5f
    00b0  29 af bb 7e c9 0b 97 b2  d2 46 dc 77 ef f4 f5 3f
    00c0  07 48 ab 25 c3 8a f3 5d  e1 23 8b c9 49 7d c0 8b
    00d0  c7 52 ca 5c 7f 29 4b 9b  fd 5d fe 71 a1 34 50 00
    00e0  10 a5 86 04 94 e8 07 b7  4b 58 05 4c 67 ca 76 ca
    00f0  5a cc cf 27 d5 a4 04 a8  31 71 83 72 73 ab 4a 00
Non-root Certificate
Key Id Hash(rfc-sha1): d6 11 4d 36 37 9e 6e e3 9e 9f 2f 61 88 98 f2 8d 56 38 69 c9
Key Id Hash(sha1): 38 ea d5 44 de a9 3f 76 78 43 6e 95 f0 2d 58 82 42 f6 55 dd
Cert Hash(md5): ea 99 4e 63 fe 99 06 60 02 c9 9b 09 e3 50 06 2e
Cert Hash(sha1): 1d 19 0f ac f0 6e 13 3e 87 54 e5 64 c7 6c 17 da 8f 56 6f bb
CertUtil: -dump command completed successfully.

This certificate had an unusual field—Issuer Unique Identifier. This field is obsolete and not used by Microsoft software or infrastructure. When we examined this field in detail, we realized that it did not contain random data, but rather it had structure. It contained a correctly encoded X.509V3 extension field starting at byte offset 0x119 into the Issuer Unique Identifier field. Here are some of the “missing” extensions we extracted from it:

Offset Field Data
0x161 CDP (CRL Distribution Point) http://tkxpasrv36.partners.extranet.microsoft.com/CertEnroll/Microsoft%20LSRA%20PA.crl
0x226 Authority Information Access http://tkxpasrv36.partners.extranet.microsoft.com/CertEnroll/tkxpasrv36.partners.extranet.microsoft.com_Microsoft%20LSRA%20PA.crt
0x35b Microsoft Hydra extension [1] Object Identifier 1.3.6.1.4.1.311.18 for value “TLS~BASIC” and is marked critical

The “Critical” Link

The Microsoft Hydra extension is marked as “critical” and this is crucial to why the attacker needed to perform a collision attack. In X.509 parlance, if an extension is essential to the proper validation of a certificate chain, it must be marked critical. The behavior of a crypto library upon encountering an extension marked critical that it does not understand is to fail validation. The Crypto API in Window Vista and later versions of Windows behave this way and the certificates fail validation on those platforms. Hence, if the attacker wanted a certificate that worked on all versions of Windows they needed to remove this field.

Circumstances that Collided

To remove the critical extension, the attacker took advantage of a number of circumstances to perform a collision attack:

  • An attacker took advantage of the Terminal Services licensing system‘s enrollment process for certificates that chained up to the Microsoft Root Authority which did not require internal access to Microsoft PKI.
  • The signature algorithm on this certificate was md5RSA.
  • The issuing certificate authority used known validity periods and certificate serial numbers that could be predicted with high probability.

An essential part of performing a collision attack is that the attacker needs to be able to predict completely the certificate content that will be signed by the CA. Because of the predictable serial numbers, the attacker can perform a set of certificate enrollments that reveal the likely serial number when they perform their collision attack. This is also called a “chosen prefix collision attack” [2]. The attacker can then apply the collision algorithm documented by Sotirov et. al. [3] to create a forged certificate that removes the critical Microsoft Hydra extension and still matches the MD5 hash of the legitimate certificate signed by the CA.

Quick Response to Extinguish Flame and Copycats

Without this collision attack, it would have been possible to sign code that would validate on systems pre-dating Windows Vista, but that signed code would fail validation on Windows Vista and above. After this attack, the attacker had a certificate that could be used to sign code that chained up to the Microsoft Root Authority and worked on all versions of Windows. Given the risk for copycat attacks on systems pre-dating Windows Vista, without the complexity of a collision attack, we took action to release an out-of-band update.

Hardening of the Terminal Server Licensing Certificate Infrastructure

We also made a number of changes to the Terminal Server licensing infrastructure to minimize risk in the future:

  • Rather than just invalidate certificates known to be used by the Flame malware, we invalidated the entire certificate authority hierarchy associated with Terminal Server licensing, both present and past. This was a broad action and was the fastest way to protect the largest number of customers. These certificates were invalidated in the update for Security Advisory 2718704. Existing Terminal Server Client Access Licenses (CALs) are not impacted and you can read more on the Terminal Server blog post.
  • A new certificate chain was introduced that no longer chains up to the Microsoft Root Authority. It has a separate standalone root not trusted by Windows clients to minimize future risk. The certificates use SHA1 in the signatures.
  • We have also discontinued issuing code-signing certificates for this new hierarchy. Also, its certificates are constrained with a new Enhanced Key Usage that is not used for code signing. This effectively constrains the capabilities of the certificates to just Terminal Server licensing.

Microsoft takes the security of its customers seriously; therefore we took the swiftest action that would protect the largest number of customers first. We will continue to take the necessary actions to help protect our customers.

Acknowledgements

Thanks to John Lambert, Magnus Nystrom, David Molnar, and special thanks to Tolga Acar for their contributions to this investigation.

- Jonathan Ness, MSRC Engineering

References

[1] Microsoft, “Object IDs associated with Microsoft cryptography”, http://support.microsoft.com/kb/287547/pt-b, March 1, 2007.

[2] M. Stevens and A. Lenstra and B. de Weger. “Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities”, http://www.win.tue.nl/hashclash/EC07v2.0.pdf, http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/, June 16, 2009.

[3] A.Sotirov, M.Stevens, J.Applebaum, A.Lenstra, D.Molnar, D.A. Osvik, B. de Weger, “MD5 considered harmful today”, http://www.win.tue.nl/hashclash/rogue-ca/, Dec.30, 2008.


Related Posts

How satisfied are you with the MSRC Blog?

Rating

Feedback * (required)

Your detailed feedback helps us improve your experience. Please enter between 10 and 2,000 characters.

Thank you for your feedback!

We'll review your input and work on improving the site.