Prev: SHA-3 Ouch!
Next: now, you need to encrypt a test .pdf file, what better than the original RSA paper?
From: Scott Fluhrer on 29 May 2010 17:36

"Thomas Pornin" <pornin(a)bolet.org> wrote in message
news:4c015f68$0$425$426a74cc(a)news.free.fr...
> 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.

Actually this result does affect collision resistance against the candidates
this applies to (although not greatly).

In a normal brute force attack, the attack hashes a huge number of messages
and looks for the collision. If he models the hash function as a random
function with an output range of 2**N, then he expects to find a collision
after c*sqrt(2**N) attempts (where c is a constant that depends on the
probability of the collision).

Now, if we assume a narrow-pipe hash function, and the attacker uses a
message length that leaves the last block fixed, then (by Gligorski's
observation) the hash function is likely to generate only an output range of
only 0.63 * 2**N outputs, and hence the attacker will expect to find a
collision after c*sqrt(0.63 * 2**N) = 0.80c * sqrt( 2**N ) [and, actually,
it's a bit worse than that, the nonempty output subset is unlikely to be
equidistributed, which makes a collision even more probable]. This
observation is true even if the attacker has no idea what the empty subset
looks like.

Now, this is not a deal breaker; this just makes the obvious brute force
attack a little more efficient (if brute force wasn't feasible before the
attack, it's not going to be feasible with it). In addition, there doesn't
appear to be a way to sharpen this result (which is why we are interested
even in theoretical attacks). One possible attempt to sharpen this would be
to look at longer messages, with the changes confined to the front part of
the message; however that doesn't lead to an attack improvement, as each
message takes longer to hash.

However (IMHO), even if this observation doesn't really disqualify anyone,
if the AHS competition came down to two otherwise equally desirable designs,
this might be enough to tip us away from the narrow-pipe design...

--
poncho


From: Grant Miller on 4 Jun 2010 00:26
On May 28, 8:31 am, 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-...)
>
> Careful with the line wrapping.
>
> rossum

please call my blocking "Tiger blocking," in honor of my cat. no harm
intended i just did what my mind told me was right, NOR AM I IGNORANT
OF MY SEQUELLAE. --gwm
First  |  Prev  | 
Pages: 1 2
Prev: SHA-3 Ouch!
Next: now, you need to encrypt a test .pdf file, what better than the original RSA paper?