Shahram Khazaei, NIST mailing list 2009-07-06 ---------------------------------------------------- Dear all We have found the following three-iteration linear differential path for CubeHash-4/64 which holds with probability 2^{-134}. D_0 = 00000008000000000000000800000000 00000000000000000000000000000000 04000000000000000000000000000000 00000000000000000000000000000000 D_1 = 88008000000000008800800000000000 00000000000000000000000000000000 00440040000000000000000000000000 00000000000000000000000000000000 D_2 = 08000000000000000800000000000000 00000000000000000000000000000000 00040000000000000000000000000000 00000000000000000000000000000000 The difference in the third iteration (D_2) is used to erase the difference in the state caused by the differences in the previous two iterations (D_0 and D_1). A random search would require complexity of order 2^{134} to produce a collision. This can be done by testing random message pairs of the form (ZERO is a 64-byte all zero message block) Message1 = M_{-1}||M_0||M_1||ZERO Message2 = M_{-1}||(M_0 \xor D_0) ||(M_1 \xor D_1)||D_2 till we get a collision. The first message block M_{-1} is used to randomize the state. However, using some message modification techniques we have reduced the complexity to 2^{34}. Here is a collision example for CubeHash-4/64 with 512 bit hash values: Message1 = B5CB4ADE6DD5BD89099036B925F2579E 74072A490D6CF18E2A51926420DF1BD5 AA65B4183A71A14301D7FC26CA53C43E 5BEE87685A79F684CA88E8EA6803C012 0B82502C520BE7BEFAFBFC14DEFA0BF7 6FDB3C224CF3D84F7D7DDDFE7FE3610C 9587726C6DFFD5EEE4BBC2336D47FFF4 9463EF271B64AA4C28C04BA07072DE1E 41B49607515E6C5E6DBA150D6F4276AB 4EF0EF0FCADF695B9DD0C56918F47682 F7D79823A40FCA2ED344DB3A5B8A31CB 785B7B0E46C0EA04E846FEF8DBF251E1 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 Messag2 = B5CB4ADE6DD5BD89099036B925F2579E 74072A490D6CF18E2A51926420DF1BD5 AA65B4183A71A14301D7FC26CA53C43E 5BEE87685A79F684CA88E8EA6803C012 0B825024520BE7BEFAFBFC1CDEFA0BF7 6FDB3C224CF3D84F7D7DDDFE7FE3610C 9187726C6DFFD5EEE4BBC2336D47FFF4 9463EF271B64AA4C28C04BA07072DE1E C9B41607515E6C5EE5BA950D6F4276AB 4EF0EF0FCADF695B9DD0C56918F47682 F7939863A40FCA2ED344DB3A5B8A31CB 785B7B0E46C0EA04E846FEF8DBF251E1 08000000000000000800000000000000 00000000000000000000000000000000 00040000000000000000000000000000 00000000000000000000000000000000 Hash Value = 8DEF4D2264B707EFC678319E1D6FB681 5D415C9840CBA73D047758BC440A0C87 A51CD6842B32F523F4FD0C02C4DDE42A 9D06151FA2B22C0A47ADB171E63510BF Best regards Eric, Shahram, Thomas, Willi