[CRUNCHY CONTEST] 3 rounds, width 400, pre-image

[孙瑶]

Dear Keccak Team and all,

We present an GPU-based algorithm for solving nonlinear systems and find a pre-image for the challenge Keccak[r=240, c=160, 3 rounds]. We  formulate the corresponding system, and fix some positions to 0. Hence, we obtain a square polynomial system with 80 equations in 80 variables. We enumerated the values of 46 variables and solve the remaining nonlinear systems. Eight GPU card (nvidia 1080Ti) are used to speed up the computations, and finally we find a pre-image in 5 days. 

A pre-image of 5c 9d 5e 4b 38 5e 9c 4f 8e 2e is:

"\x53\x73\xe0\x75\x3d\xec\xaf\x5b\x2e\xc1\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x53\x73\xe0\x75\x3d\xec\xaf\x5b\x2e\xc1"

message length = 238

Or equivalently: 

counter += verifyPreimageChallenge(
        // Keccak[r=240, c=160, rounds=3]: preimage challenge
        240, 160, 3, (const UINT8*)"\x5c\x9d\x5e\x4b\x38\x5e\x9c\x4f\x8e\x2e",
        0, // fill in this line with the start round index (0=first)
        (const UINT8*)"\x53\x73\xe0\x75\x3d\xec\xaf\x5b\x2e\xc1\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x53\x73\xe0\x75\x3d\xec\xaf\x5b\x2e\xc1", 238 // fill in this line
     );

We are grateful to Maodong Liao and Dingkang Wang for helpful discussions.

Best Regards,

Yao Sun (State Key Laboratory of Information Security,
        Institute of Information Engineering, 
        Chinese Academy of Sciences, China)
Ting Li (State Key Laboratory of Information Security,
        Institute of Information Engineering, 
        Chinese Academy of Sciences, China)

--
The Best or Nothing!
State Key Laboratory Of Information Security (SKLOIS),
Room 3214, Tel: 010-82546583.
Institute of Information Engineering, CAS.