More problems with hash functions

Hal Finney hal at finney.org
Wed Aug 25 21:37:15 EDT 2004


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.
>
> In concrete terms, you have a message of n blocks, p1 through pn.
> you xor each block with a value computed by a nonlinear function
> from its sequence number to get q1 through qn.  Now rearrange
> q1 through qn by imposing a total ordering on p1 through pn: for
> example if p4 sorted before p7, you put q4 in front of q7.
> Finally, you compute the hash value on the blocks q1 through qn
> in their new order.

This is an interesting idea, but it does not fully prevent the Joux
attack.  This is seen most obviously in the two block case, where
your method can at most increase the attacker's work by a factor of 2.
Joux shows how to find a 4-collision using 2*2^(n/2) work, while it should
take 2^(3n/4) work.  In the case of a 160 bit hash this is the difference
between 2^81 and 2^120.  Doubling the work to find the 4-collision will
not do much to address this discrepency.

Even in the more general case, where Joux puts k blocks together to
generate 2^k multicollisions, I can see a way to attack your method,
with an increase in the work by only a factor of k^2.

The attacker could choose an ordering of the blocks ahead of time, and
find collisions which preserve that order.  Specifically, he can start
searching for collisions in the first one, which WOLOG we will call q1.
He can continue to search until he finds a collision which puts p1 into
the first 1/k of "block address space", which will guarantee that this
block will sort first.  This will increase his work by a factor of k^2
(because only 1/k of the time will he get lucky, for each of the two
blocks in the collision).  Then he can find a collision in q2 which
puts p2 into the 2nd 1/k of block-address space, guaranteeing that p2
will sort as the second block.  Again this increases the work by k^2.
Proceeding down the line he produces a collision which leaves the blocks
in his pre-chosen order, at a cost of k^2 more work.

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.

Hal Finney

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



More information about the cryptography mailing list