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ård construction with chaining variables
larger than the message block. It uses two chaining variables, H a 512bit
digest of the message block, and P a permutation of the numbers between 0
and 127.
Each time P passes through the compression function it is permuted purely
according to the Message Block, that is the same message block permutes P in
the same way each time.
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