The Keccak Crunchy Crypto Collision and Pre-image Contest

This page specifies the challenges, defines the rules and reports on the status of the Keccak Crunchy Crypto Collision and Pre-image Contest.

Summary of the results: The best preimage solution was on 4 rounds and was submitted by Meicheng Liu and Jian Guo in December 2016. The best collision was on 6 rounds and was submitted by Ling Song, Guohong Liao and again Jian Guo in February 2017. Remarkably, the smaller versions are harder to break. Although they have a smaller state, they offer much less degrees of freedom, especially relative to the capacity that is the same for all versions.

Rules

We present challenges for reduced-round Keccak instances, namely Keccak[c=160, r=b-c] with b ≥ 200:

  • The capacity is fixed to 160 bits: this implies a security level of 280 against generic collision search.
  • The width b of Keccak-f[b] is in {200, 400, 800, 1600}: the width values that support the chosen capacity.
  • The number of rounds nr ranges from 1 to 12.
  • The submitter is free to choose the subsequence of consecutive rounds of Keccak-f[b], e.g., the nr first rounds, the nr last rounds or nr rounds starting anywhere. This impacts the values of the round constants in the reduced-round Keccak-f[b].

For each of these Keccak instances there are two challenges:

  • generating a collision in the output truncated to 160 bits;
  • generating a pre-image of an output truncated to 80 bits.

To be informed of solutions, we suggest all interested people to subscribe to the crypto-competitions -at- googlegroups.com mailing list. Solutions shall be sent to that mailing list with:

  • subject "[CRUNCHY CONTEST] nr rounds, width b, challenge type", with nr and b having the corresponding values and challenge type either "collision" or "pre-image";
  • in the body:
    • names and affiliations of authors;
    • round index of the first round of the reduced-round variant of Keccak-f[b];
    • colliding messages or pre-image in hexadecimal notation;
    • textual summary of how the result was obtained.

The prize money is distributed in the following way:

  • There is one prize per challenge.
  • For a given challenge, only the first received solution gets a prize.
  • The prize for a challenge for nr rounds is nr×10 €.

KeccakTools contains support for the validation of solutions (see file KeccakCrunchyContest.cpp ).

Challenges and status

We list below the challenges and the status per number of rounds.

Pre-image challenges

