Prev: SHA-3 Ouch!
Next: now, you need to encrypt a test .pdf file, what better than the original RSA paper?
From: amzoti on 28 May 2010 18:16
On May 28, 12:10 pm, Kristian Gjøsteen <kristiag+n...(a)math.ntnu.no>
wrote:
> rossum  <rossu...(a)coldmail.com> wrote:
> >This could have quite an impact on the SHA-3 competition:
>
> >(http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-....)
>
> Why?
>
> --
> Kristian Gjøsteen

Perhaps it would disqualify BLAKE, Hamsi, SHAvite-3 and Skein and that
would be huge.

If the paper is correct - I can't see why that wouldn't be the case in
the 2 minutes I spent reviewing it.

So rossum makes a good point - and I surmise that that is what he is
implying.

~A
From: Kristian Gj�steen on 29 May 2010 01:29
amzoti <amzoti(a)gmail.com> wrote:
>On May 28, 12:10�pm, Kristian Gj�steen <kristiag+n...(a)math.ntnu.no>
>wrote:
>> rossum �<rossu...(a)coldmail.com> wrote:
>> >This could have quite an impact on the SHA-3 competition:
>>
>> >(http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-...)
>>
>> Why?
>
>Perhaps it would disqualify BLAKE, Hamsi, SHAvite-3 and Skein and that
>would be huge.

Disqualifying those hash functions would be huge, yes.

>If the paper is correct - I can't see why that wouldn't be the case in
>the 2 minutes I spent reviewing it.

I expect the paper's results to be correct.

But I don't see why knowing that a hash function has a smaller image
than a random function should disqualify that hash function, even from
random oracle proofs.

Therefore: Why?

--
Kristian Gj�steen
From: rossum on 29 May 2010 08:45
On Sat, 29 May 2010 05:29:32 +0000 (UTC), Kristian Gjøsteen
<kristiag+news(a)math.ntnu.no> wrote:

>amzoti <amzoti(a)gmail.com> wrote:
>>On May 28, 12:100m, Kristian Gj?n <kristiag+n...(a)math.ntnu.no>
>>wrote:
>>> rossum <rossu...(a)coldmail.com> wrote:
>>> >This could have quite an impact on the SHA-3 competition:
>>>
>>> >(http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-...)
>>>
>>> Why?
>>
>>Perhaps it would disqualify BLAKE, Hamsi, SHAvite-3 and Skein and that
>>would be huge.
>
>Disqualifying those hash functions would be huge, yes.
>
>>If the paper is correct - I can't see why that wouldn't be the case in
>>the 2 minutes I spent reviewing it.
>
>I expect the paper's results to be correct.
>
>But I don't see why knowing that a hash function has a smaller image
>than a random function should disqualify that hash function, even from
>random oracle proofs.
>
>Therefore: Why?
As I read it the narrow-pipe hash functions fail to be 'close enough'
to random oracles for certain inputs. There is a large subset of
outputs that cannot be reached from those inputs, for instance the
paper indicates that about 53% of possible outputs are unreachable for
those particular inputs when using narrow-pipe hash functions in an
HMAC. That has to be a problem for those functions.

If we cannot trust the 'random oracle' proofs then either there have
to be alternative proofs or we have to accept 'unproven' hash
functions. The absence of a proof would put any hash function at a
disadvantage in the SHA-3 competition.

From my understanding of the issue it appears that the solution is to
use a wide pipe, i.e. to run the hash function with a 512 bit pipe for
a 256 bit output or with a 1024 bit pipe for a 512 bit output.

rossum

From: Thomas Pornin on 29 May 2010 14:39
According to amzoti <amzoti(a)gmail.com>:
> Perhaps it would disqualify BLAKE, Hamsi, SHAvite-3 and Skein and that
> would be huge.

Actually NIST will select the "finalists" (i.e. "round 3" functions) in
a few months, and it is predicted that there will be about 5 of them. So
one can expect that _nine_ of the current candidates will be
"disqualified".

Nominally, hash functions aim at providing collision resistance,
preimage resistance, and second preimage resistance. That's what the
specifications of BLAKE, Hamsi, SHAvite-3, Skein and the ten other
candidates promise. The article we are talking about does not impact
such resistance claims. In other words, those hash functions are not
"broken", academically speaking (no more than, say, SHA-512).

What would be "huge" would be the publication of actual attack methods
against collision resistance for more than, say, two of the candidates.
During the AES competition, two of the 15 candidates were "broken", but
the 13 others still seem as robust as ever. It was a great demonstration
that the problem of symmetric encryption had been subdued, and that we
knew how to make secure block ciphers. Most of the perceived strength of
the AES comes from that fact: not only AES was not broken, but it was
also chosen among twelve other block ciphers which were not broken
either. If the same situation repeats itself for SHA-3 then this is good
news: it will build trust in the function robustness.


There are a number of protocols which use hash functions as crude
approximations of random oracles. Behaving as a random oracle is a
very strong requirement and claiming that for any hash function would
be quite bold. The paper shows that BLAKE, Hamsi, SHAvite-3 and Skein
are not _exactly_ random oracles (but they are still quite close).

What hash function will be ultimately selected as SHA-3 will depend on
NIST's choice, using priorities and criteria which have not been
publicly and exhaustively described. I surmise that the paper will be
examined quite closely by NIST, and I do not see it as a fatal blow for
the named functions. But I am not NIST.


--Thomas Pornin
From: Kristian Gj�steen on 29 May 2010 15:37
rossum <rossum48(a)coldmail.com> wrote:
>As I read it the narrow-pipe hash functions fail to be 'close enough'
>to random oracles for certain inputs. There is a large subset of
>outputs that cannot be reached from those inputs, for instance the
>paper indicates that about 53% of possible outputs are unreachable for
>those particular inputs when using narrow-pipe hash functions in an
>HMAC. That has to be a problem for those functions.

Not if you cannot say anything useful about those subsets.

--
Kristian Gj�steen
 |  Next  |  Last
Pages: 1 2
Prev: SHA-3 Ouch!
Next: now, you need to encrypt a test .pdf file, what better than the original RSA paper?