RSA Signature Forgery Explained (with Nate Lawson) - Part II
Thomas Ptacek | September 13th, 2006 | Filed Under: Defenses, Guests, New Findings
«Previous: Introduction | Top | Next: The Attack»
What happened here?
Cryptography is hard to get right. Throw out every existing definition of the word “hard”. Avoiding buffer overflows in C is “easy”. Yet even for this easy problem, the very best programmers don’t produce bulletproof code. Cryptography is like that, but much worse. There’s a manageable few assumptions that the C runtime depends on for security, such as that memory writes will stay within bounds and not corrupt the program’s metadata. In contrast, crypto depends on a lot of assumptions. As with overflows in C code, where those assumptions are violated, exploitability is a “when”, not an “if”.
Public key cryptography is harder still. It’s based on number theory, which is another way to say “straightforward mathematical relationships”. In the real world, safe implementation of public key crypto is guarded by a myriad of assumptions and constraints. These constraints can be violated by tiny, innocuous-looking implementation flaws. When that happens, problems that appear to be unsolvable within the lifetime of the Sun using more computers than there are atoms in the solar system can be transformed into problems that can be solved with a pencil and a paper.
Understand what we just said. The RSA signature attack is an example of that kind of an attack, but RSA is not the only cryptosystem that has these properties. The same kinds of tiny bugs can create catastrophes for DSA, Elliptic-Curve DSA, SRP, Diffie-Hellman, and so on.
In comparing secure programming to secure public key crypto, think of the security of a piece of code as an explosive device, with little wires for every assumption the code relies on. Think of the mess of wires that are involved in securing, say, a device driver (for memory handling, concurrency, etc.) Now think of the analogous bomb for public key crypto code. Start with 10 times as many little wires. Multiply by the number of different cryptographic algorithms you use. Then by the number of modes they’re used in, and by the number of applications that use the algorithm. Short out any of those wires, or jiggle them out of place, and you’re dead.
That’s the scale of the problem implementers face getting public-key cryptography right. Next, we’ll analyze the original flaw and various problems with the attempts to fix it as they are still evolving.
Halvar
September 13th, 2006 4:31 pmSilly question, but couldn’t the entire thing have been avoided had we
a) switched to OAEP ?
b) implemented OAEP correctly ?
c) refused to trust anyone who uses a low exponent ?
At least, if we trust the random oracle model, we have something relatively strong in our hands (OAEP). I am consistently surprised that the migration away from other, clearly weaker message padding schemes isn’t happening more quickly.
Cheers,
Halvar
tyme
September 13th, 2006 5:07 pmI’d love to hear an explanation for why the people in charge of the TLS standard haven’t added any ciphersuites with alternative hashes.
They add a screwball symmetric algorithm like SEED, yet they can’t be bothered to add suites that use SHA-256, SHA-512, Whirlpool, or Tiger, even when there was speculation that SHA-1 would be next to fall when MD5 attacks were announced a couple years ago?
Thomas Ptacek
September 13th, 2006 7:37 pmMD5 makes this attack very slightly easier. SHA256 would make it slightly harder (you’d have a harder time sliding a bogus hash into a 1024 bit modulus). But all the engineering you could do with hash functions are for nothing if you don’t get signature verification right.
Matasano Chargen » RSA Signature Forgery Explained (with Nate Lawson) - Part I
October 20th, 2006 10:32 am[…] [«Previous: TOC][] [Top][] Next: The Attack» […]
Matasano Chargen » RSA Signature Forgery Explained (with Nate Lawson) - Part III
October 20th, 2006 1:19 pm[…] «Previous: Why Public Key Is Hard | [Top][] | Next: Bad Patches» […]
Matasano Chargen » RSA Signature Forgery Explained (with Nate Lawson) - Part VI
October 20th, 2006 1:23 pm[…] 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: […]
Leave a reply