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

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

«Previous: Eight Other Attacks | Top | Next: Conclusion»

Remember what we said in part 2 of this series? Public key crypto algorithms are based on number theory. Think of the words “number theory” as code for “fails catastrophically in the face of implementation errors”. The recent RSA signature vulnerabilities negated the security promises RSA sets up for SSL; that’s a terrible flaw. But we can survey publicly-deployed implementations of other cryptosystems and find significant numbers of similar attacks. For example:

Elliptic Curve-based Systems (ECDH, ECDSA)

Elliptic Curve (EC) cryptosystems are public key schemes based on equations originally designed to measure ellipses. The underlying mathematical problems involved in EC are significantly harder to solve than those used in multiplicative-group systems like RSA; this means EC cryptosystems can often achieve security with much smaller key sizes, making them popular.

To set up EC cryptography, parties need to agree on “domain parameters” (the finite field, curve, point, etc). When one party accepts another’s generated parameters, they need to be validated carefully; otherwise an attacker can forge signatures or obtain your private key.

Do you work in security? You’re more likely to be called on to evaluate an EC implementation than to write one yourself, especially because you’re probably too smart to fall into the trap of writing your own crypto. So, next time you come across someone else’s vanity EC library, look for missing steps in this sequence:

• Check that q is a prime power

• Check that E is an elliptic curve over Fq with cryptographic restrictions (order of #E(Fq) = kr, where r is prime)

• Check that G is a point on E(Fq) of order r

(source: Kaliski’s EC summary)

Secure Remote Passwords

The SRP protocol is a “zero-knowledge” password proof scheme that uses math similar to Diffie Hellman to allow two parties to prove they share a password. The draw is that neither side needs to share anything other than information derived from the password (like pre-exchanged keys, or a trusted mediator).

Like other public key cryptosystems (SRP is basically a public key scheme that generates ephemeral keys), SRP parties must agree on a few published parameters (prime numbers, a generator, etc). As with EC, when Bob receives parameters apparently generated by Alice, Bob needs to verify them. The specification gives explicit step-by-step procedures for doing this (a plus for the SRP spec). But not all implementations perform all those steps, meaning an attacker can log in as anyone without knowing your passwords.

The following is a list of constraint checks that must be performed by both sides to ensure the security of the SRP protocol. Client testing of n and g is only necessary if these values are transmitted and not embedded or prearranged. n is a large safe prime (client).

• g is a primitive root of GF(n) (client)

  Assuming the factorization of n - 1 is known, the algorithm described in [16] for testing generators can be used to verify g. If n is a safe prime, this test is particularly easy and fast.

• A > 0 (server) (mod n)

  This prevents the server’s session key from being forced to a known value, namely zero.

• B > 0 (client) (mod n!)

  This check prevents a dictionary attack on the password from a masquerading host.

• a, b > log[g] n

  The computations of g^a and g^b in GF(n) must “wrap around” to prevent an attacker from taking the algebraic logarithm of g^a to recover a. The probability of this happening is infinitesimal (less than 2^-1014 for 1024-bit n), but the check is trivial.

The client must ensure that n is large enough to resist attack; see Section 4.4.1 for recommendations. Using a probabilistic primality tester, the client should also ensure that both n and (n - 1) / 2 are prime.

Diffie Hellman

DH is a workhorse of modern cryptosystems, and it’s so simple that it’s well-captured by a few paragraphs in Wikipedia. But like our other examples, it’s based on number theory and parameter negotiation, and, as a result, the implementors of Tor broke it: if the two sides of a DH negotiation don’t check the exponents they receive, a man-in-the-middle can spoof handshake messages and predict the resulting key.

An implementation has to check for the following bad values to avoid attacks, including “small subgroup confinement”.

• Exponent of 0, p, 2p, …

• Exponent of 1, p + 1, 2p + 1, …

• Exponent of -1 (p - 1, 2p - 1, …)

• Resulting shared secret Z is not confined to a small subgroup. Check that (Z^j) mod p != 1, where j = (p-1)/q

• Or, p must be a “safe prime” (p = 2q + 1 where q is also prime)

Careful: these lists aren’t complete. It’d take pages to explain how to perform the checks correctly; don’t depend on a blog post to determine the absence of a flaw. But there is definitely some low-hanging fruit out there that doesn’t even do basic checking, and hopefully we’ve just helped you pick them.

We also wanted to show that the problem is much bigger than RSA and certainly not limited to low-exponent RSA. In all cryptosystems, especially public key systems, any variability an attacker can influence can lead to catastrophic failure. The verification of parameters needs to be performed via a simple, easy-to-audit method that can be shown to be complete. And if you’re testing a product that depends on a public key algorithm for its security, you can often glean a catastrophic finding by looking at these areas of the implementation.

Next: Conclusion»