--------------------------------------------------------------------------
From:   孙瑶 <sunyao at iie ac cn>
Date:   17/08/17 13:45
To: crypto-competitions at googlegroups.com
CC: crunchy at noekeon org, 李婷 <liting at iie ac cn>
Subject:    [CRUNCHY CONTEST] 3 rounds, width 400, pre-image
--------------------------------------------------------------------------

Dear Keccak Team and all,

We present a GPU-based algorithm for solving nonlinear systems and find a pre-image for the challenge Keccak[r=240, c=160, 3 rounds]. We formulated the corresponding system, and fixed some unknowns to 0. Hence, we obtained a square polynomial system with 80 equations in 80 variables. We enumerated the values of 46 variables and solved the remaining nonlinear systems. Eight GPU cards (nvidia 1080Ti) are used to speed up the computations, and finally we found 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.