In our current system we use an encryption solution based on RSA with OAEP padding. Key size is optional but default 2048. What is the general strength of RSA with OAEP? Are there know attacks that can break it, their complexity? Are people using it and relying on it as secure enough?



OAEP is likely to be secure as long as the underlying primitives - RSA using modular exponentiation and the hash function to generate the padding - are considered secure. So the OAEP padding in itself should not pose any problems.

That said, we don't know if your protocol is secure, nor if the RSA / OAEP implementation is secure. It could for instance be vulnerable to timing or other side channel attacks.

Currently it seems that OAEP is your best bet for performing RSA encryption. Yes, OAEP is standardized and well used. RSA encryption with PKCS#1 v1.5 padding is still used, arguably too much.

As the RFC encapsulating the PKCS#1 standard specifies:

In addition, the running time for Inv is approximately t^2, where t is the running time of the adversary. The consequence is that we cannot exclude the possibility that attacking RSAES-OAEP is considerably easier than inverting RSA for concrete parameters. Still, the existence of a security proof provides some assurance that the RSAES-OAEP construction is sounder than ad hoc constructions such as RSAES-PKCS1-v1_5.

Hybrid encryption schemes based on the RSA-KEM key encapsulation paradigm offer tight proofs of security directly applicable to concrete parameters; see [30] for discussion. Future versions of PKCS #1 may specify schemes based on this paradigm.

This was based on the following:

E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern. RSA-OAEP is Secure under the RSA Assumption. In J. Kilian, editor, Advances in Cryptology - Crypto 2001, volume 2139 of Lecture Notes in Computer Science, pp. 260 - 274. Springer Verlag, 2001.

As specified in the RFC, RSA-KEM could also be an option. RSA-KEM couples RSA encryption with a (Key Based) Key Derivation Function and symmetric encryption. RSA-KEM may be easier to implement securely. Not many libraries offer direct support for RSA-KEM though (or KDF's for that matter) and it will require some overhead.

  • $\begingroup$ You could also mention that RSA-KEM is often a better alternative than RSA-OAEP (simpler, better security guarantee). $\endgroup$ – K.G. Jan 11 '15 at 10:05
  • $\begingroup$ @K.G. Although I think "better security guarantee" could be a bit subjective, I do like the idea behind RSA-KEM. It depends a bit if it is a good alternative; there isn't that much support for it so it should really only be used by experts in my opinion. $\endgroup$ – Maarten Bodewes Jan 11 '15 at 10:49
  • $\begingroup$ For purely asymmetric encryption we use libcrypto with RSA and EME-OEAP as per PKCS #1 v2.0. For transmitting larger data we use this for encrypting an AES-256 session key, established after an SSH type handshake with certificate checking. While my implementation itself may be insecure, or that of RSA or OAEP, my question related to know attacks or weaknesses against them. (I know about the textbook RSA weakness). $\endgroup$ – Andy Jan 11 '15 at 23:23
  • $\begingroup$ There are many weaknesses on textbook RSA (still incomplete), not just one. Updated answer, warning: it's a bit less direct by not stating that OAEP is secure, that was probably somewhat overstated. $\endgroup$ – Maarten Bodewes Jan 12 '15 at 16:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.