Shahram Khazaei, NIST mailing list 2009-07-16
----------------------------------------------------

Dear All

We have found the following three-iteration linear differential path for CubeHash-4/48 which holds with probability 2^{-134}.

D_0 = 
00000008000000000000000800000000
00000000000000000000000000000000
04000000000000000000000000000000

D_1 = 
88008000000000008800800000000000
00000000000000000000000000000000
00440040000000000000000000000000

D_2 =
08000000000000000800000000000000
00000000000000000000000000000000
00040000000000000000000000000000

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 48-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 greatly.

Here is a collision example for CubeHash-4/48 with 512 bit hash values which have been found in 2^{37}.

Message1  =
741B87597F94FF1CC01761CA0D80B07C
C2E6E760C95DF9A508FFCBABDA11474E
2CCEA7AC62A7C822BE29EDCBA99D476C
1D30F8022F4AE8DBD477FA1F7DE37C1A
F2516BC6FA4657F9E51539C10EC114DA
3B8264DD9361FE07C3D56E88E8512201
014A11BFE2FF346FC306D1E430EE8026
8785A9F841562C9A88A6BF5858E95362
F541ACF41C2FDCC1C49470DF1DFAEFDC
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000


Messag2 =
741B87597F94FF1CC01761CA0D80B07C
C2E6E760C95DF9A508FFCBABDA11474E
2CCEA7AC62A7C822BE29EDCBA99D476C
1D30F80A2F4AE8DBD477FA177DE37C1A
F2516BC6FA4657F9E51539C10EC114DA
3F8264DD9361FE07C3D56E88E8512201
894A91BFE2FF346F4B0651E430EE8026
8785A9F841562C9A88A6BF5858E95362
F505ACB41C2FDCC1C49470DF1DFAEFDC
08000000000000000800000000000000
00000000000000000000000000000000
00040000000000000000000000000000

Hash Value =
EB4F51C7E3DA8C84CEB269F62DA7C59B
4AF383E1B83BB00DAAA49FD2683D875D
13DECFB92037CC60779010F21732950B
7443289628B3B1D7B0AD9EE4CCB8782D


Best regards
Eric, Shahram, Thomas, Willi