2010 Reports : Cryptology ePrint Archive Forum

**Re: 2010/430 is right but so wrong**

**Re: 2010/430 is right but so wrong**

**Re: 2010/430 is right but so wrong**

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.

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.

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

buying cards for one cent

(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

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

buying cards for one cent

(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

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!

“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!

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

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

Please log in for posting a message. Only registered users may post in this forum.