What Was Flame? The Malware That Did Original Cryptanalysis to Sign Itself
Windows will not install an update that is not signed by Microsoft. Flame had a valid Microsoft signature.
That sentence is the whole reason this one is in the archive. Everything else Flame did had been done before.
What was Flame?
Flame — also called Flamer and sKyWIper — was found in May 2012, independently by Kaspersky Lab, Hungary's CrySyS Lab, and Iran's MAHER centre. It targeted the Middle East, Iran most heavily.
It was roughly twenty megabytes, which for malware is enormous — orders of magnitude larger than anything comparable, built as a modular platform with an embedded Lua interpreter and a local database. Its modules logged keystrokes, captured screenshots, recorded audio through the machine's microphone, and enumerated nearby Bluetooth devices.
It shared code with early Stuxnet, which places it in the same programme rather than merely the same neighbourhood.
It also carried a self-removal module that wiped every trace of itself on command, which was used once the discovery became public.
The certificate
Flame's most useful capability was lateral movement: on a local network it could position itself as a Windows Update proxy and offer neighbouring machines a signed update that was actually Flame.
To do that it needed to be signed by Microsoft, and it was.
The path ran through Terminal Server Licensing Service certificates. Enterprises running Remote Desktop licensing could obtain certificates from Microsoft to activate their licence servers. Because of how that infrastructure had evolved, those certificates chained to a Microsoft root, and — the fatal part — they were still being issued signed with MD5.
MD5 had been considered cryptographically broken for years. Collisions had been demonstrated publicly since 2004, and a chosen-prefix collision had been used against a real certificate authority in 2008 by a research team who built a rogue CA to prove the point. The technique was known. The response, industry-wide, had been to migrate away from MD5 slowly.
What a chosen-prefix collision actually is
An ordinary collision means finding two inputs with the same hash, where you do not get to choose what those inputs look like. That is a curiosity.
A chosen-prefix collision means you start with two different meaningful beginnings — say, a legitimate certificate request and a malicious one — and compute filler that makes the two complete documents hash identically. Now a signature over the harmless document is, byte for byte, also a valid signature over the malicious one.
That is why the shirt is two different scrolls and one seal.
Correcting the record
The usual retelling is that Flame exploited weak MD5 certificates, which is true and undersells it considerably.
When cryptographers examined the collision — Marc Stevens, who had co-authored the 2008 rogue-CA work, prominently among them — the finding was that the attack did not match any published technique. It was a variant of chosen-prefix collision that had not appeared in the academic literature.
Somebody had advanced the state of the art in applied cryptanalysis, privately, and used the result to make a piece of malware look like a software update.
That is a genuinely unusual event. Nation-state malware normally buys or steals its certificates — Stuxnet used stolen Realtek and JMicron keys. Flame's authors did mathematics instead.
What it changed
Microsoft responded within days: Security Advisory 2718704, revocation of the affected intermediate certificates, and a hardening of the Windows Update channel so that a compromised certificate could not be used the same way again.
The wider effect was the end of the slow migration. MD5 in certificate signing went from deprecated-in-principle to removed, quickly, because the theoretical attack had a working instance in the wild signed by the world's largest software vendor.
The uncomfortable question the incident raised has not been answered. If a well-resourced actor was, in 2012, holding unpublished cryptanalytic results and spending them on operational tooling, the reasonable assumption is that this was not the only one.
Further reading
- CrySyS Lab — sKyWIper: A Complex Malware for Targeted Attacks (May 2012). The original technical report.
- Marc Stevens — Counter-cryptanalysis (CRYPTO 2013), on identifying the collision variant used.
- Sotirov, Stevens et al. — MD5 considered harmful today (2008), the rogue CA work that preceded it.
- Microsoft Security Advisory 2718704 and the Security Research & Defense post on the certificate chain.
EXHIBIT 0014 — FLAME
We put it on a shirt. Two documents entering the frame from opposite sides, visibly different from one another, curving down and terminating in a single identical wax seal.
Most people will read it as a certificate. A smaller number will notice there are two of them.
That's the whole idea.