Why RSA encryption padding is critical (cool RSA implementation flaw)

http://rdist.root.org/2009/10/06/why-rsa-encryption-padding-is-critical/

by tptacek • 17 years ago

22 9 17 years ago

rdist.root.org

sid03• 17 years ago

Hell, even if you do send just one message and do pad it, but the padding sucks (i.e. is known to the adversary) and e is small, you can use Coppersmith's theorem to break the encryption.

This is really just reason number 242151205 why you shouldn't attempt to build your own crypto system.

cperciva• 17 years ago

This is really just reason number 242151205 why you shouldn't attempt to build your own crypto system.

No, it's reason 242151205 why you should read the established standards. RFC 3447 says "use RSA-OAEP for encryption and RSA-PSS for signing".

If you have security flaws due to doing something non-standard in any field other than cryptography, people will say you're an idiot. Why does cryptography get a free pass with "oh well, we all know that stuff's hard"?

NateLawson2• 17 years ago

I don't think that's correct. Coppersmith's attack requires at least 2 messages. You're talking about the paper "Low-Exponent RSA with Related Messages (1996)" right?

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.6...

sid03• 17 years ago

No... what I'm referring to is given in http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf -- basically using LLL to bring the numbers down to below the RSA modulo. (I know it works, because I wrote Mathematica code to implement it. :) )

jsc• 17 years ago

A generalization of the attack (and many more attacks) is given in: http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

miloshh• 17 years ago

The attack seems to be based on the arbitrary assumption that e=3. Isn't e always a huge number in practice?

sid03• 17 years ago

Yes. 65537 is commonly used.

NateLawson2• 17 years ago

The lower your public exponent in RSA, the faster you can verify signatures. So e=3 is still used quite often in embedded applications. It can be secure if used properly, but for most cases, it is safer to use 65537 as that can protect you from actual exploitation even if you have a variety of implementation bugs.

gcb• 17 years ago

slightly OT, but another good anecdote about buggy RSA implementation

http://media.ccc.de/browse/congress/2008/25c3-2799-en-consol...

*edit: it's about Team Tweezer exploiting the RSA implementation on nintendo's Wii to run unsigned code.

Why RSA encryption padding is critical (cool RSA implementation flaw)

Related Stories