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 RSAOAEP instantiated with (say) some
SHA1based 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 randomoraclereduction just works. But
what if the attacker does use special properties of the SHA1based 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 SHA1 hash, then SHA1
is broken. Note that no one is claiming that "if the RSA problem is hard,
then RSAOAEP is secure". At best, we'd like to hope that "if the RSA
problem is hard and SHA1 is secure, then hopefully RSAOAEP is secure".
If someone finds an attack on RSAOAEP, the most we can hope for is that
it can be translated into either an attack on RSA or an attack on SHA1.
(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 RSAOAEP 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 RSAOAEP
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 RSAOAEP. 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 RSAOAEP that does not translate into an attack on the RSA problem
and that does not translate into an attack on the hash function?
.
 FollowUps:
 Re: Random oracles
 From: Peter van Liesdonk
 Re: Random oracles
 From: Kristian Gjøsteen
 Re: Random oracles
 References:
 Random oracles
 From: Peter van Liesdonk
 Re: Random oracles
 From: Kristian Gjøsteen
 Re: Random oracles
 From: David Wagner
 Re: Random oracles
 From: Kristian Gjøsteen
 Random oracles
 Prev by Date: Re: Random oracles
 Next by Date: Re: Password Psychology
 Previous by thread: Re: Random oracles
 Next by thread: Re: Random oracles
 Index(es):
Relevant Pages
