CWI Cryptology Group

Abstract: Flame, a highly advanced malware for cyberwarfare discovered in May, spread itself through Microsoft Windows Update as a properly, but illegitimately, signed security patch. Flame achieved this by forging a signature from Microsoft using a so-called chosen-prefix collision attack on the very weak cryptographic hash function MD5.
In this talk we will introduce counter-cryptanalysis, a new paradigm for strengthening cryptographic primitives, and the first example thereof, namely an efficient anomaly detection technique that detects whether a given signature was forged using a cryptanalytic collision attack on the underlying hash function.
We have used our new technique to analyze the collision attack used by Flame and made the very surprising (and scientifically interesting) discovery that Flame used an as of yet unknown variant of our chosen-prefix collision attack that we introduced in 2007 and greatly improved in 2009. In this talk we will also present our analysis of this new variant attack.

Abstract: On June 3, 2012, Microsoft published an emergency, out-of-band critical update that revoked two X.509 certificates associated with the Microsoft Public Key Infrastructure (PKI). These certificates were revoked in order to shut down a propagation mechanism being used by the Flame malware. Flame was digitally signed with private key associated with a forged (but cryptographically valid) X.509v3 public key certificate that chained into a portion of the Microsoft PKI; the forged certificate was created using an MD5 hash collision attack against a live Microsoft Certificate Authority.
Microsoft Research personnel were involved very early on in the analysis of the Flame malware and the development of Microsoft's corporate response, and following that work we have begun a project looking at building tools that could efficiently and automatically detect signed objects that appeared to be created through hash collision attacks. In this talk we will discuss MSR's involvement in the analysis and response to the Flame malware, the specific hash collision attack that the authors of Flame carried out against the Microsoft PKI, and our attempts to develop automated mechanisms for detecting future attempts to subvert other PKIs in a similar fashion.