--------------------------------------------------------------------------
From: Peralta, Rene <rene.peralta at nist.gov>
Subject: CRUNCHY CONTEST: Keccak[r = 40, c = 160, nr = 1], preimage
Date: Wed, March 6, 2013 03:11
To: crunchy at noekeon.org
--------------------------------------------------------------------------

Authors: Joan Boyar (University of Southern Denmark)
             Rene Peralta (NIST)

A pre-image of   e9 f5 7f 02 a9 b0 eb d8 44 98

is this padded message (unpadded length is 117)
"\x01\x00\x00\x00\x00\x58\x59\x0e\x59\xbf\x41\x9e\x19\x81\xb6"

The corresponding binary message is

10000000000000000000000000000000000000000001101010011010011100001001101011
1111011000001001111001100110001000000101101



How the result was obtained :

There are no pre-images with 2 blocks. So we produced one with 3 blocks.
- set the first block to anything
- guess the second block (complexity 2^{40}).
- a correct guess can be checked quickly using only linear algebra,
  since the nonlinear part of f used in the squeezing can be inverted.