Re: [cryptography] Microsoft Sub-CA used in malware signing
On 12-6-2012 10:45, Ben Laurie wrote: On Tue, Jun 12, 2012 at 8:24 AM, Marc Stevensm...@marc-stevens.nl wrote: On 12-6-2012 0:59, Ralf-Philipp Weinmann wrote: On 6/11/12 6:38 PM, Ondrej Mikle wrote: On 06/11/2012 11:06 AM, Ben Laurie wrote: On Mon, Jun 11, 2012 at 1:56 AM, Nico Williamsn...@cryptonector.com wrote: On Sun, Jun 10, 2012 at 3:03 PM, Florian Weimerf...@deneb.enyo.de wrote: * Marsh Ray: Marc Stevens and B.M.M. de Weger (of http://www.win.tue.nl/hashclash/rogue-ca/) have been looking at the collision in the evil CN=MS cert. I'm sure they'll have a full report at some point. Until then, they have said this: [We] have confirmed that flame uses a yet unknown md5 chosen-prefix collision attack. Does this mean they've seen the original certificate in addition to the evil twin? The evil twin has the nasty bits[*] in the issuerUniqueID field, which is weird, and the ID is not one likely to be generated by any CA. Would the original have it?? I don't see why the TS CA would have issued certs with issuerUniqueIDs under any circumstances, which is why it's interesting the the evil twin had any evil bits. Surely the whole point is that the collision is used to switch somethingto issuerUniqueID in order to hide the stuff that would've stopped the cert from working. I haven't looked, but I'm prepared to bet it would not be hard to figure out what the original cert must have looked like. [...] Very interesting. So if this is the case, it's not a chosen-prefix collision attack but a mere collision attack with the right differential to hide the extension. In fact, I had written a paper about almost the same trick - I called it extension hopping - which was submitted to USENIX Security 2008 and rejected - yes, I know, I should've put my money where my mouth was and come up with a suitable differential as well. But in the end I was distracted by different subjects and Marc Stevens et al. wiped the floor with MD5 using their chosen-prefix attack. There is some public documentation on this from the Echternach Symmetric Cryptography Seminar in January 2008 where I gave an outline of the idea in a brief talk: http://wiki.uni.lu/esc/docs/rpw_friday_x509ehopping.pdf Thank you, dear flame authors, for providing an implementation for my idea! Now, how should I cite you? The more interesting question here however is: Why did they choose this approach? I posit it might be significantly cheaper computationally than a chosen-prefix attack since you don't need the expensive birthdaying step at the beginning. To avoid misinformation to start spreading: Flame used a chosen-prefix collision attack. See also: http://www.cwi.nl/news/2012/cwi-cryptanalist-discovers-new-cryptographic-attack-variant-in-flame-spy-malware Flame used a birthday search followed by 4 near-collision blocks to obtain a collision. These collision bits were hidden inside the RSA modulus in the original cert and inside the issuerUniqueID field in the evil cert. Using my forensic tool I was able to retrieve the near-collision blocks of the original cert (that is not available and might never be) and the chaining value before the first near-collision block. Would you share your reconstruction of the original cert? Certainly, the reconstruction of the near-collision blocks and the underlying attack is the topic of a future paper. In the mean time, I'll probably open a webpage soon where I can put the reconstruction and updates about my findings online. Also, recently Alex Sotirov has released some other very interesting details about how Flame used the collision attack: http://www.trailofbits.com/resources/flame-md5.pdf They were limited to a millisecond time-window to request the original cert for their attack to succeed. That means they probably needed a lot more attempts than the 9 attempts (over 4 weekends) we needed. There is also a slide on Flame's MD5 attack complexity, but this seems to be based on the assumption that Flame used our attack, which is clearly not the case. I do not support his statement that Flame's MD5 attack has similar complexity to ours: we simply do not know yet. Also his Remaining Question is easily answered with the details I gave earlier today: Flame did not use the open-source software from my HashClash project (http://code.google.com/p/hashclash). Using this information I was able to reconstruct the 4 differential paths. These differential paths clearly show that a new variant chosen-prefix collision attack was used as well as a new differential path construction algorithm that are not in the literature. On a side note, chosen-prefix collisions can be achieved with a birthday search complexity as low as 2^33 MD5 compressions. That is not significantly cheaper than doing an identical-prefix collision attack where you also have to fix significant portions of your near-collision blocks to meaningful values to do a extension hopping attack. Extension hopping is a nice idea, but I
Re: [cryptography] Microsoft Sub-CA used in malware signing
On 06/12/2012 04:09 AM, Marc Stevens wrote: They were limited to a millisecond time-window to request the original cert for their attack to succeed. That means they probably needed a lot more attempts than the 9 attempts (over 4 weekends) we needed. From Sotirov's http://www.trailofbits.com/resources/flame-md5.pdf : Serial number format: o number of milliseconds since boot (4 bytes) o CA index (fixed 2 byte value) o sequential certificate number (4 bytes) So I see three challenges: a) Ensuring the request goes to the correct server. If there are multiple boxes behind a load balancer serving requests this could be an issue. But given the format of the serial number and that the CA index always seems to be '00 00' we can assume this isn't a problem. If there are load-balanced signing servers, their likely working off of a shared consistent database. b) Submitting the CSR at the correct millisecond. It's not uncommon for internet timing jitter to be +- 1 ms or less: PING google.com (173.194.64.100) 56(84) bytes of data. 64 bytes from oa-in-f100.1e100.net (173.194.64.100): icmp_req=1 ttl=43 time=48.6 ms 64 bytes from oa-in-f100.1e100.net (173.194.64.100): icmp_req=2 ttl=43 time=47.5 ms 64 bytes from oa-in-f100.1e100.net (173.194.64.100): icmp_req=3 ttl=43 time=48.0 ms 64 bytes from oa-in-f100.1e100.net (173.194.64.100): icmp_req=4 ttl=43 time=47.8 ms 64 bytes from oa-in-f100.1e100.net (173.194.64.100): icmp_req=5 ttl=43 time=47.6 ms 64 bytes from oa-in-f100.1e100.net (173.194.64.100): icmp_req=6 ttl=43 time=48.2 ms The attacker could probably do even better if he sent the request from a box hosted on a nearby network. So this shouldn't present too much of a problem. c) Getting the predicted cert number. The cert numbers in the pdf Feb 23 19:21:36 2010 GMT 14:51:5b:02:00:00:00:00:00:08 Jul 19 13:41:52 2010 GMT 33:f3:59:ca:00:00:00:05:25:e0 Jan 9 20:48:22 2011 GMT 47:67:04:39:00:00:00:0e:a2:e3 suggest that these were increasing at the rate of about 1094840 per year and that there was about 29 s on average between issuances. Assuming MS Terminal Services activations are twice as likely to happen during business hours (the actual factor is probably much larger than that), then probably there is a time of the week at which there is 60 s or more between activations. From the publicly documented demonstration at http://www.win.tue.nl/hashclash/rogue-ca/ : In a three day period from Thursday night to Sunday night, [RapidSSL] typically issues between 800 and 1000 certificates. Which is about 324 s on average between issuances. So the timing target was a bit tighter for the Flame attackers than the rogue-ca researchers, but not prohibitive. What is unclear is if there are any effective costs or rate limitations on how often one can 'activate' an MSTS license server. A compute cluster faster than 200 PS3s could cut down on the number of license certs that were burned to make the attack work. - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
On Tue, Jun 12, 2012 at 10:51:59AM -0500, Marsh Ray wrote: What is unclear is if there are any effective costs or rate limitations on how often one can 'activate' an MSTS license server. A compute cluster faster than 200 PS3s could cut down on the number of license certs that were burned to make the attack work. One wonders what Microsoft knows about who requested all those licenses. Presumably there was some effort put into plausible deniability. Thor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
Hi Florian, * Marsh Ray: Marc Stevens and B.M.M. de Weger (of http://www.win.tue.nl/hashclash/rogue-ca/) have been looking at the collision in the evil CN=MS cert. I'm sure they'll have a full report at some point. Until then, they have said this: [We] have confirmed that flame uses a yet unknown md5 chosen-prefix collision attack. Does this mean they've seen the original certificate in addition to the evil twin? No, we've only seen the 'evil twin'. That was sufficient for Marc to arrive at this conclusion. For the sake of fairness I would like to add that both the development of the 'forensic tool', and the discovery of the 'yet unknown attack' by analyzing the results of applying that tool to the 'evil' certificate, were entirely Marc's work. Grtz, Benne de Weger ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
On 06/10/2012 03:03 PM, Florian Weimer wrote: Does this mean they've seen the original certificate in addition to the evil twin? Until then, there is another explanation besides an advance in cryptanalysis. Just saying. 8-) I guess I look at it like this: Start with the simplest explanation: e0 - attacker implements cert collision attack much like that demonstrated by Stevens et al. in 2008, but having some different characteristics Then take each explanation in turn from the e1 - eN other possible explanations like: e1 - attacker compromises system holding the RSA signing key e2 - attacker bribes Microsoft personnel into issuing evil cert e3 - attacker factors 1024 bit RSA e4 - attacker finds second preimage on MD5 e5 - ... and so on Then to that explanation add the additional requirement: ... *and* fools Marc Stevens into thinking it's a cert collision attack much like that demonstrated in 2008, but having some different characteristics. So it's an advance in cryptanalysis either way. :-) - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
On 06/05/2012 07:21 AM, Douglas Pichardo wrote: The last link below [http://rmhrisk.wpengine.com/?p=52] points out that the sub-CA's were issued with constraints granting them: - License Server Verification (1.3.6.1.4.1.311.10.6.2) - Key Pack Licenses (1.3.6.1.4.1.311.10.6.1) - Code Signing (1.3.6.1.5.5.7.3.3) But I don't see any constraints at all listed in the MS.txt certificate you attached from [http://blog.crysys.hu/2012/06/the-flame-malware-wusetupv-exe-certificate-chain/]. Am I missing something here? No you're not. There aren't any. This is true not only for the evil cert, but also for Genuine Microsoft^TM Terminal Services License Server license certs. You can find examples with http://www.google.com/search?q=06+01+04+01+82+37+12; Attached are a couple of examples found this way. Ryan Hurst has more good detailed analyses on the MSTS licensing PKI goof based on a Genuine Microsoft^TM cert. http://rmhrisk.wpengine.com/?p=57 and http://rmhrisk.wpengine.com/?p=60 Marc Stevens and B.M.M. de Weger (of http://www.win.tue.nl/hashclash/rogue-ca/) have been looking at the collision in the evil CN=MS cert. I'm sure they'll have a full report at some point. Until then, they have said this: [We] have confirmed that flame uses a yet unknown md5 chosen-prefix collision attack. We are interested in other possible certs based on this md5 coll attack for further analysis. I am now analyzing their chosen-prefix collision attack in more detail, (more examples would greatly help) and trying to write up some results and conclusions to make a more detailed statement. The collision attack itself is very interesting from a scientific viewpoint and there are already some practical implications. Didier Stevens has posted the full chain at http://blog.didierstevens.com/2012/06/06/flame-authenticode-dumps-kb2718704/ There is a mystery cert CN=TLS Server in the executable. It does not appear to have a tumor. It's attached here. Perhaps someone can figure out what it's for. - Marsh P.S. The first couple of 64-byte blocks here are the tumor. For some reason, it does not show up with 'openssl x509 -text' or even 'openssl asn1parse -dump'. 500:d=2 hl=4 l= 888 prim: cont [ 1 ] dd if=MS.der bs=1 skip=500 count=888 | hd 81 82 03 78 00 6a 4c e0 1f f5 91 69 b2 74 36 f0 |...x.jLi.t6.| 0010 7f 7b 4b 7b c6 be eb 3f 9f 98 3d a3 84 87 54 7e |.{K{...?..=...T~| 0020 72 87 71 25 4b 68 35 ae 65 bd 6c 8f dc 8d ac c4 |r.q%Kh5.e.l.| 0030 e8 98 92 de dc 53 62 f5 72 6a 25 27 a3 12 46 eb |.Sb.rj%'..F.| 0040 7f 6d 58 cd 30 83 d7 7a 85 b8 48 e6 0e 01 11 68 |.mX.0..z..Hh| 0050 65 7d 53 38 0b 40 f4 3b 68 43 59 c1 3c 05 c3 40 |e}S8.@.;hCY...@| 0060 26 9d 51 97 e2 eb 2e b8 c2 19 6e 4e 94 46 3b d8 |.Q...nN.F;.| 0070 d4 fd 0d 00 d1 68 fa df f3 fa 18 8a 7c 65 9b da |.h..|e..| 0080 23 11 9f 16 a6 8b 23 24 88 87 22 69 19 c2 11 ea |#.#$..i| 0090 9d 36 81 ad fb e8 8b d2 d0 eb 06 f2 1a 86 8d c6 |.6..| 00a0 84 f3 88 c5 e0 d9 64 c6 48 95 d4 be d3 54 48 91 |..d.HTH.| 00b0 e6 6c e9 1e 33 97 15 42 ee b4 6d 1f 15 0b 27 dd |.l..3..B..m...'.| 00c0 08 bb 81 de b6 96 16 39 d9 26 44 6a 5f d1 6b 3f |...9.Dj_.k?| 00d0 12 71 dc f0 99 62 d2 43 14 58 f8 6e f8 22 35 d2 |.q...b.C.X.n.5.| 00e0 90 f7 fd 93 6a c4 49 b8 cb 0c e9 65 a8 f7 22 b5 |j.Ie...| 00f0 f2 05 19 20 ef 25 63 c7 b3 97 4a 82 3e b2 e3 ee |... .%c...J| 0100 b4 5e cb 1d b3 59 8f 8d f4 79 01 b1 b6 68 89 14 |.^...Y...y...h..| 0110 b4 8f 9d 60 d7 71 a5 3d 95 02 03 01 00 01 a3 82 |...`.q.=| 0120 02 5a 30 82 02 56 30 1d 06 03 55 1d 0e 04 16 04 |.Z0..V0...U.| 0130 14 9a 9a 5d 77 bd 84 66 a4 f1 de 18 10 1b 6e 67 |...]w..f..ng| 0140 a5 97 c1 14 87 30 1f 06 03 55 1d 23 04 18 30 16 |.0...U.#..0.| 0150 80 14 75 e8 03 58 5d fb 65 e4 d9 a6 ac 17 b6 03 |..u..X].e...| 0160 7e 47 ad 2e 81 af 30 81 c2 06 03 55 1d 1f 04 81 |~G0U| 0170 ba 30 81 b7 30 81 b4 a0 81 b1 a0 81 ae 86 56 68 |.0..0.Vh| 0180 74 74 70 3a 2f 2f 74 6b 78 70 61 73 72 76 33 36 |ttp://tkxpasrv36| 0190 2e 70 61 72 74 6e 65 72 73 2e 65 78 74 72 61 6e |.partners.extran| 01a0 65 74 2e 6d 69 63 72 6f 73 6f 66 74 2e 63 6f 6d |et.microsoft.com| 01b0 2f 43 65 72 74 45 6e 72 6f 6c 6c 2f 4d 69 63 72 |/CertEnroll/Micr| 01c0 6f 73 6f 66 74 25 32 30 4c 53
Re: [cryptography] Microsoft Sub-CA used in malware signing
These researchers have detailed the cert chain here: http://blog.crysys.hu/2012/06/the-flame-malware-wusetupv-exe-certificate-chain/ If you like X509, you'll find this interesting. I've attached copies for reference. Microsoft is saying some strange things like: http://blogs.technet.com/b/msrc/archive/2012/06/04/security-advisory-2718704-update-to-phased-mitigation-strategy.aspx?Redirected=true 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. Ryan Hurst CTO of GlobalSign has an interesting analysis of the MS Terminal Services license server protocol WRT current events. http://rmhrisk.wpengine.com/?p=52 An excerpt: That’s right, every single enterprise user of Microsoft Terminal Services on the planet had a CA key that could issue as many code signing certificates they wanted and for any name they wanted. It sounds as if Windows users might have a million code-signing DigiNotars to worry about. My guess is that there are multiple vulnerabilities in play here and maybe even a little bit of misdirection. I have a feeling the other shoe is going to drop sometime closer to next (patch) Tuesday. - Marsh Certificate: Data: Version: 3 (0x2) Serial Number: c1:00:8b:3c:3c:88:11:d1:3e:f6:63:ec:df:40 Signature Algorithm: md5WithRSAEncryption Issuer: OU=Copyright (c) 1997 Microsoft Corp., OU=Microsoft Corporation, CN=Microsoft Root Authority Validity Not Before: Jan 10 07:00:00 1997 GMT Not After : Dec 31 07:00:00 2020 GMT Subject: OU=Copyright (c) 1997 Microsoft Corp., OU=Microsoft Corporation, CN=Microsoft Root Authority Subject Public Key Info: Public Key Algorithm: rsaEncryption Public-Key: (2048 bit) Modulus: 00:a9:02:bd:c1:70:e6:3b:f2:4e:1b:28:9f:97:78: 5e:30:ea:a2:a9:8d:25:5f:f8:fe:95:4c:a3:b7:fe: 9d:a2:20:3e:7c:51:a2:9b:a2:8f:60:32:6b:d1:42: 64:79:ee:ac:76:c9:54:da:f2:eb:9c:86:1c:8f:9f: 84:66:b3:c5:6b:7a:62:23:d6:1d:3c:de:0f:01:92: e8:96:c4:bf:2d:66:9a:9a:68:26:99:d0:3a:2c:bf: 0c:b5:58:26:c1:46:e7:0a:3e:38:96:2c:a9:28:39: a8:ec:49:83:42:e3:84:0f:bb:9a:6c:55:61:ac:82: 7c:a1:60:2d:77:4c:e9:99:b4:64:3b:9a:50:1c:31: 08:24:14:9f:a9:e7:91:2b:18:e6:3d:98:63:14:60: 58:05:65:9f:1d:37:52:87:f7:a7:ef:94:02:c6:1b: d3:bf:55:45:b3:89:80:bf:3a:ec:54:94:4e:ae:fd: a7:7a:6d:74:4e:af:18:cc:96:09:28:21:00:57:90: 60:69:37:bb:4b:12:07:3c:56:ff:5b:fb:a4:66:0a: 08:a6:d2:81:56:57:ef:b6:3b:5e:16:81:77:04:da: f6:be:ae:80:95:fe:b0:cd:7f:d6:a7:1a:72:5c:3c: ca:bc:f0:08:a3:22:30:b3:06:85:c9:b3:20:77:13: 85:df Exponent: 65537 (0x10001) X509v3 extensions: 2.5.29.1: 0[.p.ir.#Q~..Mr0p1+0)..U...Copyright (c) 1997 Microsoft Corp.1.0...UMicrosoft Corporation1!0...UMicrosoft Root Authority..c..@ Signature Algorithm: md5WithRSAEncryption 95:e8:0b:c0:8d:f3:97:18:35:ed:b8:01:24:d8:77:11:f3:5c: 60:32:9f:9e:0b:cb:3e:05:91:88:8f:c9:3a:e6:21:f2:f0:57: 93:2c:b5:a0:47:c8:62:ef:fc:d7:cc:3b:3b:5a:a9:36:54:69: fe:24:6d:3f:c9:cc:aa:de:05:7c:dd:31:8d:3d:9f:10:70:6a: bb:fe:12:4f:18:69:c0:fc:d0:43:e3:11:5a:20:4f:ea:62:7b: af:aa:19:c8:2b:37:25:2d:be:65:a1:12:8a:25:0f:63:a3:f7: 54:1c:f9:21:c9:d6:15:f3:52:ac:6e:43:32:07:fd:82:17:f8: e5:67:6c:0d:51:f6:bd:f1:52:c7:bd:e7:c4:30:fc:20:31:09: 88:1d:95:29:1a:4d:d5:1d:02:a5:f1:80:e0:03:b4:5b:f4:b1: dd:c8:57:ee:65:49:c7:52:54:b6:b4:03:28:12:ff:90:d6:f0: 08:8f:7e:b8:97:c5:ab:37:2c:e4:7a:e4:a8:77:e3:76:a0:00: d0:6a:3f:c1:d2:36:8a:e0:41:12:a8:35:6a:1b:6a:db:35:e1: d4:1c:04:e4:a8:45:04:c8:5a:33:38:6e:4d:1c:0d:62:b7:0a: a2:8c:d3:d5:54:3f:46:cd:1c:55:a6:70:db:12:3a:87:93:75: 9f:a7:d2:a0 -BEGIN CERTIFICATE- MIIEEjCCAvqgAwIBAgIPAMEAizw8iBHRPvZj7N9AMA0GCSqGSIb3DQEBBAUAMHAx KzApBgNVBAsTIkNvcHlyaWdodCAoYykgMTk5NyBNaWNyb3NvZnQgQ29ycC4xHjAc BgNVBAsTFU1pY3Jvc29mdCBDb3Jwb3JhdGlvbjEhMB8GA1UEAxMYTWljcm9zb2Z0 IFJvb3QgQXV0aG9yaXR5MB4XDTk3MDExMDA3MDAwMFoXDTIwMTIzMTA3MDAwMFow cDErMCkGA1UECxMiQ29weXJpZ2h0IChjKSAxOTk3IE1pY3Jvc29mdCBDb3JwLjEe MBwGA1UECxMVTWljcm9zb2Z0IENvcnBvcmF0aW9uMSEwHwYDVQQDExhNaWNyb3Nv ZnQgUm9vdCBBdXRob3JpdHkwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIB AQCpAr3BcOY78k4bKJ+XeF4w6qKpjSVf+P6VTKO3/p2iID58UaKboo9gMmvRQmR5 7qx2yVTa8uuchhyPn4Rms8VremIj1h083g8BkuiWxL8tZpqaaCaZ0Dosvwy1WCbB
Re: [cryptography] Microsoft Sub-CA used in malware signing
2012/6/5 Marsh Ray ma...@extendedsubset.com [...] An excerpt: That’s right, every single enterprise user of Microsoft Terminal Services on the planet had a CA key that could issue as many code signing certificates they wanted and for any name they wanted. It sounds as if Windows users might have a million code-signing DigiNotars to worry about. md5withRSA, sequential serials, everybody-gets-a-CA... This is depressing. The timestamp on the signed objects allows the signature to stay valid for much longer than the validity of the signer. So the 2 years validity for TS-CA certificates is not a problem here. -- Erwann. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
On 06/04/2012 02:41 AM, Marsh Ray wrote: I've attached the revoked sub-CAs and their roots. In case its not clear from the filenames (e.g. the email system drops them) there were three certs revoked. These are the ones with Licensing in the CN. For convenience I also included the two root CA certs that issued them. These were not revoked. - Marsh ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
It's also not clear about what could have been done with TS certificates. Is it only codesigning, or TLS server as well? -- Erwann. Le 4 juin 2012 09:57, Marsh Ray ma...@extendedsubset.com a écrit : In case its not clear from the filenames (e.g. the email system drops them) there were three certs revoked. These are the ones with Licensing in the CN. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Microsoft Sub-CA used in malware signing
On Mon, Jun 04, 2012 at 10:20:33AM +0200, Erwann Abalea wrote: It's also not clear about what could have been done with TS certificates. Is it only codesigning, or TLS server as well? I'm surprised they can be used for code signing at all. TS (in its modern incarnation) is a TLS-encapsulated protocol. Thor ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography