Recent Results on OAEP Security
(Throughout this page, all security considerations are within the random oracle model.)
Recent results have helpfully clarified the security properties of the OAEP encoding method. The background is as follows. In 1994, Bellare and Rogaway  introduced a security concept that they denoted plaintext awareness (PA94). They proved that if an encryption primitive (e.g., RSAEP) is hard to invert without the private key, then the corresponding OAEP-based encryption scheme is plaintext-aware, meaning roughly that an adversary cannot produce a valid ciphertext without actually "knowing" the underlying plaintext. Plaintext awareness of an encryption scheme is closely related to the resistance of the scheme against chosen ciphertext attacks. In such attacks, an adversary is given the opportunity to send queries to an oracle simulating the decryption primitive. Using the results of these queries, the adversary attempts to decrypt a challenge ciphertext.
However, there are two flavors of chosen ciphertext attacks, and PA94 implies security against only one of them. The difference relies on what the adversary is allowed to do after she is given the challenge ciphertext. The indifferent attack scenario (denoted CCA1) does not admit any queries to the decryption oracle after the adversary is given the challenge ciphertext, whereas the adaptive scenario (denoted CCA2) does (except that the decryption oracle refuses to decrypt the challenge ciphertext once it is published). In 1998, Bellare and Rogaway, together with Desai and Pointcheval , came up with a new, stronger notion of plaintext awareness (PA98) that does imply security against CCA2.
To summarize, there have been two potential sources for misconception: that PA94 and PA98 are equivalent concepts; or that CCA1 and CCA2 are equivalent concepts. Either assumption leads to the conclusion that the Bellare-Rogaway paper implies security of OAEP against CCA2, which it does not. OAEP has never been proven secure against CCA2; in fact, Victor Shoup  ingeniously demonstrated recently that such a proof does not exist in the general case. Put briefly, Shoup showed that an adversary in the CCA2 scenario who knows how to partially invert the encryption primitive but does not know how to invert it completely may well be able to break the scheme. For example, one may imagine an attacker who is able to break RSAEP-OAEP if she is able to recover all but the first 20 bytes of an integer encrypted with RSAEP. Such an attacker does not need to be able to fully invert RSAEP, because she does not use the first 20 octets in her attack.
Still, RSAEP-OAEP is secure against CCA2, which was proved by Fujisaki, Okamoto, Pointcheval, and Stern  shortly after the announcement of Shoups result. Using clever lattice reduction techniques, they managed to show how to invert RSAEP completely given a sufficiently large part of the pre-image. This observation, combined with a proof that OAEP is secure against CCA2 if the underlying encryption primitive is hard to partially invert, fills the gap between what Bellare and Rogaway proved about RSAEP-OAEP and what some may have believed that they proved. Somewhat paradoxically, we are hence saved by an ostensible weakness in RSAEP (i.e., the whole inverse can be deduced from parts of it). As a consequence, it makes little sense replacing OAEP with a "more secure" encoding method, because if a CCA2 adversary is able to break RSAEP-OAEP, then she will be able to break RSAEP equipped with any encoding method (if maybe slightly less efficiently). For encryption primitives different from RSAEP, however, it might be worthwhile considering a stronger encoding method such as OAEP+ suggested by Shoup .
- M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among Notions of Security for Public-Key Encryption Schemes. In Advances in Cryptology Crypto94, pp. 26-45. Springer Verlag, 1994.
- M. Bellare and P. Rogaway. Optimal Asymmetric Encryption How to Encrypt with RSA. In Advances in Cryptology Eurocrypt 94, pp. 92-111. Springer Verlag, 1994.
- E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern. RSA-OAEP Is Still Alive! Preprint, November 2000. Available from http://eprint.iacr.org/.
- V. Shoup. OAEP Reconsidered. Preprint, November 2000. Available from http://eprint.iacr.org/.