Re: Random oracles



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?
.



Relevant Pages

  • Re: Hashing of short fixed length messages
    ... You actually have 55 bytes of useful payload before MD5 requires a 2nd ... to present a traditional hash interface since the ... The input itself is a hash too, so I can ignore related key attack, ... to a speed-up factor of two, but I don't think it's secure. ...
    (sci.crypt)
  • Re: How good an encryption algorithm is this?
    ... Actually it's vitally important that the salt is different every time. ... but a one-way hash of the password). ... >>> attack (using my dictionary of plaintext trial passwords and the ... you need to perform this iteration only once. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: How good an encryption algorithm is this?
    ... Actually it's vitally important that the salt is different every time. ... but a one-way hash of the password). ... >>> attack (using my dictionary of plaintext trial passwords and the ... you need to perform this iteration only once. ...
    (microsoft.public.vc.language)
  • Re: Public key encryption
    ... >>messages as to break the hash algorithm. ... > it amounts to equivalence to the RSA problem. ... > anything that can forge PSS signatures can do arbitrary RSA ... > attack on weak padding is Bleichenbacher's "Million Message Attack", ...
    (sci.crypt)
  • Re: iis 6 ssl redirect initial login encrypted?
    ... encrypted using the hash of the password. ... that to the end user to encrypt, and I then return it to the IIS server. ... Yes, there is a man-in-the-middle attack on a specific auth sequence, ... authentication will somehow result in the exposure of credentials. ...
    (microsoft.public.inetserver.iis.security)