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.
Add New Comment
Viewing 3 Comments
Thanks. Your comment is awaiting approval by a moderator.
Do you already have an account? Log in and claim this comment.
Do you already have an account? Log in and claim this comment.
Do you already have an account? Log in and claim this comment.
Do you already have an account? Log in and claim this comment.
Add New Comment
Trackbacks