[cryptography] Microsoft Sub-CA used in malware signing

Ben Laurie ben at links.org
Tue Jun 12 04:45:27 EDT 2012

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?

> 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