FunctionPre-imageImage
Keccak[r = 40, c = 160, nr = 1]found by Joan Boyar and Rene Peraltae9 f5 7f 02 a9 b0 eb d8 44 98
Keccak[r = 240, c = 160, nr = 1]found by Paweł Morawieckid9 d6 d3 c8 4d 1a c1 d7 5f 96
Keccak[r = 640, c = 160, nr = 1]found by Paweł Morawiecki3f 41 9f 88 1c 42 cf fc 5f d7
Keccak[r = 1440, c = 160, nr = 1]found by Paweł Morawiecki0f 0a f7 07 4b 6a bd 48 6f 80
Keccak[r = 40, c = 160, nr = 2]?02 4a 55 18 e1 e9 5d b5 32 19
Keccak[r = 240, c = 160, nr = 2]found by Paweł Morawiecki7a b8 98 1a da 8f db 60 ae fd
Keccak[r = 640, c = 160, nr = 2]found by Paweł Morawiecki82 8d 4d 09 05 0e 06 35 07 5e
Keccak[r = 1440, c = 160, nr = 2]found by Paweł Morawiecki63 90 22 0e 7b 5d 32 84 d2 3e
Keccak[r = 40, c = 160, nr = 3]?d8 ed 85 69 2a fb ee 4c 99 ce
Keccak[r = 240, c = 160, nr = 3]found by Yao Sun and Ting Li5c 9d 5e 4b 38 5e 9c 4f 8e 2e
Keccak[r = 640, c = 160, nr = 3]found by Jian Guo and Meicheng Liu00 7b b5 c5 99 80 66 0e 02 93
Keccak[r = 1440, c = 160, nr = 3]found by Jian Guo and Meicheng Liu06 25 a3 46 28 c0 cf e7 6c 75
Keccak[r = 40, c = 160, nr = 4]?74 2c 7e 3c d9 46 1d 0d 03 4e
Keccak[r = 240, c = 160, nr = 4]?0d d2 5e 6d e2 9a 42 ad b3 58
Keccak[r = 640, c = 160, nr = 4]?75 1a 16 e5 e4 95 e1 e2 ff 22
Keccak[r = 1440, c = 160, nr = 4]found by Meicheng Liu and Jian Guo7d aa d8 07 f8 50 6c 9c 02 76
Keccak[r = 40, c = 160, nr = 5]?e0 53 f9 64 4f aa b1 da 31 1b
Keccak[r = 240, c = 160, nr = 5]?8d f4 44 09 b4 6f b8 c6 1b c4
Keccak[r = 640, c = 160, nr = 5]?6e f2 61 6f eb b9 9b 1f 70 ed
Keccak[r = 1440, c = 160, nr = 5]?65 3b c0 f8 7d 26 4f 08 57 d0
Keccak[r = 40, c = 160, nr = 6]?e5 1c 00 c4 8e d5 db 07 02 b3
Keccak[r = 240, c = 160, nr = 6]?57 16 e7 01 ef 67 cc 04 48 b0
Keccak[r = 640, c = 160, nr = 6]?5f 9e 63 88 4f 2e 94 f1 a1 0e
Keccak[r = 1440, c = 160, nr = 6]?d6 05 33 5e dc e7 d2 ca f4 10
Keccak[r = 40, c = 160, nr = 7]?95 93 25 c5 67 73 a7 4a 43 c6
Keccak[r = 240, c = 160, nr = 7]?9c ec ce 92 93 8a ea ba 26 af
Keccak[r = 640, c = 160, nr = 7]?a4 c1 35 21 90 12 aa c8 08 ed
Keccak[r = 1440, c = 160, nr = 7]?5e 0d 17 9c 50 c2 93 0c 0d 76
Keccak[r = 40, c = 160, nr = 8]?05 4d da f1 b9 b5 9b 9a 60 bf
Keccak[r = 240, c = 160, nr = 8]?19 c2 d8 ff 69 e5 66 a5 07 c9
Keccak[r = 640, c = 160, nr = 8]?f4 83 5d 80 2a ab c5 be 75 8e
Keccak[r = 1440, c = 160, nr = 8]?34 e1 81 23 29 d5 e8 9d 67 1a
Keccak[r = 40, c = 160, nr = 9]?5e d1 a9 c1 84 eb 72 b9 45 46
Keccak[r = 240, c = 160, nr = 9]?78 d6 58 de c5 01 ee d6 3b 1e
Keccak[r = 640, c = 160, nr = 9]?2e dd 24 58 7f 22 5c 69 6e 61
Keccak[r = 1440, c = 160, nr = 9]?ca 18 6a 0f e1 26 ed be 2c a6
Keccak[r = 40, c = 160, nr = 10]?c3 8f 61 8f 53 a9 6e 4f fd 53
Keccak[r = 240, c = 160, nr = 10]?46 68 1a 4a 3a 97 5b 16 2a c4
Keccak[r = 640, c = 160, nr = 10]?b8 6d b6 0f f7 23 18 76 6e ef
Keccak[r = 1440, c = 160, nr = 10]?df 7b f3 01 7c d3 22 a4 6c 31
Keccak[r = 40, c = 160, nr = 11]?19 f8 e6 bc 5d 71 41 77 65 95
Keccak[r = 240, c = 160, nr = 11]?12 9e 94 0f 63 43 00 f6 b4 14
Keccak[r = 640, c = 160, nr = 11]?a2 49 0a 3e 68 d5 d0 2d d4 aa
Keccak[r = 1440, c = 160, nr = 11]?69 c9 4f 0a e8 30 40 26 b3 da
Keccak[r = 40, c = 160, nr = 12]?20 68 65 eb 08 b4 2a 66 63 e1
Keccak[r = 240, c = 160, nr = 12]?85 5a 86 45 96 c5 1c af 7d 3d
Keccak[r = 640, c = 160, nr = 12]?68 ed de 13 a4 79 e1 47 71 bd
Keccak[r = 1440, c = 160, nr = 12]?bf 8c 82 63 a9 87 59 5b 21 c0
Table 1: Pre-image challenges and status

