-------------------------------------------------------------------------- From: 林晓恩 Date: 25-02-2024 13:20 To: all at keccak team, jda at noekeon org Subject: [CRUNCHY CONTEST] 4 rounds, width 800, pre-image -------------------------------------------------------------------------- Dear Keccak Team and all, We find a pre-image for the challenge Keccak[r=640, c=160, rounds=4]. A pre-image of 75 1a 16 e5 e4 95 e1 e2 ff 22 is: "\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x52\x25\x14\x75\xc1\x14\x5e\xcf\x5f\x91\xee\x85\x85\x6a\xb3\x8e\x1a\x6c\xd0\x89\x27\x9c\xae\xb5\x93\xf1\x2f\xa1\xbc\x73\xa4\xa4\xe0\x02\xc1\x95\x0e\xeb\x6a\x07\x62\x06\x8e\x83\x8d\x14\x47\x94\xf7\xae\x66\x77\x8d\x5d\x65\xbf\x5a\x66\x4f\x54\x34\x91\xce\x3c\x82\x76\x34\x4e\x7b\xa6\xc7\x7d\x81\x5d\x6a\x38\xd4\x01\x3c\xcb" message length = 1278 Or equivalently: counter += verifyPreimageChallenge( // Keccak[r=640, c=160, rounds=4]: preimage challenge 640, 160, 4, (const UINT8*)"\x75\x1a\x16\xe5\xe4\x95\xe1\xe2\xff\x22", 0, // fill in this line with the start round index (0=first) (const UINT8*)"\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x52\x25\x14\x75\xc1\x14\x5e\xcf\x5f\x91\xee\x85\x85\x6a\xb3\x8e\x1a\x6c\xd0\x89\x27\x9c\xae\xb5\x93\xf1\x2f\xa1\xbc\x73\xa4\xa4\xe0\x02\xc1\x95\x0e\xeb\x6a\x07\x62\x06\x8e\x83\x8d\x14\x47\x94\xf7\xae\x66\x77\x8d\x5d\x65\xbf\x5a\x66\x4f\x54\x34\x91\xce\x3c\x82\x76\x34\x4e\x7b\xa6\xc7\x7d\x81\x5d\x6a\x38\xd4\x01\x3c\xcb", 1278 // fill in this line ); The algorithm is based on [1] with the following improvements. 1. Use more delicate constant settings for the linear structure, so that the bits on the state before Theta of the third round (ir=2) keep constant as many as possible (e.g., X0X01 for most of rows, where X means a linear bit). As a result, by consuming 1 degree of freedom, 6 bits on the state before Theta of the fourth round can be linearized. 2. Build an MILP model to optimize the linearization and the probability of the last Chi matching the digest under limited degrees of freedom. Note that when solving the quadratic equation system by Crossbred algorithm, the guess of some variables is selected according to the result of MILP model, rather than arbitrary values. 3. For the capacity part of Keccak[r=640, c=160] only involves the last plane, the linear structure can be rotated on the y-axis on the starting state (and the following part adjusts accordingly). For example, considering the state before Theta of the second round, the linear bits now lie on x=1 and x=3 sheets, instead of x=0 and x=2 sheets. 4. Use a two-block model with two candidates for the previous message block. Thus, the capacity part can be restricted by 159 equations, saving 1 degree of freedom. In summary, the complexity is calculated as follows. With the linear structure, there remains 98 degrees of freedom before Theta of the third round. To make further linearization, 71 degrees of freedom are consumed so that 19 bits before the last Chi are linearized which result in a gain of around 2^16.5 by adding 19 linear equations. From the digest, 48 quadratic equations can be derived, while 14 of them are included in the 19 linear equations mentioned above. Then, for each guess, we solve 48-14=34 quadratic equations on 98-71-19=8 variables. By guessing the value of one more variable, the quadratic system can be linearly solved by Gauss elimination which brings a gain of 2^7. The guessing times will be 2^(80-16.5-7)=2^56.5. The solving time for each guess is around 2^4.4 4-round Keccak calls according to experimental result (the solving time is usually higher than the time estimated by bit operations). Finally, the total complexity is 2^60.9. [1]Wei, C. et al. (2022). Preimage Attacks on 4-Round Keccak by Solving Multivariate Quadratic Systems. In: Park, J.H., Seo, SH. (eds) Information Security and Cryptology – ICISC 2021. ICISC 2021. Lecture Notes in Computer Science, vol 13218. Springer, Cham. https://doi.org/10.1007/978-3-031-08896-4_10 Best Regards, Xiaoen Lin (Department of Computer Science and Technology, Tsinghua University, Beijing, China) Hongbo Yu (Department of Computer Science and Technology, Tsinghua University, Beijing, China) Congming Wei (Beijing Institute of Technology, Beijing, China) Le He (School of Cyber Engineering, Xidian University, Xi'an, China) Chongxu Ren (Department of Computer Science and Technology, Tsinghua University, Beijing, China)