More problems with hash functions

[bear]

On Wed, 25 Aug 2004, Hal Finney wrote:

>Bear writes:
>> One interesting idea which I came up with and haven't seen a way
>> past yet is to XOR each block with a value computed from its
>> sequence number, then compute the hash function on the blocks in
>> a nonsequential order based on the plaintext of the blocks.
<snip>

>This is an interesting idea, but it does not fully prevent the Joux
>attack.
 <snip>
>The attacker could choose an ordering of the blocks ahead of time, and
>find collisions which preserve that order.
 <snip>
>
>Joux shows that finding an 2^k collision takes k times the work to
>find a single block collision.  Among other things he shows how this
>reduces the work to find a collision in the output of two independent
>n-bit hashes from 2^n to n*2^(n/2).  Your approach effectively makes
>this (n^3)*2^(n/2) which is an improvement, but still not attaining
>the exponential security increase expected from ideal hash functions.

You are correct.  Thank you for your quick and clear thought
regarding the proposal.  Increasing the attacker's work by
a factor of n^2 where n is the number of blocks preserves the
strength only where n^2 >= (2^k)/2 where k is the block size.

So, for a 160-bit hash, (2^k)/2 is 2^159, and that means the
proposed method preserves nominal strength only for messages
longer than 2^80 blocks.  Which in practical terms will not
happen; I don't think 2^80 bits of storage have yet been
manufactured by all the computer hardware makers on earth.

I guess I momentarily forgot that with a hash function the
attacker has access to the plaintext and can therefore tell
unambiguously the result of the permutation of the blocks.
I'll continue to think about it.  Maybe I'll come up with
something better.

				Bear


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com