## Fun with Exponents: Certificate Forgery

Last week, we fixed a problem in OpenSSL. Explaining what’s going on here to non-cryptographers is a little tricky, but I’m going to have a go.

The essence of RSA is that you (carefully) pick three numbers, usually known as d, e and n. The details of how they are chosen isn’t important right now. Two of these numbers, conventionally e and n, you publish, and are known as your *public key* (e is known as the *exponent* and n as the *modulus*). The other, d, you keep secret and is your *private key*. These three numbers have some interesting properties.

Firstly, if you choose some other number, say x, and work out y = x^e mod n, then it turns out that x = y^d mod n.

Similarly, (and obviously from the previous property, but for completeness), if you choose another number, w, and calculate z = w^d mod n, then w = z^e mod n.

Finally, you can’t work out d from e and n.

Since you can safely pubish e and n, this means people can send you messages only you can read, by representing the message as a number, m, calculating c = m^e mod n and sending you c. You can then get m back by calculating c^d mod n, but no-one else can, because only you know d.

Similarly it is possible for you to “sign” a message, m, by calculating s = m^d mod n, and sending both m and s. Anyone can verify that this is indeed a signature for m by calculating s^e mod n, and seeing that it matches m, but only you could have calculated s in the first place.

Well, almost. Here’s where it all went wrong. For various reasons, its quite popular to choose certain values for e. 3 and 65537 (which is 2^16 + 1) are common. It turns out that its still easy to find suitable values for d and n even if you’ve fixed e.

So, when e is 3, the way you verify that a signature is correct is by calculating s^3 mod n, and making sure it matches m. Now, you might think that this is obviously broken, because all you need to do is work out the cube root of m, which any fool can do, and you’ll have a signature, s, whether you know d or not. But this isn’t so, because s and m are both constrained to be whole numbers. Unless by some chance m turns out to be a perfect cube, you can’t find a whole cube root. There’s still *some* number that when cubed mod n will yield m, but you can’t figure out what it is without knowing d.

And there’s the fault. It turned out that because of some inadequate checking in OpenSSL it was possible to take the real message, m, and add some extra stuff to it that OpenSSL didn’t “see”. If you chose the stuff carefully, you could make “m+stuff” a perfect cube, work out the cube root, s, and send it. OpenSSL would then verify this signature by cubing s, get m+stuff, fail to notice the extra stuff on the end and say, “yes, this is a signature for m”.

There was also another attack, where effectively you split m into two parts, so m = a + b. It was then possible to find stuff so that a + stuff + b is a perfect cube, but, again, have OpenSSL ignore the stuff in the middle, and just see a and b.

Either of these methods could be used to make fake SSL certificates. And since there are certificate authorities built into common browsers with exponent 3, if the browser uses a cryptographic library with this bug in it, it will believe the certificate.

Does this work against larger exponents (e is known as the exponent, by the way)? Well, yes, but the larger the exponent is, the less chance you have of finding the extra stuff to make any particular message a perfect nth power. I can just about make it work for e=5 for reasonable key sizes, but it gets harder very rapidly as e increases, and it turns out that people don’t use small e other than 3 very much.

Note for purists and crypto-geeks: yes, I’ve left out *lots* of detail here, I doubt more detail would have aided understanding by a general audience. I (and others) are considering writing up a more precise description of how you mount these attacks, but, on the other hand, it is Bleichenbacher’s baby, so perhaps we’ll leave it to him – and its a lot more work than this general explanation! :-).

[...] Thomas Ptacek blogged about the exponent 3 exploit, with pictures! [...]

Pingback by Links » Exponent 3: With Pictures! — 11 Sep 2006 @ 10:36

[...] Understand what we just said. The RSA signature attack is an example of that kind of an attack, but RSA is not the only cryptosystem that has these properties. The same kinds of tiny bugs can create catastrophes for DSA, Elliptic-Curve DSA, SRP, Diffie-Hellman, and so on. [...]

Pingback by Matasano Chargen » RSA Signature Forgery Explained (with Nate Lawson) - Part II — 13 Sep 2006 @ 14:14