--------------------------------------------------------------------------
From:    林晓恩 <lxe21 at mails tsinghua edu cn>
Date:    2023-08-20 16:46:27 (Sunday)
To:      crypto-competitions at list cr yp to
Subject: [CRUNCHY CONTEST] 2 rounds, width 200, pre-image
--------------------------------------------------------------------------

Dear Keccak Team and all,

We find a pre-image for the challenge Keccak[r=40, c=160, rounds=2]. 

A pre-image of 02 4a 55 18 e1 e9 5d b5 32 19 is: "\xff\x00\x00\x00\x00\x8b\xff\x00\x00\xff\x8b\xff\xff\x00\x00\x8b\x00\x00\xff\xff\x8b\x00\x00\xff\xff\x8b\x00\x00\xff\x00\x74\xff\x55\xff\x55\x8b\xff\xff\xaa\xff\xde\xff\x55\xff\x00\x21\x00\xff\x55\xee\xb8\x88\xdd\xdd\x22\x74\xdd\x11\x66\x77\xdc\x7c\x53\xc8\xad
" message length = 517

Or equivalently:

counter += verifyPreimageChallenge(
// Keccak[r=40, c=160, rounds=2]: preimage challenge
40, 160, 2, (const UINT8*)"\x02\x4a\x55\x18\xe1\xe9\x5d\xb5\x32\x19",
3, // fill in this line with the start round index (0=first)
(const UINT8*)"\xff\x00\x00\x00\x00\x8b\xff\x00\x00\xff\x8b\xff\xff\x00\x00\x8b\x00\x00\xff\xff\x8b\x00\x00\xff\xff\x8b\x00\x00\xff\x00\x74\xff\x55\xff\x55\x8b\xff\xff\xaa\xff\xde\xff\x55\xff\x00\x21\x00\xff\x55\xee\xb8\x88\xdd\xdd\x22\x74\xdd\x11\x66\x77\xdc\x7c\x53\xc8\xad", 517 // fill in this line
);

The main idea of this algorithm is shown as follows.

Forward:
To construct the last message block and the corresponding state, we use the linear structure starting with:
XXXXX
CCCCC
XXXXX
CCCCC
CCCCC
where X means linear and C means constant.
We add equations to ensure that:
1. For each lane, the first 4 bits are equal to the last 4 bits (e.g.0x11).
2. After two rounds, the output bits match the first 40 bits of the request digest.
We repeat solving the equation system (2^40 times in average) to match the last 40 bits of the request digest.

Backward:
Since we choose the start round index 3, there is a zero round constant for the first round.
For the second round, the effect of the round constant can be eliminated by adjusting the messages.
After that, the property of each lane remains while executing the permutation.
For example: 
bb 44 00 66 77                       a9 aa 33 00 88
bb 66 cc 11 00                       33 66 ee 88 44
00 11 cc 77 99 <--inverse 2 rounds-- 22 ee ee cc dd
66 ff 00 00 cc                       33 ff cc 99 dd
66 11 22 cc 88                       bb 66 55 88 dd
(round constant for the second round is 0x8b. 0xa9 xor 0x8b = 0x22)
Gradually, the property of each lane becomes better and better:
the value of each lane is limited in
  {0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff}
=>{0x00,0x55,0xaa,0xff}
=>{0x00,0xff}
=>{0x00}
At last, the state satisfy the all '0' starting state.

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)
Zhengrong Lu (Department of Computer Science and Technology, Tsinghua University, Beijing, China)
Yantian Shen (Department of Computer Science and Technology, Tsinghua University, Beijing, China)
​