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

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

«Previous: The Attack | Top | Next: Eight Other Attacks»

Analysis of the patch timeline

This section works better if we tell it starting from the future and working backwards. But the future hasn’t happened yet. And we don’t know what goes on inside the various software teams. So, like ABC’s Path to 9/11, some of this episode is fictionalized for dramatic purposes. But the lessons are real.

Winter 2006

At last, the RSA cleanup work seems complete. The obvious crypto libraries, commercial applications, and hardware accelerators have swept their code, in some cases furiously rewriting it to avoid pernicious variants of the attack.

RSA implementers have a new mantra: “byte-compare against good, don’t parse for bad.” It’s not sexy, but the simplest approach for checking a signature is also the best way to eliminate variability, the source of these security flaws.

It works like this. You’re given an RSA signature S_received, of modulus size N and hash type T over the data D. You:

1. Perform an RSA public key operation on S_received, turning the signature into a message block.

2. Match the modulus N to a template based on its length (1024, 2048, 4096 bits, etc).

3. Look up the appropriate algorithm identifier for your hash algorithm T (SHA1, SHA256).

4. Hash the data D using that algorithm

5. Copy the template, algorithm identifier and hash result to a new buffer S_expected

6. Byte-compare S_received and S_expected.

7. If there is any difference, return “signature verify failed”

There are a few variations. Some RSA code lives in smart cards or small embedded computers. They only support one modulus size and one hash type. They skip steps 2 and 3. All they have to do is copy the hash result directly into a template and compare it against S_received.

How did we wind up here? The old approach added checks for bad fields in signatures. Lots of checks. For every aspect of the padding or the digest information that could possibly go wrong. It was very hard to review for correctness. Like a rev1 beta PHP application deployed in the wild for the first time, no one was sure every bit was validated for every possible signature an attacker could send.

Since this approach is so simple and obviously correct, projects like Python’s tlslite, GPG, and new work from OpenSSL progenitor Eric Young already used it (at least for his 2nd time around). But it took time for the lesson to sink in for everyone else.

2006/9/18

People stopped calling the RSA signature attack the “e=3 problem”, realizing the exponent wasn’t really the problem. Calling out one instance of an implementation problem handling RSA signatures was like calling all buffers overflows “strcpy() attacks”. “e=3” wasn’t the problem. If you did RSA properly, e=3 (and higher exponents) were closely related to e=2, and e=2 is provably as secure as factoring N. If you did RSA wrong, it didn’t matter what your exponent was. For example, e=17 was also vulnerable if you used a 4096 bit modulus and the implementation only checked the SHA1 hash (or also up to 10 other bytes).

However, we have started eliminating the few e=3 root certificates. That was a good idea. There was no way we were picking up the millions of pieces of all the broken deployments, and PCs were plenty fast with e=65537 even 10 years ago. (A 33 MHz machine can do dozens of verifies per second with a 1024 bit key.)

2006/9/15

Firefox is vulnerable to the same 2 flaws in OpenSSL, although NSS is a different codebase. They took the same approach to fixing the problem as OpenSSL — check for the number of 0xFF bytes and look for a bad “parameters” field.

Opera and Konqueror, both of which used OpenSSL, also turned out to be vulnerable.

Did we mention phishing?

2006/9/6

OpenSSL backed out part of their fix today. They figured they could spot forged signature results by the way they looked — the padding would be very short. In particular, if the hash and its ASN.1 metadata added up to more than 1/3 the modulus size, then the padding must be less than 2/3 the total, suggesting hash had been shifted to the left by an attacker.

However, with a modulus of 840 bits or less, this check would reject all valid signatures also. (SHA1 OID + hash = 35 bytes * 3 = 105 bytes or 840 bits.)

A special case was added to handle this as well.

The check returned a distinct error value (“signature too small”) as opposed to a general “signature verify failed”. Believe it or not, even the specificity of your error messages can be used to break your crypto. Bleichenbacher used distinguishing error messages in 1998 as an oracle to attack Netscape’s RSA encryption. Fortunately, since this was signature verification, and not decryption, the data being handled was ostensibly “public”; nothing would be gained by an attacker knowing what part of a signature was found corrupt.

However, in embedded cryptosystems, attackers can often glitch a private key operation and from it, recover the private key. One of the defenses against this is to always check the signature with the public key before exposing it (this discards faulty results before they’re revealed to an attacker). By leaking small bits of information about that faulty computation via the signature library’s error codes, this approach may have been problematic in such embedded environments.

Since the other half of the original patch was essential and this approach of looking for bad data was fundamentally flawed, this code was backed out.

2006/9/5

In response to Bleichenbacher’s attack, OpenSSL just checked in a fix. It actually patches 2 flaws. The first is already being discussed to death on mailing lists and blogs (varying the number of 0xFF bytes). The second is just starting to be discussed as it also applied to gnutls (varying the bytes in the encoded hash algorithm type).

The patch is simple. It adds 2 more checks of the padding format:

1. Verify the number of 0xFF bytes is correct
2. Check that the optional “parameters” ASN.1 extension is either:
1. Not present
2. Set to the special value V_ASN1_NULL

Unfortunately, it’s not clear that this covers all the possible variability that a future attacker might exploit. Any amount of unchecked or variable data in the signature can potentially be leveraged by an attacker, especially as the underlying cryptanalytic attacks evolve. Also, because these patches are implemented as point-checks for specific bad cases, it’s very hard to verify that they are correct and complete.

Instead of trying to parse the potentially malicious signature, why doesn’t everyone just generate a template of what the signature should look like and byte-compare it?

Next: Eight Other Attacks»