Halvar Flake and Nate Lawson on Alternative Padding Schemes
Nate | September 13th, 2006 | Filed Under: Defenses, Guests, Uncategorized
Halvar Flake asks,
Silly 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.
OAEP is for encryption, not signing/verification. You probably mean PSS?
Although you didn’t suggest this, I want to take this opportunity to point out that in signature verification, nondeterministic padding would be the worst thing to have since the whole point is that the recipient needs to be able to verify it. Replacing the 0xFF’s with random bytes would be a bad idea.
So what about using a random seed, but with a one-way function so the attacker can’t exactly choose the resultant, deterministic but masked message? This is how PSS works. The proof that RSA-PSS is theoretically secure is attractive, whereas nothing can be proven about PKCS#1v1.5 constant padding. However, I’m not sure if that’s balanced out by the cost of changing existing implementations and the possibility of implementation flaws since it’s more complex than fixed padding. Similar to DNSSEC, PSS needs to be supported by nearly all nodes in a network before it has value.
Regarding low exponent RSA (e=2, e=3), it is just as secure as higher exponent RSA if implemented properly. It also has nice performance benefits in the embedded arena. However, it is more “fragile” if not implemented properly and PCs are fast enough the past 10 years that no CA should use low exponents for a root cert.
Adam Morrison
September 14th, 2006 1:58 ame=2 is not a valid RSA exponent, since it’s not coprime to (p-1)(q-1).
Nate
September 14th, 2006 10:29 amNo. e=2 is Rabin, a variant of RSA.
http://www.x5.net/faqs/crypto/q37.html
sargon
September 14th, 2006 1:56 pmAnd here…
http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-212.pdf
Adam Morrison
September 14th, 2006 2:19 pmYeah, Rabin is a variant of RSA; it’s not RSA.
It’s not RSA, because the signing algorithm is totally different.
It’s not RSA, because PKCS#1 says so [PKCS#1 v2.1, sec 3.1].
It’s not RSA, because if you try using e=2 in any decent RSA implementation, you won’t get past the key generation phase, and things will break horribly even if you do.
You just spent an entire blog post explaining how cryptography is hard to get right, and how the minute details of the implementation matter. Isn’t it also important to know which algorithm is being used?
Thomas Ptacek
September 14th, 2006 2:37 pmI think we can all easily reach a consensus that Rabin keys are “NOT” PKCS#1 v2.0 or above.
Is there any way to have a conversation that doesn’t involve us delving into the definitions of what “variant” means, or questioning the legitimacy of various sources (even I can cite credible sources that say e=2 is RSA — for instance, Ferguson and Schneier, p 231, discussing how to choose the public exponent for RSA)?
I’m also going to call you on comparing a blog post to an implementation of RSA.
You seem sharp. What are your technical critiques on the posts so far?
Nate
September 14th, 2006 3:02 pm1a. Rabin uses a small exponent (e=2)
1b. RSA can use e=3
2a. Rabin security is based on the difficulty of factoring N (p*q)
2b. RSA, ditto
3a. Rabin requires special formatting and redundancy checking of the result (i.e. that M is a quadratic residue mod N)
3b. RSA requires special formatting and redundancy checking of the result (i.e. PKCS)
In refuting the argument that small exponents in RSA are the cause of the problem (not an implementation flaw), it’s perfectly legitimate to include Rabin as a counter example.
The lesson remains: proper redundancy checking is vital to security in public key crypto, no matter what the public exponent. I hope you can agree.
Adam Morrison
September 16th, 2006 3:01 amI agree with everything you said, except the reference to Rabin’s system as “low exponent RSA”, which is wrong both from a technical and historical perspective.
The details we already mentioned, plus a paper or two, affirm this assertion. If e=2 were to RSA as e=3 is, there’d be nothing to debate.
Even Ferguson and Schneier, in that footnote you cited, allude to these differences (lthough arguably too mildly).
I just thought that, seeing as how the series started by explaining how the little details matter, it’s important not to gloss over the difference between RSA and Rabin.
Adam Morrison
September 16th, 2006 3:02 amI agree with everything you said, except the reference to Rabin’s system as “low exponent RSA”, which is wrong both from a technical and historical perspective.
The details we already mentioned, plus a paper or two, affirm this assertion. If e=2 were to RSA as e=3 is, there’d be nothing to debate.
Even Ferguson and Schneier, in that footnote you cited, allude to these differences (although arguably too mildly).
I just thought that, seeing as how the series started by explaining how the little details matter, it’s important not to gloss over the difference between RSA and Rabin.
Leave a reply