Complexity of web certificate attacks

Question

I heard a while ago about someone exploiting md5 weaknesses to create a web certificate with the same md5 that a different certificate has.

They were able to create a certificate through bad issuing policies and i think they had 200 ps3 calculating.

So I wondered, is it possible to scrape the whole web for certificates and create a database with all of them and use brute force to create a certificate that has the same md5 as one in the database?

So my question: Does anyone know the math behind this? I mean how many unique md5s are there? I think its 32^16. How many certificates are there with md5 (including outdated, they will still work) then estimate hash/min for an average computer.

I know that a lot of certificates have changed to sha1. I must say that I don't think this is possible but its a thought that have bugged me for a loooong time now and i need input! There's a lot of md5's but i have a fast computer ;)

Answer 1

MD5 has been deprecated due to the ease in which you can find a collision: a few years ago I wrote a paper showing how to generate an MD5 collision in under a minute. This has since been refined to just a few seconds.

Generating two different postscript documents with the same MD5 sum leverages the fact that postscript is a computer language and postscript viewers evaluate this language. It's a neat trick. It works like this: File1 has a binary block Q, then some code, then document A, then document B. When you display File1, it runs the code which examines Q then displays A.

Now we make a copy of File1 called File2. We modify only Q to Q' which has the same MD5 sum as Q. This means that File2 has the same MD5 sum as File1 since nothing else changes. But now when we display File2 it runs the same code, sees Q' and outputs document B. Cute!

But here we are using the fact that collisions are easy to find in MD5. No one (as far as I know) can invert arbitrary MD5 digests, nor can anyone find a 2nd input to match a given file's MD5 sum (this is called "second preimage resistance").

So what you suggest above is still infeasible. The math you asked for: MD5 outputs 128 bits, so the chance that a random digest will match a given one is $1/2^{128}$ and it will therefore take an expected $2^{128}$ trials to reproduce a desired digest.

Answer 2

The existing attacks are about collisions: the attacker builds two certificates which hash to the same MD5, but with distinct contents. One of them is "benign" (it contains the attacker's name) and this is the one which the attacker sends to the CA for a signature. The CA signs it, because it is a perfectly valid certificate request (it comes from the attacker and really contains the attacker's name). Thanks to the MD5 collision, the signature is also verifiable when plugged in the other certificate. So the attacker got a CA signature on a certificate on which he chose the contents out of control of the CA. Details are a bit complex because the attacker must find a collision in such a way that the two resulting certificates are both "structurally valid".

What you ask for is something very different: you are asking about an attacker trying to generate a certificate with a hash matching that of an existing certificate, one that the attacker did not generate in the first place. This is called a second preimage attack and is generally harder than finding collisions. In particular, there is currently no known weakness in MD5 with regards to second preimages.

There are 2¹²⁸ possible MD5 outputs (that's 16³², not 32¹⁶). On a general basis, if you have N input messages m₁, m₂,... m_N, and you want to build a new message m distinct from all the m_i but such that the MD5 of m is equal to the MD5 of one of the m_i (any will do), then the best known attack method is simply trying random messages m until one matches. The average cost of that operation will be 2¹²⁸/N.

There are probably much less than 2³² SSL certificates out there, so this means that the attack cost will be at least 2⁹⁶, which is totally unfeasible with existing technology. So this attack will not work. Breaking a CA public key will be much easier (not feasible either, but still easier, by a factor about 1 million if the attacked CA key is a 1024-bit RSA key).

Actually, for certificates, the attack is more expensive than that, because a certificate contains the name of the issuing CA. Having a matching signature from the CA (e.g. through using the same MD5) is not enough for the resulting certificate to be of any use: it must also properly "chain" with the CA, which implies containing the CA name as "issuer name". So the N in the formula above is not the total number of certificates existing in the wild, but the total number of certificates emitted by a given CA which you have to target specifically. That's lower, yielding an even higher attack cost.