Figured this might be of interest

I figured this might be of interest. A hole in the OAEP proof has been
found, and it's been proven that the hole cannot be patched.

This information may have errors in it since I do not personally have a copy
of the Crypto 2001 list, so I am taking this second hand.

The data comes from 2 papers for Crypto 2001. One by Shoup and one by
Fujisaki, et all.

The Shoup abstract is:
The OAEP encryption scheme was introduced by Bellare and Rogaway at
Eurocrypt '94.  It converts any trapdoor permutation scheme intoa public-key
encryption scheme.  OAEP is widely believed to provide resistance against
adaptive chosen ciphertext attack.  The mainjustification 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 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.





These two papers indicate that OAEP does not offer perfect security, but
does offer very good security. It shouldn't change our decision, or at least
it shouldn't until significant review of at least Shoup's paper can be made.
                    Joe

Received on Friday, 15 June 2001 15:25:15 UTC