[Cryptography] NSA and cryptanalysis

[Jerry Leichter]

>>> Do we know they produced fake windows updates without assistance
>>> from Microsoft?
>> 
>> Given the reaction from Microsoft, yes.
>> 
>> The Microsoft public affairs people have been demonstrating real
>> anger at the Flame attack in many forums.
> 
> ...Clearly, as things like bad vendor drivers updates have been sent out
> using stolen keys in the past, and clearly vendors might simply make
> mistakes in the future....

Except that that's not what happened in this case.

Someone took an old, valid Microsoft license - which should never have been issued, and which was blocked on Vista and Windows 7.  They worked around the block using a technique that required the ability to produce MD5 collisions, which allowed them to spoof Windows Update.  All the details are at http://trailofbits.files.wordpress.com/2012/06/flame-md5.pdf.

A cryptographic approach for producing chosen-prefix collisions in MD5 was presented at CCC in 2008, with a cost estimate of about $20K on a 2008 Amazon EC2 cluster - the authors showed a POC using a cluster of PS3's.  Open source code to implement the attack was published in 2009.

However, the form of the collision apparently didn't match the published code, nor, more fundamentally, the theoretical work that made it possible.  Someone has a *different*, so far nowhere-published attack.  The comment that this required "world-class cryptanalysis" came from the developer of the published chosen-prefix attack, Marc Stevens.
                                                        -- Jerry