[cryptography] Microsoft Sub-CA used in malware signing

Marc Stevens marc at marc-stevens.nl
Tue Jun 12 05:09:40 EDT 2012

On 12-6-2012 10:45, Ben Laurie wrote:
> On Tue, Jun 12, 2012 at 8:24 AM, Marc Stevens<marc at 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 Williams<nico at cryptonector.com>
>>>>>   wrote:
>>>>>> On Sun, Jun 10, 2012 at 3:03 PM, Florian Weimer<fw at 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
>>>>> <something>    to 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:
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 

>> 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 don't think it will work in
>> practice:
>> I don't know any CA that allows you to add arbitrary x509 fields as
>> required.
>> All the best,
>>     Marc
>> _______________________________________________
>> cryptography mailing list
>> cryptography at randombit.net
>> http://lists.randombit.net/mailman/listinfo/cryptography

More information about the cryptography mailing list