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

Thomas Ptacek | September 25th, 2006 | Filed Under: Defenses, Guests, Uncategorized

«Previous: Bad Patches | Top | Next: Attacks on Other Algorithms»

More Implementation Flaws

There is more than one way to screw up RSA padding checks, especially if your approach is to “parse” for bad formatting (instead of comparing against known-good formatting). Here are a few of them:

• The “Skip To The Zero” bug, in which you ignore the value of every byte leading up to the 0x00 terminator in the padding. Vulnerable code might look like this:

  while (*p != 0)
         p++;
  

  Every one of those 0xFF bytes counts. If they aren’t 0xFF, it’s not a valid signature. Each byte not checked can take 255 other values (that’s 216 variable bytes for an attacker, assuming a 2048 bit modulus).

• The “Ignore The Hash OID” bug, in which you rely on the hash you think the signature uses, but don’t check that the ASN.1 OID in the signature m-block matches. This is like the 0xFF problem, but harder: before you just needed to make sure all the bytes were 0xFF, but once you get to the ASN.1 data you have to know what to expect. If you don’t verify these bytes (preferably by generating a known-good m-block), an attacker can use the OID field to gain as many as 15 more bytes of variability.

• The “Assume The ASN.1 Common Case” bug, in which you rely on the assumption that the ASN.1 fields in the m-block are the typical values. PKCS#1 allows lots of variations, including a “parameters” field, usually “null”, that follows the hash OID. If you don’t check all the ASN.1 data, an attacker can specify any bytes within an ASN.1 field (up to its maximum allowed length). OpenSSL and GNU TLS were vulnerable to this for the hash “parameters” field.

• The “Misaligned Padding” bug, in which you incorrectly align the padding and the result of the RSA private key operation. Your modulus doesn’t have to be a multiple of 8 bits long (unless there is some external constraint)! If it isn’t, your verifier might miss padding bits. You can’t always force moduli to be an even number of bytes; if you need to support variably-sized moduli, you need to test this.

• The “Cheating Backwards Verifier” bug, in which you get clever and simply compare the hash bytes backwards to the last bytes of the signature, and then stop. Without verifying the rest of the signature.

• The “Overlong Digest” bug, in which you slurp out all the bytes of the digest, but only use the first 20 (or 16 for MD5) to compare; the trailing bytes, described by the ASN.1 metadata, are exploitable by an attacker.

• The “Distinguishing Error Oracle” bug, in which you emit a telltale error message when padding is incorrect. (Note: this attack normally applies only to RSA encryption, not signature verification, but can occur in signing systems too).

• An attacker can always choose an arbitrary number of bytes of the hash by varying the message. For example, by adding a counter field to the message to be signed and by performing up to 2^40 hashes (which could take as little as 52 CPU days, a pittance), an attacker can find one with the rightmost 5 bytes all zero (or leftmost or some other pattern).

The last case is impossible to prevent since an attacker can choose arbitrary messages to be signed. Any number of X.509 certificate fields can be abused to vary the message (signing date, expiration date, serial number, issuer and subject names, etc.). So it’s not a parsing bug, per se. But it proves our point. You need to rigidly verify every bit you could possibly know the correct value for, because some of the bits in the m-block are impossible to predict.

Since there are so many possible ways to fail, the best solution is not to try to verify the padding is correct but just to compare it to a known good value. We said this before, but it can’t be said enough.

Next: Attacks on Other Algorithms»