[cryptography] Microsoft Sub-CA used in malware signing

Marc Stevens marc at marc-stevens.nl
Tue Jun 12 03:24:05 EDT 2012

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:

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.
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 
I don't know any CA that allows you to add arbitrary x509 fields as 

All the best,

More information about the cryptography mailing list