Real World Exploit for Bleichenbachers Attack on SSL from Crypto'06 working

[Erik Tews]

Hi

I had an idea very similar to the one Peter Gutmann had this morning. I
managed to write a real world exploit which takes as input:

      * an CA-Certificate using 1024 Bit RSA and Exponent 3 (ca-in)
      * a Public Key, using an algorithm and size of your choice
        (key-in)

and generats an CA-Certificate signed by ca-in, using public key key-in.

At least 3 major webbrowsers on the marked are shipped by default with
CA certificates, which have signed other intermediate CAs which use
rsa1024 with exponent 3, in their current version. With this exploit,
you can now sign arbitary server certificates for any website of your
choice, which are accepted by all 3 webbrowsers without any kind of
ssl-warning-message.

I used the following method:

I first generated a certificate, with BasicConstraints set to True,
Public Key set to one of my keys, and Issuer to the DN of a CA using
1024 Bit RSA with Exponent 3. I used usual values for all the other
fields. When I signed a Certificate I shiftet all my data to the left. I
had 46 bytes of fixed valued (this can perhaps be reduced to 45 bytes, I
have not checked yet, but even with 46, this attack works). They had the
form 00 01 FF FF FF FF FF FF FF FF ASN1DataWithHash. This gives me 82
bytes I can fill with arbitary values (at least, if the implementations
skipps some part of the asn1-data, I can choose some bytes there too).

If you now set all the bytes right of your ASN1DataWithHash to 00, and
interpret that as a number n, and compute:

                       y = (ceil(cubeRoot(n)))^3

   Where ceil means rounding to the next bigger natural number and cubeRoot
                     computes the third Root in R.

y will be a perfect cube and have the form:

        00 01 FF FF FF FF FF FF FF FF ASN1DataWithHash' Garbage

and ASN1DataWithHash' looks quite similar to your original
ASN1DataWithHash, with perhaps 2-3 rightmost bytes changed. These bytes
are part of the certificate hash value.

This signature is useless, because every certificate has a fixed hash
value. But you don't need to sign a fixed certificate. So i started
adding some seconds to the notAfter value of the certificate and
computed the hash again. I brute forced until I had a certificate where
the computation of y did not alter any bytes of the ASN1DataWithHash.

I had to try 275992 different values which took 2-3 minutes on my 1.7
GHz Pentium using an unoptimized java-implementation.

I used this cert and my key to sign an end-entity certificate which I
used to set up an webserver.

I have to check some legal aspects before publishing the names of the
browser which accepted this certificate and the name of the
ca-certificates with exponent 3 I used in some hours, if nobody tells me
not to do that. Depending on the advice I get, I will release the
sourcecode of the exploit too.

Thanks go to Alexander May and Ralf-Philipp Weinmann who helped me.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Dies ist ein digital signierter Nachrichtenteil
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20060915/d9d702c6/attachment.pgp>