2010 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2010. Please put the report number in the subject.
2010/430 is right but so wrong
Posted by: Orr (IP Logged)
Date: 05 August 2010 19:28

The authors of 2010/430 claim that finding collisions in a narrow-pipe takes 2^{n/2-k/2} calls for the _hash function_, which is lower than 2^n/2 expected by the birthday bound.

However, the colliding messages are 2^k long, meaning that the amount of work is 2^{n/2+k/2} _compression function_ calls.

As finding a collision in any of the discussed hash functions can be easily done once a collision in the compression function is found, then using the results of the paper is not only wrong, but misleading, as one can easily find a collision in the above mentioned hash functions using only 2^n/2 compression function calls.

Re: 2010/430 is right but so wrong
Posted by: Vlastimil Klima (IP Logged)
Date: 05 August 2010 23:01

Orr,
you mix theory and practice, hash function
and compression functions together.
We even underlined the difference between
hash function calls and compression
function calls in the paper.

You wrote: "I explain why the results of
this paper are right but not interesting."
Well, so here is an interesting game for you.

Let us have a SHA3 winner.

Let there are two casinos. In both casinos
they play the same game: the players are
(the card has a 256bit number) until they
find two cards with the same number.
Once a player present such a collision,
he/she win all the money from both casinos.

In the first/second casino,
the cards are numbered using SHA3/SHA2
and the method and the messages,
described in our eprint paper.

Even if I don't know how long messages
they used for producing the cards,
even if I don't know what is SHA3 winner,
even if I don't know its compression function,...
I would go to the first casino.

Vlastimil Klima

Re: 2010/430 is right but so wrong
Posted by: gligoroski (IP Logged)
Date: 09 August 2010 05:38

Designers of narrow-pipe hash functions can ignore the facts that those designs are inferior to wide-pipe designs. Its their choice.

“Know the enemy and know yourself; in a hundred battles you will never be in peril. When you are ignorant of the enemy, but know yourself, your chances of winning or losing are equal. If ignorant both of your enemy and yourself, you are certain in every battle to be in peril.", Sun Tzu.

Regards,
Danilo!

Re: 2010/430 is right but so wrong
Posted by: Orr (IP Logged)
Date: 13 August 2010 13:59

Danilo,

Your are entitled to your opinion. But narrow pipe designs are more efficient, and their security is clearly defined (the discussion on the hash function mailing list can probably explain why the paper is technically right, but so wrong, for example, the security proofs assume less than birthday-paradox number of queries to the _compression function_, your attack makes more than that queries).