Thomas Peyrin, NIST mailing list 2009-01-07
----------------------------------------------------
Hi all !
Here is a colliding pair of messages for the 512-bit version of CubeHash-2/4 (two permutation calls and 4 bytes inserted per round), using five rounds:
Message 1 : 0x72d9dcf5 0xb835e32f 0x05a4593f 0xb897ebd7 0x00000000
Message 2 : 0x72d9dcf5 0xb835e32f 0x04a4593f 0xa897ab97 0x10000000
Hash value : 220f6a8a640870f42757873d8f16bc800f5595faa519aa372091d3f0c1e86527fe9fa656de7d1cb7b9c367b2a06d661627aa321dd3fd2ec6378d61d19a270371
This took me about 10 minutes of computation on my laptop. The differential path has been found by using a linear version of the scheme, as Dai did for his collision on CubeHash-2/12. The messages pair search is very slightly optimized (a little bit less stupid than just testing random pairs).
The method provides an internal collision, thus it works for any hash output. I expect that a collision for CubeHash-2/3 can be also easily found.
Note that CubeHash-r/b runs at about 20 r/b cycles/byte, thus CubeHash-2/4 would run at about 10 cycles/byte.
Cheers,
Thomas Peyrin
Cryptography Expert
Ingenico SA
www.ingenico.com
Tél: + 33 (0)1.41.44.67.44