Universiteit Leiden Universiteit Leiden

Nederlands English

CWI-cryptanalist ontdekt nieuwe cryptografische aanvalsvariant in Flame-virus

Cryptanalist Marc Stevens van het Centrum Wiskunde & Informatica (CWI) in Amsterdam, bekend van zijn 'kraak' van de MD5 hash-functie voor https-beveiliging in 2008, 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 voor overheden en bedrijven om te investeren in cryptografisch onderzoek, om deze ontwikkelingen in de praktijk voor te blijven”.

Proefschrift Marc Stevens

Baanbrekend cryptografie-onderzoek

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.

Over het CWI

Het Centrum Wiskunde & Informatica (CWI) is sinds 1946 het nationale onderzoeksinstituut voor wiskunde en informatica. Het is gevestigd op het Science Park Amsterdam en is deel van de Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO). Het instituut heeft een sterke internationale positie. Ruim 150 wetenschappers doen er grensverleggend onderzoek en dragen de verkregen kennis over aan de maatschappij. Meer dan 30 van de onderzoekers zijn hoogleraar aan een universiteit. Het instituut heeft 21 spin-off bedrijven voortgebracht.

Gedetailleerde technische uitleg

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.