RSA Signature Forgery Explained (with Nate Lawson) - Part III

Thomas Ptacek | September 13th, 2006 | Filed Under: Defenses, Guests, New Findings, Uncategorized

«Previous: Why Public Key Is Hard | Top | Next: Bad Patches»

For an object lesson in how small errors explode cryptosystems, let’s consider the recent RSA attack.

In a TLS/SSL setting, a browser (for instance) depends on an RSA verify operation to ensure that a certificate received from a web site was approved by one of several CA authorities embedded in the browser. Each CA root cert contains a public key, and a valid server certificate (e.g., for amazon.com) will be signed with a CA’s key. If an attacker could forge a signature of any of the authorities, then they can create bogus certificates for any web site. Phishers could pretend to be WELLSFARGO.COM. If you can forge X.509 certificates, you can mint your own, hand them out to your friends, and sell them to your customers.

X.509 certificate data is bound to a signature using a hash function (SHA1, unless it’s legacy MD5). A SHA1 hash is 20 bytes long. But RSA needs much more data than this to work with; with 1024-bit keys, RSA needs 128 bytes. This is because RSA’s security depends on the properties of numbers, in this case their size and structure (more below).

So we expand the data to sign by padding it. In PKCS#1v1.5, we:

• encode the digest algorithm type (SHA1) as an ASN.1 OID

• stick that in an ASN.1 sequence

• encode the message digest as an ASN.1 octet string

• paste the OID and the digest together in another sequence, and

• prepend:

   00 01 FF... [88 more] ...FF 00
  

Now, the only thing that’s obviously important in this structure is the hash value. If we receive a certificate with a signature, decode it with a public key, and end up with something we can “parse”, we appear to be able to “check” the signature by finding the digest, applying the same hash algorithm to the certificate body, and comparing the two values.

But that’s a trap! Checking just the hash value recovered from an RSA signature is not the same thing as verifying the signature. It’s true that the only thing that binds the signature to the certificate contents is the hash value. But you need to check every bit of the decoded signature to verify it. The redundant 0xFF bytes don’t just pad the hash to the right place; along with all of the other bytes in the message, they assert the validity of the signature itself. The limp word “padding” does us a disservice here.

In other words, if you’re only checking 50 digits of a 200 digit number, you’re tacitly accepting any of zillions of possible numeric signatures that an attacker could send you, each of which evades your broken check while remaining totally incorrect. Even worse, they don’t need to blindly guess numbers that will work. RSA is based on straightforward numerical operations, so it’s easy to calculate a number that will fit the evil message’s SHA1 hash.

(Note to Halvar and friends: If you understand the number theory involved in calculating a perfect cube mod n, please excuse the very limited description of modular math that follows.)

RSA operations are based on repeated multiplication, with a twist. Unlike normal multiplication, once your result gets bigger than some value (the modulus), it wraps, like an odometer on a beat-up Nova. A lot of the security in RSA depends on nobody being able to tell if your car has 35, 135, or 935 thousand miles on its very large odometer.

With a public exponent of 3, the RSA part of signature verification is:

 result = s ^ 3 mod n

or, said differently:

 result = s * s * s mod n

Remember that multiplying two numbers creates a result that can be up to twice as big. So, if you multiply two 32-bit numbers, you’ll need up to 64 bits to store the result. Each successive multiply “grows” the result to the left, and, when it hits the left edge of the odometer, it wraps back around. With proper, verified padding, we’re confident that those multiplies “wrap” many times, since the signature is close to the same size as the modulus. This makes “guess-the-odometer attacks” very hard.

But what if an attacker can give you “small” signature; say, 1/3 the size of the modulus?

Now those three multiplies look like this:

Whoops! The attacker can choose the left-hand digits of your result.

Conveniently for the attacker, if the message is padded with 0xFF’s, and you don’t check the number of 0xFF’s, the attacker can shrink the signature they provide you and let your multiplies move whatever hash they want to the correct position. They just decrease the number of 0xFF bytes. Pitiful humans! Your clever parser has betrayed you, helpfully delivering the attacker’s hash for comparison.

This was one bug in OpenSSL.

This pitfall has been known for over 20 years. For any system that verifies less than 1/3 of the bits in a block, de Jonge and Chaum published attacks in 1985 that allow an attacker to forge signatures by manipulating the remaining bits. Since then, an arms race has ensued with subsequent papers from Misarsky (1997), Girault and Misarsky (1997), and Brier et al (2001) shrinking the number of bytes an attacker needs to control to forge signatures. At present, a verifier that checks less than 2/3 of the bits in a message block — for instance, validating fewer than 1365 bits (171 bytes) of a 2048 bit signature — is vulnerable to an attacker who chooses the value of the remaining 85 bytes.

With the number of bits an attacker needs to manipulate decreasing steadily, there is absolutely no reason not to just check all of them. Code that doesn’t validate every bit of an RSA signature is playing with fire.

In our next post, we’ll explain why this is one case where the simplest solution is also the most secure. Later, we’ll discuss the varying ways this attack can be put into practice.

Citations:

• W. de Jonge and D. Chaum. “Attacks on some RSA signatures,” Advances in Cryptology Crypto ‘85, LNCS vol. 218, Springer-Verlag, pp. 18-27.

• J.-F. Misarsky, “A multiplicative attack using LLL algorithm on RSA signatures with redundancy,” Proceedings of Crypto ‘97, LNCS vol. 1294, Springer-Verlag, pp. 221-234.

• M. Girault and J.-F. Misarsky, “Selective forgery of RSA signatures using redundancy,” Proceedings of Eurocrypt ‘97, LNCS vol. 1233, Springer-Verlag, 1997, pp. 495-507.

• E. Brier, C. Clavier, J.-S. Coron, and D. Naccache, “Cryptanalysis of RSA Signatures with Fixed-Pattern Padding,” Proceedings of Crypto 2001, LNCS vol. 2139, Springer-Verlag, pp. 433-439.

Next: Bad Patches»