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.