Collision challenges

FunctionInputs
Keccak[r = 40, c = 160, nr = 1]?
Keccak[r = 240, c = 160, nr = 1]found by Paweł Morawiecki
Keccak[r = 640, c = 160, nr = 1]found by Paweł Morawiecki
Keccak[r = 1440, c = 160, nr = 1]found by Paweł Morawiecki and by Alexandre Duc, Jian Guo, Thomas Peyrin and Lei Wei
Keccak[r = 40, c = 160, nr = 2]?
Keccak[r = 240, c = 160, nr = 2]found by Paweł Morawiecki
Keccak[r = 640, c = 160, nr = 2]found by Paweł Morawiecki
Keccak[r = 1440, c = 160, nr = 2]found by Paweł Morawiecki and by Alexandre Duc, Jian Guo, Thomas Peyrin and Lei Wei
Keccak[r = 40, c = 160, nr = 3]?
Keccak[r = 240, c = 160, nr = 3](closed)
Keccak[r = 640, c = 160, nr = 3](closed)
Keccak[r = 1440, c = 160, nr = 3]found by Itai Dinur, Orr Dunkelman and Adi Shamir
Keccak[r = 40, c = 160, nr = 4]?
Keccak[r = 240, c = 160, nr = 4](closed) yet found by Stefan Kölbl, Florian Mendel, Martin Schläffer and Tomislav Nad
Keccak[r = 640, c = 160, nr = 4](closed) yet found by Stefan Kölbl, Florian Mendel, Martin Schläffer and Tomislav Nad
Keccak[r = 1440, c = 160, nr = 4]found by Itai Dinur, Orr Dunkelman and Adi Shamir
Keccak[r = 40, c = 160, nr = 5]?
Keccak[r = 240, c = 160, nr = 5]?
Keccak[r = 640, c = 160, nr = 5]found by Kexin Qiao, Ling Song, Meicheng Liu, and Jian Guo
Keccak[r = 1440, c = 160, nr = 5]found by Kexin Qiao, Ling Song, Meicheng Liu, and Jian Guo
Keccak[r = 40, c = 160, nr = 6]?
Keccak[r = 240, c = 160, nr = 6]?
Keccak[r = 640, c = 160, nr = 6]?
Keccak[r = 1440, c = 160, nr = 6]found by Ling Song, Guohong Liao and Jian Guo
Keccak[r = 40, c = 160, nr = 7]?
Keccak[r = 240, c = 160, nr = 7]?
Keccak[r = 640, c = 160, nr = 7]?
Keccak[r = 1440, c = 160, nr = 7]?
Keccak[r = 40, c = 160, nr = 8]?
Keccak[r = 240, c = 160, nr = 8]?
Keccak[r = 640, c = 160, nr = 8]?
Keccak[r = 1440, c = 160, nr = 8]?
Keccak[r = 40, c = 160, nr = 9]?
Keccak[r = 240, c = 160, nr = 9]?
Keccak[r = 640, c = 160, nr = 9]?
Keccak[r = 1440, c = 160, nr = 9]?
Keccak[r = 40, c = 160, nr = 10]?
Keccak[r = 240, c = 160, nr = 10]?
Keccak[r = 640, c = 160, nr = 10]?
Keccak[r = 1440, c = 160, nr = 10]?
Keccak[r = 40, c = 160, nr = 11]?
Keccak[r = 240, c = 160, nr = 11]?
Keccak[r = 640, c = 160, nr = 11]?
Keccak[r = 1440, c = 160, nr = 11]?
Keccak[r = 40, c = 160, nr = 12]?
Keccak[r = 240, c = 160, nr = 12]?
Keccak[r = 640, c = 160, nr = 12]?
Keccak[r = 1440, c = 160, nr = 12]?
Table 2: Collision challenges and status