-------------------------------------------------------------------------- From: 林晓恩 Date: 16-11-2024 22:07 To: all at keccak team, jda at noekeon org Subject: [CRUNCHY CONTEST] 4 rounds, width 400, pre-image -------------------------------------------------------------------------- Dear Keccak Team and all, We find a pre-image for the challenge Keccak[r=240, c=160, rounds=4]. A pre-image of 0d d2 5e 6d e2 9a 42 ad b3 58 is: "\x1d\x00\x0a\x12\x00\x00\x00\x00\x70\xb5\x26\x63\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x86\xc2\x74\x98\x17\x59\xf1\xdb\xee\x56\xdb\x52\x09\x00\xe2\x1e\x4e\xa8\xb9\x63\xdc\xb8\x09\x5e\xcb\x9a\xc4\xb4\x3a\x6a\xbf\xfd\xd6\x16\xd6\x96\x75\x75\x67\xe7\x63\x23\x16\x17\x2d\x6d\x3e\x3f\x7e\x7e\xdd\xdf\x26\x24\x36\x36\x81\x81\xff\xff" message length = 718 Or equivalently: counter += verifyPreimageChallenge( // Keccak[r=240, c=160, rounds=4]: preimage challenge 240, 160, 4, (const UINT8*)"\x0d\xd2\x5e\x6d\xe2\x9a\x42\xad\xb3\x58", 5, // fill in this line with the start round index (0=first) (const UINT8*)"\x1d\x00\x0a\x12\x00\x00\x00\x00\x70\xb5\x26\x63\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x86\xc2\x74\x98\x17\x59\xf1\xdb\xee\x56\xdb\x52\x09\x00\xe2\x1e\x4e\xa8\xb9\x63\xdc\xb8\x09\x5e\xcb\x9a\xc4\xb4\x3a\x6a\xbf\xfd\xd6\x16\xd6\x96\x75\x75\x67\xe7\x63\x23\x16\x17\x2d\x6d\x3e\x3f\x7e\x7e\xdd\xdf\x26\x24\x36\x36\x81\x81\xff\xff", 718 // fill in this line ); The result is obtained by a meet-in-the-middle (MitM) attack on the $2^{80}$ symmetric capacity part with period $i=8$. For the first stage, we use the target internal difference algorithm (TIDA) [1, 2, 3] for producing $2^{32}$ states with symmetric capacity part. For the second stage, we need $2^{48}$ states with symmetric capacity part (or $2^{49}$ if padding rule is considered), and the states should match the required digest after four rounds. To accomplish the second stage, we use a new technique: 1. Determine a 2.5-round internal differential characteristic that starts with no internal difference (a symmetric state). 2. Regard the bits in the state before the third $\theta$ as variables. 3. Add some equations ensuring that the state propagates backward through the second $\chi$ with probability $p=1$. Because the probability of the internal differential characteristic passing through the first round is also 1, the starting state will be symmetric as required. 4. In another direction, invert the digest and derive the corresponding bits before the last $\chi$. 5. Because the internal difference of the state before the third $\theta$ is known, the internal difference of the state before the last $\chi$ can be linearly expressed by the variables. Thus, add some equations to satisfy 40 conditions in terms of $a_{x,0,z}+a_{x,0,z+8}$. 6. With the help of the MILP model, use the rest degrees of freedom to linearize and restrict 31~33 bits before the last $\chi$. 7. Try and collect different solutions of the equation system that match the digest successfully. At last, with time-memory trade-off, it is expected to find a collision between the two sets (states with symmetric capacity) produced by the two stages. The complexity is calculated as follows. For the first stage, the probability of the internal differential characteristic is $2^{-21}$. Thus, we need to guess around $2^{32+21}=2^{53}$ times. For the second stage, the probability of matching the digest is $2^{-9}$. Thus, we need to guess around $2^{49+9}=2^{58}$ times. According to the experimental result, every guess is equivalent to $2^{4.8}$ or $2^{-0.4}$ 4-round Keccak calls for two stages, respectively. In summary, the complexity will be $2^{57.8}+2^{57.6}=2^{58.7}$. The result is run on Sunway TaihuLight supercomputer using 10 thousand cores with around 3+1=4 days. [1] Dinur, I., Dunkelman, O., Shamir, A.: Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials. In: Moriai, S. (eds) Fast Software Encryption. FSE 2013, LNCS vol. 8424, pp. 219–240. Springer, Berlin, Heidelberg (2013). https://doi.org/10.1007/978-3-662-43933-3_12 [2] Zhang, Z., Hou, C., Liu, M.: Collision Attacks on Round-Reduced SHA-3 Using Conditional Internal Differentials. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023, LNCS vol 14007, pp. 220–251. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30634-1_8 [3] Zhang, Z., Hou, C., Liu, M.: Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of SHA-3. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024, LNCS, vol 14923, pp. 241–272. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-68385-5_8 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) Chongxu Ren (Department of Computer Science and Technology, Tsinghua University, Beijing, China) Zhengrong Lu (Department of Computer Science and Technology, Tsinghua University, Beijing, China) Yantian Shen (Department of Computer Science and Technology, Tsinghua University, Beijing, China)