-------------------------------------------------------------------------- From: 林晓恩 Date: 2025-10-18 20:52:47 (GMT+08:00) To: all at keccak team Subject: [CRUNCHY CONTEST] 5 rounds, width 800, pre-image -------------------------------------------------------------------------- Dear Keccak Team and all, We find a pre-image for the challenge Keccak[r=640, c=160, rounds=5]. A pre-image of 6e f2 61 6f eb b9 9b 1f 70 ed is: "\x5e\x5e\x5e\x5e\x63...(the message)...\x42\xbb\x63\x1e\x88" message length = 17275, the start round index = 5 The equivalent verification code containing the complete message is provided at the end of this email. The result is obtained by internal differential cryptanalysis. 1. We first find 10 states that start with symmetric capacity part (period $I=8$) and also match the required digest. 2. We then find around $2^{41}$ states that start with symmetric capacity part and also end with symmetric capacity part after 5 rounds. 3. By scanning these $2^{41}$ states multiple times, we are able to bridge a path that starts from the all '0' IV, traverses many states with symmetric capacity part, and finally reaches one of the 10 target states from Step 1 that leads to the required digest. As a result, a 27-block preimage is found successfully. The specific details are in the slides from Permutation-Based Crypto (PBC 2025) workshop. The expected guessing times will be around $2^{61}$. After further optimization of the code implementation, the solving time for each guess is around 0.4 5-round Keccak calls according to the performance on a personal computer (3.7 GHz). The experiment is completed in around 7 days using 3000 core-groups on the new Sunway supercomputer. 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) Enming Dong (The National Research Center of Parallel Computer Engineering and Technology, Beijing, China) Wenhao Wu (The National Research Center of Parallel Computer Engineering and Technology, Beijing, China) Yantian Shen (Department of Computer Science and Technology, Tsinghua University, Beijing, China) -------------------------------------------------- counter += verifyPreimageChallenge( // Keccak[r=640, c=160, rounds=5]: preimage challenge 640, 160, 5, (const UINT8*)"\x6e\xf2\x61\x6f\xeb\xb9\x9b\x1f\x70\xed", 5, // fill in this line with the start round index (0=first) (const UINT8*)"\x5e\x5e\x5e\x5e\x63\x63\x63\x63\x73\x71\x71\x71\x19\x19\x19\x19\x9d\xbd\xbd\xbd\xfd\xfd\xfd\xfd\x23\x23\x23\x23\x03\x03\x03\x03\x63\x63\x63\x63\x52\x52\x52\x52\x68\x68\x68\x68\x37\x37\x37\x37\xad\xaf\xaf\xaf\xa9\xa9\xa9\xa9\xec\xcc\xcc\xcc\x12\x12\x12\x12\x17\x17\x17\x17\x63\x63\x63\x63\xd9\xd9\xd9\xd9\xb0\xb0\xb0\xb0\x22\x21\xfc\x09\x94\x76\xb0\x14\xba\x2a\x69\x06\x9e\x66\xc6\x2b\x29\xc6\x1d\xc0\x2a\xe8\x30\x8f\xe2\x86\x57\xff\xb0\x69\xe1\x91\x78\xfe\xe0\xd8\x8b\x9c\xc9\x90\xc8\x7b\x40\x8d\x83\x04\xd4\xa5\xf9\xc0\xbb\xa2\x29\x07\xd9\x74\xad\x6d\x86\x8a\xab\x79\xae\x0f\xc3\xe4\xc8\x3f\xf4\x71\xf8\xeb\xb7\xb5\x11\xd3\x04\x16\x01\x9a\x88\x33\x37\xb3\x24\x15\xb4\xd4\x1a\xeb\x6c\xf1\x60\x14\x47\xdf\x5f\x10\x64\x86\x92\x90\x1f\x55\x31\x4b\x80\xe7\xda\x33\xe2\x19\xd0\x35\x8d\xd0\xcb\xe1\x73\x28\xd3\x89\xf3\x89\xb5\x5a\xe3\xc1\x4a\xfd\x6d\xc0\x23\xe1\xe0\x9d\xd8\x2f\x12\x1a\xc7\x11\x78\x97\xc3\x2e\x0d\x25\xdf\x86\xf3\x81\xef\x7c\x64\x1e\xbc\xf4\x04\x06\xf8\x18\xc6\x0e\x22\xc5\x25\x30\x22\x01\x0f\xe1\xdd\xc8\xed\x85\xc2\x3e\xee\x75\xe6\x8c\x6f\xd0\xf4\xdd\x83\x54\x17\xe1\x7e\xa6\xe3\x83\x4c\x51\x8f\x60\x5f\x82\x41\x23\xd9\xce\x19\xc1\x56\x91\xbe\x2a\x3b\xbf\x04\xe6\xda\x37\xb0\x24\x27\xe7\xb9\x39\xaa\x5c\x91\xb7\x76\x8a\x11\xf1\x00\x50\x23\x63\x18\x25\x64\x84\x3a\x62\xce\x4c\x2d\xb3\x10\x9b\x40\x4f\x25\x3d\xc0\x6d\x52\x27\x2d\x16\x3f\x6e\xec\xd8\x55\x6c\xea\xcf\xaf\x67\x83\x0d\xb8\xea\xe7\x3b\xca\x1a\x16\x17\xc8\x5c\xec\x6e\xbb\xf0\xe5\xd3\xd0\x55\x03\x29\x21\x60\x60\x3f\xe2\x38\xed\xee\x07\xfa\xa8\xd3\x9f\xf3\xbf\xe6\xf5\xa3\xa4\xf3\xa6\x27\xb9\x83\x29\xea\x10\xaf\x16\xe8\xba\xfe\xb2\x28\xb8\xd8\x3c\xa4\x33\xd8\xfc\xf0\xd3\x89\xce\xb8\x7c\x6e\x41\x65\x45\x40\x7f\x7b\xe3\x8c\x7f\x71\xb2\xfa\xb3\x25\x1d\x73\x71\x7f\xf8\x52\x7b\x96\x5a\x4c\xb6\x5f\xea\xc4\xdf\x21\xa1\x7c\xd0\x65\x54\x51\x72\x7e\x23\x12\x01\xdb\x5c\xdc\x42\x3f\xc4\xe1\x3d\x03\xfc\x10\x5d\x74\x12\x02\xf9\x04\x4f\x24\x28\x64\xd3\x23\x69\x50\xd0\x15\x1a\x7d\xc2\x1b\x80\x69\x11\x87\xfc\x81\x46\x40\x76\x5e\xc6\xee\x38\xf6\x57\xcc\xa0\x6b\xc9\x37\x6e\xed\x0b\x29\x1b\xd2\x68\xf6\x3b\xe6\x85\x5b\xcc\x4b\x61\x3a\x29\xf0\xc8\x30\x4d\x91\xea\x51\x9c\xbe\x0e\x81\xdf\x71\x51\x8a\xb3\x24\x3b\x2e\x08\x5e\x53\x01\xda\x37\x71\x2b\x0d\x58\xab\x7a\x1a\xf8\xb3\xbf\x15\x0b\xf7\xec\xb3\xa6\x85\x90\xbe\x81\xd7\xf3\x8c\x84\x0e\x84\x45\x5b\xfc\xd8\x7d\x24\x53\xe8\xf8\x5b\xd9\xc8\x4b\x27\xd4\xea\x85\x84\xaf\xa5\xfe\xb8\x80\xfc\x97\x4e\xdc\xac\x9c\xd6\x42\x36\xb8\xb5\x7a\x83\x03\x59\x8e\xca\xb4\x01\xa8\xde\xbb\x70\x3c\x43\xef\x16\x29\x31\x88\x11\x81\x8f\xd3\x21\x63\x60\x3a\x6d\x35\x4e\xb6\x7b\x36\x0e\x79\x73\x2a\x82\x7a\x25\x19\xca\x19\x58\xc4\xe1\x8c\xf3\x31\xa7\x9a\x3c\x4e\xaa\x53\x39\xb5\x5f\x1d\xfd\xf2\xe5\xec\x76\x2a\xcb\xac\xa6\xb8\x96\x49\x5c\x73\x89\xe1\x20\x8c\xb0\xc5\xba\x06\x48\xba\x42\xe0\xf1\x22\x00\xa4\xa9\x25\xbe\x99\x80\x7d\x1b\x6e\xf6\x59\xfe\x9c\xcb\x58\x37\xc2\x63\x0d\x3e\x18\x1c\xf5\x76\x6b\x01\xac\xb0\x80\x1a\x44\xa7\xe8\x1c\x73\xbc\x89\x22\x2b\xf1\x89\x18\xef\x8e\xd7\x67\xf0\x69\x61\xb1\x98\x04\x45\xa1\xc5\xc0\x7d\xbb\x9e\xba\x33\x8a\x43\x96\x1a\x0d\x9e\xca\x50\xae\x4b\x1f\xf1\x31\xdb\x91\x37\x76\x3f\xb7\xa4\xca\x23\xa3\x8a\x44\xd4\x80\x0e\xa7\x0a\xea\xb9\xe8\xef\xbd\x52\xf8\xf7\xb2\x8b\x93\x23\xb4\x1f\xcf\xaf\x1f\x38\xd9\xe5\xa7\xc4\x13\xa2\xc3\x4c\xba\xa1\x6c\xfe\x01\xef\x01\xf3\x90\x3a\x1f\xad\xe3\xba\x63\x7d\x8a\x23\x3b\xe4\x38\x1b\x10\xb8\x83\x44\xfa\xb9\xa5\x81\x8d\x72\x11\x1f\x71\x96\x22\x85\x33\x0f\xe0\x5c\x66\x4c\x6e\xd9\xcb\xc2\x86\x98\x82\x53\xe7\x7d\x28\x2f\xe5\x72\xeb\xbf\xb7\xdd\x85\xa6\x13\x0e\xb6\xd1\x9b\x4b\x0c\xb9\x81\x06\xb0\xe7\x35\x81\x03\xb6\x67\x42\xf4\x46\x7f\x58\x10\x29\x97\x73\x01\x3b\xe5\xb9\xc9\x35\x80\x78\x75\x68\xfa\x78\x8a\x3f\xe7\xc3\x71\x5e\x2f\xb4\x3f\x0e\x00\x20\xef\x95\xb3\x67\xf1\xe4\x01\x1f\x09\x5b\x9a\x96\x8a\x42\xaa\x4d\xe2\x97\x6a\xae\x0e\xef\xad\x17\xd1\x4a\x41\x48\x82\x6e\x61\x94\x22\xf3\x6f\xd8\xb4\xe1\x22\xb8\x43\xcd\xcf\x35\x0d\xd3\x3b\xab\xac\x1b\x94\xb6\x16\x11\x9f\x9a\xba\xd8\xe2\x0c\xa6\x48\x35\xf9\xc7\xa8\x70\xe7\x12\xe7\xa6\xb6\x62\x5f\x51\x9b\xdb\x9c\x5b\xbe\xb8\x9b\xd6\x13\x64\x45\xe5\x8e\x24\x96\xf7\x75\x92\xfb\xa8\x8b\xfe\xcf\x1d\x61\x5c\x8e\xf0\x4f\x91\x08\xeb\xaf\x6c\x64\x06\x3e\xea\x06\x96\x6a\xf0\x94\x79\x34\xd0\x58\x9b\x3a\x99\xa5\x9e\x7e\x7d\xdd\x20\xfa\xea\xd3\xd3\xb7\xbf\xb5\xef\x3e\x77\x7c\x92\x3c\xa9\x6a\xea\x13\x03\x11\x8b\x12\x17\x93\x85\x07\x86\xb6\x40\x42\x89\xd2\x0e\xa0\x49\x22\x88\xba\xa0\xd7\xea\x29\x9a\x6d\x86\x56\x2b\x76\xd0\xb5\xb1\xb3\x7e\xf0\xf8\xd6\xc6\xc7\x39\x88\xf1\x17\x7b\x89\x1f\x94\x4b\xce\xda\x76\xb7\x36\xec\x0a\x7b\x65\xe6\x08\x70\x27\x88\x26\x00\x27\x86\x64\x96\xbe\xd9\x0a\x32\x76\x35\x45\x27\x8e\x1f\xb4\x49\x93\xa0\xa3\xf1\x7d\xfc\x87\x7a\x38\x2a\x5f\x29\x62\x00\x28\xf0\xd2\x8e\xd7\x37\x3e\x82\x2a\x99\xf5\x3a\xeb\x8d\xe3\xc4\xe7\xcb\x04\x6f\x89\x8a\x5f\xf1\x1c\x37\xbe\x2a\x96\x4a\xff\x4c\xf1\x46\x97\x91\x76\x60\x7a\xcd\x05\x81\x30\x9f\xe5\x92\x16\x21\x91\xb4\x4c\x13\xb7\x97\xd7\xc2\xcc\x30\x2b\xbe\x1b\xc9\x11\x03\xd9\x5c\x74\x70\xdd\xa2\x91\xf4\x5c\x56\x41\xd2\xd8\x6a\x2a\xd6\xdf\x6f\xda\xa8\x0f\xa8\x9d\x26\xb5\x96\x4f\x11\x88\x8c\x8d\x77\x80\xe4\x57\xc8\x32\x20\x3a\xc3\x03\x73\x07\x62\xd4\x13\x51\x72\x54\x1b\xf0\x17\x55\x24\xea\x35\xa4\x87\xf2\xd0\x94\xc2\xb9\xdb\x2a\xbd\xcf\xe2\x2c\x5d\x05\x42\x40\xe8\xf0\x5f\xd1\x04\xea\x5a\xfc\x34\x8b\xdc\xd8\x09\xde\xab\xc4\x5d\x9a\x19\xd5\x3f\xef\x11\x0a\x9c\x0a\x9c\x25\x36\x2a\x75\xcd\xe2\xb5\x10\xf8\x36\x4d\xfa\x07\x0e\xe2\x8a\x81\xde\x5c\x7b\x99\xc8\xee\x62\xb6\x8e\xfc\x88\xd1\x49\x94\x4a\xed\xbb\x6a\xf8\x77\x3f\xf1\x29\x45\x05\x44\xf2\x19\x2a\x33\x0a\x5b\xe9\x6b\xe4\x2f\x8b\xbb\x86\xe2\x4b\x87\xbc\x3d\xda\xd6\x24\x02\xf2\x02\x5e\x9a\xde\x06\xa2\x1e\x34\x8a\xa8\xbd\xe1\xc0\x46\xea\x6f\x08\xf4\xc8\x51\x81\x8a\x29\x33\x83\x52\x73\x2e\x5e\x85\x6d\x08\xa0\x6b\xd1\x6e\x7a\xec\x05\x7b\xd5\x93\x08\x8f\x41\xcd\x27\x8f\x1a\x77\x3b\xea\x81\x2e\xf1\x96\x54\x68\x9d\xcf\x89\xf0\x9f\xc6\xfd\x39\xf2\x29\x45\xf5\x7e\x9d\xfc\xed\x85\x71\x7a\xb4\xc2\x5c\x2c\xa4\x0f\x60\xf8\xdc\xbc\x1e\xd1\xa8\x22\xe1\xa2\x3b\xc8\xfe\x56\xb7\xd1\x76\xd5\xcb\xa8\xfd\xaf\xa8\x55\x0e\xe7\x75\x5e\x08\xca\x35\x67\xc5\x55\xed\xfa\x8f\x68\xb8\x7b\xde\x8e\x94\xdf\xb3\xb9\x5e\x23\xa6\x24\x95\x84\xc5\x3b\x92\x95\x35\xab\xd5\xd7\xf6\xb2\x89\xfa\xce\x0d\x28\x76\x63\xa9\x8a\x66\x17\x74\x54\xde\x8d\x72\x50\x63\x42\x73\x0f\xa9\x42\xea\x31\xbd\x89\x26\xe3\x22\xfa\x53\x82\x67\x56\x7d\x1b\x13\x9e\x89\x8e\xf9\x8f\x51\x4a\xcf\x3a\xa5\x57\x3c\x58\xb0\xf2\xc5\x5d\xa8\x69\x40\x4b\xa3\x32\xfe\xb2\x7f\x56\xc8\xa3\x4b\x90\x74\x2c\x9d\x1d\x4d\x24\xaa\xfd\x62\xa5\xd4\x2d\x11\x1a\x5d\x0d\xb0\xd2\x8b\x7e\x7d\x30\x63\xf3\x8b\xf8\xf7\xf4\x92\x4e\x5f\x41\x65\x34\xcb\xac\xc3\x4d\x0c\xc4\xd5\x9d\x8a\x1b\x96\x86\xdf\x71\xa4\x07\xa1\x0e\x06\x79\x8e\x72\x4d\x38\x3b\x60\x46\x8b\xa2\xd8\x7a\xc7\xcc\xaa\xd7\x1d\x9c\x3e\x9d\x2c\x41\x8a\x82\xfd\xeb\x48\x9d\xa4\xf3\xfc\x5f\x4e\xf8\xa5\xc6\x5d\xb8\x8b\xcc\xf4\x49\xd7\xd2\xa5\xd4\xb7\xc4\x3e\x4d\x40\xde\x62\xdd\xfd\x6a\xb8\xaf\x31\xd5\x3f\x1b\x03\x0d\x51\x47\xca\xab\xd1\x48\x51\x90\xa1\x76\x1a\x44\x70\x5a\xdf\xda\x00\xe5\x5b\x1f\xbc\x5a\x64\xbc\x69\x17\xb2\x08\xc1\xe6\x6b\xa3\xdb\x8f\x6a\xd6\x1e\x2f\x9c\x71\xad\xe7\xaf\x32\xfb\xf8\x3a\x42\x78\x00\x48\x99\x13\xd4\xed\xe8\xb0\xfd\xc4\x54\xf7\x72\xd2\x80\xc1\xd4\xae\xf3\xae\xa6\x36\x79\x48\x9f\xf7\x4d\xd4\x13\x47\xc7\x6d\x25\xe4\xa4\x79\x41\x82\x72\xdf\x6c\x9f\xba\xdf\xe3\x43\xbc\x94\x93\x18\xa0\xb1\x26\x39\x8f\x6d\xac\x89\x40\x95\xae\x7f\xab\x3a\x17\xfb\x06\xcb\x35\xad\x29\x41\xbd\xb8\x7e\xa0\x53\xd2\xfc\x9e\x66\xe5\xbb\x38\x01\x84\x0e\xf9\x0d\x9e\x9d\x05\x82\x9d\xe0\x56\xef\xf8\x40\x33\xa6\xa2\x11\xfe\xc7\x33\xd6\x51\x8b\x9b\x1b\x05\x5a\xca\x1b\xf2\x9a\xc2\x23\x70\x4c\x9c\x3b\xc9\xd1\x8e\xb4\x54\x1e\xd5\x90\x85\x71\x0d\x54\x1c\x74\xff\xf0\xd5\x11\x36\xe4\x73\x0a\x7a\x8c\xe4\xca\x76\x32\x1f\x52\xcd\x49\x9f\xb1\xcb\xb0\x74\x85\x05\x58\x88\xc9\xfd\xc6\xa4\xa8\xf6\x8e\xc7\x09\x27\x0a\xbf\xac\x28\x72\xba\xd6\xda\xe6\x2a\x1c\x12\x96\xce\x9b\x34\xbb\x69\xda\xf4\xb6\x98\x18\xb4\xcc\x60\xea\x6e\x27\x25\x74\x38\x71\x09\xce\x76\xd1\x2c\x6a\x78\x3e\x20\x27\xbd\x71\xe3\xa1\x85\xb2\x03\x91\x37\x45\xca\x15\x3d\x20\x25\x9e\x57\x0e\x34\x0c\xfe\xad\xbf\x61\x0e\xaf\xb1\xa8\xf9\x4a\xae\x62\x22\x05\xc0\x90\xcf\x33\x28\x61\x25\x9e\xed\x15\xec\x1c\xbe\xc6\x9c\xd6\x18\x9c\x49\xaa\xe3\x5d\x56\x56\x33\xed\x05\x6b\x45\x63\x63\x76\x7d\x4f\x43\x51\x24\xc4\x39\x01\x75\x04\xa9\xf7\x9a\x92\x5b\xd9\x29\xea\xa4\xcc\x04\x17\x2d\x72\x73\x50\xee\x41\xab\xd4\xc9\xe8\x08\x13\x74\x80\x99\x63\x28\x36\xad\x64\xbd\xaf\x1e\x97\x97\x5d\x98\x43\x83\x2e\xa5\xd8\x39\xef\x58\x9e\x97\x98\x04\x81\x13\xb7\x4a\x20\x8c\x8a\x55\x89\x20\x79\xd6\x55\x69\xa0\xca\x79\x06\x70\xfc\x17\x71\xd3\x1b\x2e\xf4\xb1\x7e\x7e\x42\xbb\x63\x1e\x88", 17275 // fill in this line );