We’ve already written about the ability of the Flame malware to trick you into installing apparently-trusted software signed with a fraudulent digital certificate.
Microsoft has now gone public with additional information about the cryptographic trickery used in this case.
For pre-Vista versions of Windows, it seems that the certificate spoofing didn’t rely on any sort of cryptographic forgery.
But for Vista and later, the attackers needed to forge a certificate. They did this using an MD5 collision.
The details of what the forged certificate looked like can be found on the Technet blog; here, we’ll simply review what we mean by “an MD5 collision.”
Digital certificates rely on public-key cryptography. You use a private key to encrypt the certificate; the recipient can use your public key – and only your public key – to decrypt it and thus to validate it. If the certificate doesn’t decrypt with your public key, then clearly you didn’t sign it, and vice versa.
Except that public-key algorithms aren’t good at encrypting and decrypting arbitrarily-sized blocks of data such as certificate files, not least because they’re very much slower than non-public-key cryptographic algorithms.
So, to digitally sign a file, you first generate a cryptographic hash of it – generating a fixed-length fingerprint – and then use public-key encryption on just the hash.
This makes computation much more convenient, but at the cost that the digital signature is now only as strong as the weaker of the hash algorithm and the public-key algorithm.
In the Flame case, the attackers took a legitimate Microsoft certificate using MD5 for its hash and RSA-2048 for its public-key encryption. They then generated a similar-but-different certificate with the same MD5 hash. This means that the RSA-2048 signature from Microsoft’s genuine certificate could be grafted into their forged certificate to make it appear valid.
Of course, this isn’t supposed to happen. For a hashing algorithm to be considered cryptographically sound, there should be no method better than chance (i.e. no alternative to brute force) for creating two objects with a matching hash.
But this isn’t true for MD5. Back in 2004, Chinese researchers showed how to create colliding MD5 messages in about one hour on a (then) high-end IBM server.
And by the end of 2008, European researchers had successfully generated a rogue Certificate Authority (CA) digital certificate. They used a network of 200 PS3s for the computational heavy lifting.
The moral of the story?
Don’t use digital certificates which rely on MD5. In fact, avoid MD5 as far as you can. You should not use MD5 in any new IT project.