Cryptanalist Marc Stevens van het Centrum Wiskunde & Informatica (CWI) in Amsterdam, bekend van de 'kraak' van de https-beveiliging in 2008 met een cryptanalytische aanval op MD5, heeft deze week het recente Flame-virus geanalyseerd. Hij ontdekte dat voor deze spy malware een compleet nieuwe, tot nu toe onbekende cryptografische aanvalsvariant van zijn eigen MD5-aanval is gebruikt. Stevens analyseerde dit met nieuwe, door hem ontwikkelde forensische software. Aanvankelijk ging de onderzoeker ervan uit dat Flame zijn eigen, in 2009 openbaar gemaakte aanval gebruikte maar dit bleek niet het geval te zijn. "Flame gebruikt een geheel nieuwe variant van een 'chosen prefix collision' aanval om zich voor te doen als een legale beveiligingsupdate van Microsoft. Het maken van zo’n variant vereist cryptanalyse van wereldniveau," zegt Marc Stevens. "Het is dus zeer belangrijk om te investeren in cryptografisch onderzoek, om deze ontwikkelingen in de praktijk voor te blijven".
Het baanbrekende cryptografie-onderzoek is gedaan in CWI's Cryptology-groep, die onder leiding staat van prof.dr. Ronald Cramer. Deze groep onderzoekt fundamentele cryptografische vragen vanuit een breed wetenschappelijk perspectief, met name vanuit de wiskunde, computerwetenschap en natuurkunde. "Zonder ons fundamenteel wiskundig, cryptografisch onderzoek hadden we deze forensische software niet kunnen ontwikkelen", zegt Ronald Cramer. Het onderzoek van Marc Stevens maakt deel uit van diens promotieonderzoek, waarop hij op 19 juni aan het Mathematisch Instituut van de Universiteit Leiden hoopt te promoveren.
De gedetailleerde technische uitleg van CWI-onderzoeker Marc Stevens volgt onderaan dit bericht.
Proefschrift Marc Stevens: http://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf
Foto: CWI-onderzoekers prof. dr. Ronald Cramer (links) en ir. Marc Stevens. Foto: Centrum Wiskunde & Informatica (CWI).
TECHNICAL BACKGROUND OF THE FLAME COLLISION ATTACK
By Marc Stevens, CWI
FLAME design required world-class cryptanalysis: an as yet unknown variant cryptographic collision attack was revealed by a novel forensic tool, developed by Marc Stevens from the Centrum Wiskunde & Informatica (CWI) in Amsterdam. Marc Stevens is currently Scientific Staff Member in the Cryptology Group of prof. dr. Ronald Cramer at CWI. Marc’s research focuses on the cryptanalysis of cryptographic hash function standards.
The spy malware Flame (aka Flamer aka sKyWIper), whose discovery was announced on May 28 2012 by Kaspersky Lab, CrySys and the Iranian CERT [1], fulfills a long standing nightmare for security engineers: it is able to mask itself as a valid Windows Update and thus ironically can spread itself as a security patch [2]. Flame’s ability stems from the fact that it is signed by a fraudulent certificate appearing to be originating from Microsoft which was obtained by launching a cryptographic collision attack. Analysis of this collision attack using our forensic tools (see [7], chapter 8) has revealed the use of an as yet unknown variant of our chosen-prefix collision attack.
The first cryptographic collision attack against the cryptographic hash function MD5 was invented by Xiaoyun Wang et al. in 2004 [3], which however did not pose a serious immediate threat due to technical limitations. Subsequently, we have devised a more flexible collision attack against MD5 in 2007, a so-called chosen-prefix collision attack [4]. This posed a greater threat due to the removal of the most important technical limitation. Finally, we refined our attack in 2008 and used it to construct a rogue Certification Authority, thereby demonstrating a serious vulnerability in internet security. Our demonstration convinced Microsoft and various governments to raise the security standards for Certification Authorities, by disallowing the use of MD5-based signatures effective 15 January 2009 [6].
It is clear that Microsoft, at that time, should have also disallowed MD5-based signatures in their Terminal Server Licensing Service (TSLS). As apparently the Flame collision attack was executed in February 2010, it now turns out they did not; this has been an important oversight. The result of this collision attack on a Microsoft TSLS Certification Authority was a code-signing certificate appearing to be from Microsoft that may be used to sign Windows Updates. This attack avenue was essentially open to any knowledgeable attackers since June 2009, when, under the belief that MD5-based signatures had indeed been disallowed, we made the program sources for a chosen-prefix collision attack publicly available. Furthermore, it should be noted that, even without a collision attack, Microsoft has unsuspectingly been providing its TSLS customers with unwarranted code-signing abilities.
We have developed a forensic tool for collision attacks [7] that can efficiently detect a wide range of known and unknown collision attacks against MD5 as well as MD5's successor SHA-1. Moreover, this tool may also be used to online detect fraudulent certificates constructed using a collision attack.
Using our forensic tool, we have indeed verified that a chosen-prefix collision attack against MD5 has been used for Flame. More interestingly, the results have shown that not our published chosen-prefix collision attack was used, but an entirely new and unknown variant. Therefore it is not unreasonable to assume that the particular chosen-prefix collision attack variant underlying Flame had already been in development before June 2009. This has led to our conclusion that the design of Flame is partly based on world-class cryptanalysis. Further research will be conducted to reconstruct the entire chosen-prefix collision attack devised for Flame.
References:
1. "sKyWIper: A Complex Malware for Targeted Attacks".
Budapest University of Technology and Economics.
http://www.crysys.hu/skywiper/skywiper.pdf. 28 May 2012.
2. "Microsoft releases Security Advisory 2718704". Microsoft. 3 June 2012.
3. "How to break MD5 and other hash functions", Xiaoyun Wang and Hongbu Yu,
EUROCRYPT 2005, Lecture Notes in Computer Science, vol. 3494, Springer, 2005, pp. 19–35.
4. "Chosen-Prefix Collisions for MD5 and Colliding X.509
Certificates for Different Identities", Marc Stevens, Arjen Lenstra and Benne de Weger,
EUROCRYPT 2007, Lecture Notes in Computer Science, vol. 4515, Springer, 2007, pp. 1-22.
5. "Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate", Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, CRYPTO 2009, Lecture Notes in Computer Science, vol. 5677, Springer, 2009, pp. 55-69.
6. "Microsoft Root Certificate Program", Microsoft.
http://technet.microsoft.com/en-us/library/cc751157.aspx.
January 2009.
7. "Attacks on Hash Functions and Applications", Marc Stevens. PhD thesis. 19 June 2012. http://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf
