Re: Random oracles
- From: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
- Date: Mon, 22 Jan 2007 22:46:22 +0000 (UTC)
Kristian Gjøsteen wrote:
I'm slightly confused. The idea is that we get (by a miracle, say)
an efficient adversary against RSA-OAEP instantiated with (say) some
SHA-1-based hash thingy. How likely is it that we can turn that attacker
into something that breaks RSA? Of course, if the attacker doesn't care
about the hash function, then the random-oracle-reduction just works. But
what if the attacker does use special properties of the SHA-1-based hash
thingy? Even if you can isolate the hash computations, you cannot just
replace them by something else and expect the attacker to keep on working.
If the attack uses some special properties of the SHA-1 hash, then SHA-1
is broken. Note that no one is claiming that "if the RSA problem is hard,
then RSA-OAEP is secure". At best, we'd like to hope that "if the RSA
problem is hard and SHA-1 is secure, then hopefully RSA-OAEP is secure".
If someone finds an attack on RSA-OAEP, the most we can hope for is that
it can be translated into either an attack on RSA or an attack on SHA-1.
(I'm aware that my statements above aren't very carefully worded, and
if you push at the details of the above claims, it's a little messier
than I'm giving credit for. But my ultimate point still stands: you
have no right to expect that an attack on RSA-OAEP will necessarily be
translateable into an attack on RSA.)
What if some very special property
of the hash function is found that allows an attack?
Then the hash is insecure. The most one can hope for is for RSA-OAEP
to be secure assuming that both the RSA problem is hard and that
the underlying hash function is secure. Of course, if either of
those assumptions turn out to be inaccurate, then you have no basis
for expecting any kind of security out of RSA-OAEP. That's not the
interesting part of the random oracle debate. The interesting part of
the random oracle debate is: is it possible that someone finds an attack
on RSA-OAEP that does not translate into an attack on the RSA problem
and that does not translate into an attack on the hash function?
- Prev by Date: Re: Random oracles
- Next by Date: Re: Password Psychology
- Previous by thread: Re: Random oracles
- Next by thread: Re: Random oracles