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<n...@cryptonector.com> wrote:
On Sun, Jun 10, 2012 at 3:03 PM, Florian Weimer<f...@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.
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@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
