2014-01-24

Maximilian Johann Fillinger - Reconstructing the Cryptanalytic Attack behind the Flame Malware

Interesting crypto paper:
Reconstructing the Cryptanalytic Attack behind the Flame Malware
Fillinger, Maximilian Johann

This paper is analyzing this algorithm the authors of the Flame malware (2012) used an MD5 collision to forge a Windows code-signing certificate.
It claims that complexity of the MD5 attack used to fake RSA certificate signatures as used in Flame
was approximately 2^46 - 2^49 of MD5 operations.

It is surprise that it is not (dramatically) faster than the other known solutions as it was originally expected.
So it is contrary to original speculations on it using some backdoor in MD5 or some NSA special intelligenco on MD5 not known to public :).

------------------------------------
Just to recap history of attacks to MD5:

1996 - collisions found in the compression function of MD5 (and rest of the MD family)
2004 - identical prefix collision - Wang et al. - 2^40 operations
2005 - identical prefix collision - Wang and Yu - 2^39 operations
2005 - identical prefix collision - Vlastimil Klima - 2^33 operations
2006 - identical prefix collision -Marc Stevens - 2^32 of MD5
2006 - identical prefix collision - Peter Selinger - code published based on Wang et al. 2^39 operations
2007 - identical prefix collision - Mark Stevens - 2^25
2007 - choosen prefix collision - Mark Stevens,Arjen K. Lenstra, and Benne de Weger - 2^49 operations
2008 - identical prefix collision - Xie et al. - 2^21 operations
2009 - identical prefix collision - Mark Stevens - 2^16 operations
2009 - choosen prefix collision - Mark Stevens,Arjen K. Lenstra, and Benne de Weger - 2^39 operations
2010 - single block collision - Tao Xie, Dengguo Feng - 2^47 MD5 operations
2012 - single block collision - Mark Stevens - 2^50 operations
2013 - single block collision - Tao Xie, Fanbao Liu, Dengguo Feng - 2^41


Sites related:
http://marc-stevens.nl/research/
http://www.win.tue.nl/hashclash/
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/

No comments:

Post a Comment