Paper 2016/298

Reverse-Engineering of the Cryptanalytic Attack Used in the Flame Super-Malware

Max Fillinger and Marc Stevens


In May 2012, a highly advanced malware for espionage dubbed Flame was found targeting the Middle-East. As it turned out, it used a forged signature to infect Windows machines by MITM-ing Windows Update. Using counter-cryptanalysis, Stevens found that the forged signature was made possible by a chosen-prefix attack on MD5 \cite{DBLP:conf/crypto/Stevens13}. He uncovered some details that prove that this attack differs from collision attacks in the public literature, yet many questions about techniques and complexity remained unanswered. In this paper, we demonstrate that significantly more information can be deduced from the example collision. Namely, that these details are actually sufficient to reconstruct the collision attack to a great extent using some weak logical assumptions. In particular, we contribute an analysis of the differential path family for each of the four near-collision blocks, the chaining value differences elimination procedure and a complexity analysis of the near-collision block attacks and the associated birthday search for various parameter choices. Furthermore, we were able to prove a lower-bound for the attack's complexity. This reverse-engineering of a non-academic cryptanalytic attack exploited in the real world seems to be without precedent. As it allegedly was developed by some nation-state(s), we discuss potential insights to their cryptanalytic knowledge and capabilities.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2015
MD5hash functioncryptanalysisreverse engineeringsignature forgery
Contact author(s)
max fillinger @ cwi nl
2016-03-17: received
Short URL
Creative Commons Attribution


      author = {Max Fillinger and Marc Stevens},
      title = {Reverse-Engineering of the Cryptanalytic Attack Used in the Flame Super-Malware},
      howpublished = {Cryptology ePrint Archive, Paper 2016/298},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.