It has been reported that the Flame malware can covertly install malicious code delivered through Windows Update [1]. By using a man-in-the-middle (MITM) attack and a certificate which appears to be digitally signed by Microsoft, the malicious code is accepted by Windows with no warning. Amazingly, the certificate is a forgery — created using an MD5 hash collision [2].
Media hype about the Flame malware's MD5 attack [3] have confused and overshadowed, to some extent, the more serious problem which made these attacks possible: Microsoft's poorly engineered security architecture. Flame is the first instance of malicious certificate forgery in the wild, but practical certificate forgery using MD5 hash collisions was demonstrated years ago [4]. Flame represents a malware milestone, but is not a new class of crypto attack.
This threat boils down to two distinct security issues. Either of these on its own can compromise Microsoft code-signing and Windows Update on many systems. Issue 1 provided the basis for the attack, and Issue 2 extended the attack to all Windows platforms. It's likely that Issue 1 simplified the hash collision problem.
Microsoft has a Terminal Services product, and a 'license server' for Terminal Services. Anyone can run a license server. During the internet-based activation process, the license server creates a public/private key pair and asks Microsoft to sign its certificate. It is automatically granted a certificate that is signed by a Microsoft certificate authority [2]. The resulting legitimate certificate is meant to be used for Terminal Services.
However, it turns out this certificate doesn't have extended key usage restrictions and allows code-signing, inherited from the authority's certificate. This means that anyone who activates their license server has a certificate that allows them to sign code as Microsoft! This appears to have been the case since at least 2010. No hash collision or crypto attack is needed on Windows XP; the certificate is instantly valid for signing any arbitrary code you present to Windows Update.
It's worth noting that this is a critical bug in Microsoft's trust architecture, with many forgery and intrusion consequences.
Vista and Windows7 include an extension in the certificate that safeguards against use for code-signing [2]. To make the certificate work on those platforms, the attacker had to modify/forge the certificate to remove that extension. Cryptographic hashes like MD5 and SHA-1 protect a certificate from tampering. Luckily for the attacker, Microsoft used the weaker MD5 hash (see Issue 2).
Certificates hashed with MD5 alone are vulnerable to forgery and can result in spoofing attacks. This is true for any application, any operating system.
Meaningful MD5 collisions could be found since at least 2005 [5]
MD5 collisions were used to create a practical, forged certificate authority in 2008, demonstrated in the RapidSSL attack [4]
Flame authors apparently used a previously unknown MD5 chosen-prefix collision attack [2], which means there is a way to attack MD5 that has not been published
Alex Sotirov estimates the Flame hash collision complexity was about the same as RapidSSL, which generated a collision in approximately 2 days on their cluster
Flame authors had to retry collisions 10-100x in order to predict millisecond time stamps. Assuming their cluster was similar, this could be done in a couple months (perfectly feasible)
Flame aside, MD5 was already broken for crypto (known in 2005, proof of concept in 2008)
We learned that Windows had a major bug in certificate trust for code-signing (Issue 1)
We learned that Microsoft security architecture was still using MD5 in certificates, when it was known to be broken for years (Issue 2)
We now have an attack in the wild that uses a forged certificate created through an MD5 attack
The method used by Flame authors to collide MD5 is not identical to HashClash [4], but there is no strong evidence to suggest that Flame authors have a faster algorithm
After this incident, Windows Update doesn't seem very trustworthy (even with the fixes)
Don't use MD5 in certificates and digital signatures
Review your certificate authority trust chains very carefully
In certificate generation, truly random serial numbers will make attacks more difficult
Windows systems have been vulnerable to this for a long time (4 years?)
There were two critical bugs in Windows
Yes, Flame authors must have used advanced MD5 collision techniques, but
[1] http://www.techspot.com/news/48886-flame-malware-subverts-windows-updates-infects-networked-pcs.html
[2] http://trailofbits.files.wordpress.com/2012/06/flame-md5.pdf
[3] http://arstechnica.com/security/2012/06/flame-crypto-breakthrough/
[4] http://www.win.tue.nl/hashclash/rogue-ca/
[5] http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html
[6] http://technet.microsoft.com/en-us/security/advisory/961509
[7] http://technet.microsoft.com/en-us/security/advisory/2718704