Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email firstname.lastname@example.org
From: David Wagner (dawmozart.cs.berkeley.edu)
Date: Sat Mar 31 2001 - 18:38:05 CST
Bram Cohen wrote:
>First, compute CBC MACs using the two fixed keys (a CBC MAC is where
>encrypt the first block, xor with the second, encrypt again, xor with the
>third, etc.) Call the two MACs A and B. Now encrypt A using B and B with
>it's last byte xored with FF using A (the xor is in case the data is only
>a single block length, making A and B both be the original
>file). Concatenate those two values together and that's the hash.
It's not as secure as the 256-bit output length would suggest: one can
find collisions with 2^64 work. Consequently, I think this construction
should be considered broken.
Let h_1(X) denote the hash of X under the first fixed key, and h_2(X)
the second hash. Let X_i be the i-th block of the message X.
Here's the attack. Define f(X_1) = h_1(X_1) xor h_2(X_1), and look for
a collision X_1,X'_1 in f() by hashing 2^64 random messages and sorting
them according to their value of f(). Let X_2 be arbitrary and set X'_2 =
X_1 xor h_1(X_1) xor h_1(X'_1). Note that h_1(X_1,X_2) = h_1(X'_1,X'_2)
by choice of X'_2, and moreover h_2(X_1,X_2) = h_2(X'_1,X'_2) due to
the fact that X_1,X'_1 collide under f(). In other words, we have an
collision in the internal chaining value, and we can append any common
prefix to both messages to obtain a full collision for the hash function.
You can also obtain second pre-images (or even invert the hash) with
2^128 work, again faster than should be possible for an ideal 256-bit
hash function. The attack algorithm is more complicated to describe,
so I won't try here, but I hope the collision attack above should be
enough to point to flaws in this proposal.