---------- Forwarded message ---------- Date: 13 Jun 2001 17:40:07 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> To: cryptography@wasabisystems.com Subject: The summer of OAEP These are some of the papers to be presented at Crypto 2001 in August[1]: A Chosen Ciphertext Attack On RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized In PKCS #1 James Manger OAEP Reconsidered Victor Shoup RSA--OAEP is Secure Under the RSA Assumption Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval and Jacques Stern Simplified OAEP for the RSA and Rabin Functions Dan Boneh Shoup's abstract[2] reads: The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme into a public-key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way. This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard "black box" security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general OAEP scheme is insecure. The paper also presents a new scheme OAEP+ along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP, and even has a tighter security reduction. It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure. They simply undermine the original justification for its security. In fact, it turns out - essentially by accident, rather than by design - that RSA-OAEP is secure in the random oracle model; however this fact relies on special algebraic properties of the RSA function, and not on the security of the general OAEP scheme. The Fujisaki, et al abstract[3] reads: Recently Victor Shoup noted that there is a gap in the widely-believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying trapdoor permutation. This paper establishes another result on the security of OAEP. It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to its (full-domain) one-wayness, it follows that the security of RSA-OAEP can actually be proven under the sole RSA assumption, although the reduction is not tight. [1] http://www.iacr.org/conferences/c2001/accept.html [2] http://shoup.net/papers/oaep.ps.Z [3] http://cgi.di.ens.fr/cgi-bin/pointche/papers.html?FuOkPoSt00 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com -- ____________________________________________________________________ "...where annual election ends, tyranny begins;" Thomas Jefferson & Samuel Adams The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------