Cryptanalyst Marc Stevens from the Centrum Wiskunde & Informatica (CWI) in Amsterdam, known for breaking the https security in 2008 using a cryptanalytic attack on MD5, analyzed the recent Flame virus this week. He discovered that for this spy malware an as yet unknown cryptographic attack variant of his own MD5 attack is used. Stevens analyzed this with new forensic software that he developed. Initially, the researcher assumed that Flame used his own attack, which was made public in June 2009, but this was not the case. “Flame uses a completely new variant of a ‘chosen prefix collision attack’ to impersonate a legitimate security update from Microsoft. The design of this new variant required world-class cryptanalysis,” says Marc Stevens. “It is very important to invest in cryptographic research, to continue to be ahead of these developments in practice.”
The groundbreaking research was done in the CWI Cryptology group, which is headed by Prof. Ronald Cramer. This group investigates fundamental cryptographic questions from a broad scientific perspective, particularly from mathematics, computer science and physics. "Without our fundamental mathematical, cryptographic research, we could not have developed this forensic software," says Ronald Cramer. The research of Marc Stevens is part of his PhD research. His PhD ceremony takes place at the Mathematical Institute of Leiden University on 19 June.
The detailed technical explanation of CWI researcher Marc Stevens follows below this news item.
PhD dissertation Marc Stevens: http://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf
Picture: CWI researchers Prof. dr. Ronald Cramer (left) and ir. Marc Stevens. Source: 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
