--------------------------------------------------------------------------
Subject: 	[CRUNCHY CONTEST] 1 round, width 200, collision
Date: 	22/09/2017 11:42
From: 	Roman Walch <roman walch at student tugraz at>
To:     keccak at noekeon org
Cc:     Maria Eichlseder <maria eichlseder at iaik tugraz at>
--------------------------------------------------------------------------


Dear Keccak team,

I would like to present you a solution for the Keccak challenge[r = 40, 
c = 160, nr = 1]:

Msg1: 0xBBADC011
length: 32
Msg2: 0x0000000000BAADC011
length: 72

Or to easily verify the solution with the Keccak Tools:

counter += verifyCollisionChallenge(
     // Keccak[r=40, c=160, rounds=1]: collision challenge
     40, 160, 1, 0,
     (const UINT8*)"\x00\x00\x00\x00\x00\xba\xad\xc0\x11", 72,
     (const UINT8*)"\xbb\xad\xc0\x11", 32
);

Authors: Roman Walch and Maria Eichlseder (Graz University of Technology)

A solution was initially obtained with a SAT-based attack.
On further investigation the found solution could be identified as a 
generic collision for every keccak configuration (b=200 to b=1600) with 
1 round:
Since the keccak-f function with nr = 1 projects and input consisting of 
only zeros to an output of only zeros XOR the round constant (0x1 in the 
first byte), a collision can be found for every input by prepending a 
block of zeros and flipping the LSB of the first byte of the original input.

Please verify the found solution!

Best regards,
Roman Walch

-- 
Roman Walch - roman.walch@student.tugraz.at
Information and Computer Engineering, Graz University of Technology