The summer of OAEP
lcs Mixmaster Remailer
mix at anon.lcs.mit.edu
Wed Jun 13 13:40:07 EDT 2001
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 at wasabisystems.com
More information about the cryptography
mailing list