Ethan Heilman, NIST mailing list 2009-03-12
---------------------------------------------
Dear Nist and all,
I believe I have found an inexpensive method for generating arbitrary collisions in spectral hash for all key sizes.
Spectral Hash uses a Merkle-Damg
f(P_{0}, H_{0}, M) => P_{1}, H_{1},
f(P_{1}, H_{1}, M) => P_P{1}, H_{1},
f(P_{2}, H_{2}, M) => P_P{2}, H_{2}
...
f(P_{n}, H_{n}, M) => P_P{n}, H_{n}
It is easy to generate some message block M, which repeated n times produces a P_{n} s.t. P_{n} = P_{0}, that is to find a cycle in P.
H_{1} is solely dependent on P_{0} , H_{0} and M, if M does not change and P repeats itself twice, H will cancel out and return to it's initial state. By engineering cycles in the chaining variables we can cause collisions in the chaining variables which allow us to create collisions in the hash function.
I have attached some of the generated sample collisions and test code I used to verify the hash collisions, a full write up of the attack will be forthcoming,
Ethan Heilman