Furthermore, we present the first example of counter-cryptanalysis, namely the efficient detection whether any given single message has been constructed -- together with an \emph{unknown} sibling message -- using a cryptanalytic collision attack on MD5 or SHA-1.
An immediate application is in digital signature verification software to ensure that an (older) MD5 or SHA-1 based digital signature is not a forgery using a collision attack. This would certainly be desirable for two reasons. Firstly, it might still be possible to generate malicious forgeries using collision attacks as too many parties still sign using MD5 (or SHA-1) based signature schemes. Secondly, any such forgeries are currently accepted nearly everywhere due to the ubiquitous support of MD5 and SHA-1 based signature schemes. Despite the academic push to use more secure hash functions over the last decade, these two real-world arguments (arguably) will remain valid for many more years.
Only due to counter-cryptanalysis were we able to discover that Flame, a highly advanced malware for cyberwarfare uncovered in May 2012, employed an as of yet unknown variant of our chosen-prefix collision attack on MD5 \cite{DBLP:conf/eurocrypt/StevensLW07,DBLP:conf/crypto/StevensSALMOW09}. In this paper we disect the revealed cryptanalytic details and work towards the reconstruction of the algorithms underlying Flame's new variant attack. Finally, we make a preliminary comparision between Flame's attack and our chosen-prefix collision attack.
Category / Keywords: secret-key cryptography / counter-cryptanalysis hash functions MD5 SHA-1 collision attack differential path Flame malware Publication Info: CRYPTO 2013 Date: received 7 Jun 2013 Contact author: marc at marc-stevens nl Available format(s): PDF | BibTeX Citation Version: 20130610:130359 (All versions of this report) Short URL: ia.cr/2013/358 Discussion forum: Show discussion | Start new discussion