Bleichenbacher ’06 RSA Signature Forgery: What they assume you know

In 2006, Daniel Bleichenbacher shared a discovery in an evening session at a cryptography conference: Several implementations of RSA-based PKCS 1 v 1.5 cryptographic signature verification were fatally flawed and susceptible to signature forgery.

It is as bad as it sounds. The sad part: The flaw in the signature verification algorithm is that the signature submitted for validation is trusted too much. Any engineer worth his salt knows you should never trust user input.

This blog post is directly tied to cryptopals challenge 42 in which you are asked to exploit a still-existing weakness (or at least still-existing up to 2016 … I would hope it’s fixed now) in several RSA cryptographic signature verification implementations. But they don’t give you a lot of background on how to construct a signature in the first place. Some parts are obvious; many are not.

The algorithm

If you google this subject long enough, you’ll run into something that looks like this in lots of different places.

00 01 FF FF ... FF 00 ASN HASH GARBAGE

This format (sans GARBAGE) is outlined in RFC 2313. (Spend some time there… it will help). The signature algorithm, as outlined there, is pretty straightforward. Using the public RSA key (not the private key), follow these steps:

• Use a hashing algorithm to hash a message. SHA1 is ok, but you could use MD4, MD5, SHA256, SHA512, or whatever you want
• Encode that message in ASN.1 format following a specific encoding scheme (as outlined below)
• Pad that octet string out to the width of the RSA public modulus (aka n), starting with a byte of 00, then a byte of 01, then k bytes of FF, followed by another 00 byte, then the ASN.1 encoded octet string.
• RSA-encrypt that octet string using the public key (not the private key).

Signature verification is basically the same, but backwards:

• RSA-decrypt the submitted signature using the private key (not the public key).
• Parse the decrypted octet string, verifying and validating the padding scheme.
• Seek the beginning of the ASN.1 encoded octets.
• Using the hash algorithm specified in the ASN.1 encoded octets, hash the message submitted for signature verification.
• Compare the resulting hash with the hash included in the signature. If they match, then the signature is valid.

ASN.1 Formatting

If you’re a n00b like I was, the first questions are “What in the blazes is ASN.1?” and “How am I supposed to encode something in it?”

The answer: Don’t do it manually. There are libraries available all over the internet that make it easy. You just have to know how to use them. I used bouncy castle.

In RFC 2313, the encoding schema for the ASN.1 encoding is outlined as follows

   DigestInfo ::= SEQUENCE {
     digestAlgorithm DigestAlgorithmIdentifier,
     digest Digest }

   DigestAlgorithmIdentifier ::= AlgorithmIdentifier

   Digest ::= OCTET STRING

AltorithmIdentifier is defined in RFC 5280 (X.509) as follows.

   AlgorithmIdentifier  ::=  SEQUENCE  {
        algorithm               OBJECT IDENTIFIER,
        parameters              ANY DEFINED BY algorithm OPTIONAL  }

People the world over have written libraries to do this. Here’s a how I implemented the encoding. (It seems simple, but boiling this down to knowing which library objects to use was not obvious and took a lot of searching and reading).

The object identifier is a defined constant elsewhere in the library. It was just a matter of finding it and knowing which one to use.

    public byte[] encodeHashToAsn1SignatureFormat(final byte[] hash, final ASN1ObjectIdentifier hashAlgo) {
        ASN1Sequence s1 = new DERSequence(new ASN1Encodable[] {
                new AlgorithmIdentifier(hashAlgo, DERNull.INSTANCE),
                new DEROctetString(hash)
        });
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        s1.toASN1Primitive().encodeTo(out);
        return out.toByteArray();
    }

Small e and poor padding validation

Like I said … the fatal flaw in many RSA signature algorithms is that they trusted the submitted signature too much. Specifically, they didn’t validate the length of the signature to make sure it was as long as the RSA public modulus, and didn’t make sure that the content of the signature is right justified. That means that if you have a signature that nominally follows the signature encoding format of …

00 01 FF FF FF ... FF FF 00 ASN HASH

… then you can throw whatever you want (GARBAGE) after HASH, and the signature will still validate.

This is sort of a big deal. Recall from this explainer that RSA encryption is based on modular exponentiation. If you have a small exponent and a large modulus, you run the risk that a message might not be numerically large enough to wrap around the modulus after exponentiation. This being the case, all someone would have to do to forge a signature is come up with a figure that when exponentiated follows the format:

00 01 FF FF ... FF FF 00 ASN HASH GARBAGE

This is hard with larger exponents. It’s almost trivial when e=3. Why? All you have to do is build a message, take the cube root of that figure, and round up.

Why round up? Let’s be honest … you’re probably not going to be crafting a message that when translated into a large integer is a perfect cube. Computers are good at lots of things. Computing roots and computing prime factors of large figures are not among those things. But you don’t need a perfect cube anyway because you don’t care what comes after the HASH, right?

If you take a cube root of your crafted message and round up, the least significant (read: the right-most) bytes will be different than where you started, but the most significant (read: the left-most) bytes will stay the same. If you’re dealing with a padding validator that doesn’t validate that HASH is right-justified, you’ve won.

Here’s my implementation of an RSA signature “forger.” Pretty simple, pretty scary that it works so well.

The alternative, and why I didn’t pursue it

Hal Finney, in his original summary of this exploit, detailed that signatures could also be forged by treating everything before GARBAGE as if it was the result of (A – B)³. He loosely outlined a way that a message could crafted such that when cubed would follow the same basic pattern.

I saw this as needlessly complex. And, I already had a method written to find cube roots (and other roots) of large integers. I didn’t see a reason to bang my head against the wall when I was already 90% of the way there.

However, this is definitely a problem to revisit in the future.

Thanks for reading! -LH