ZK Hash Function Cryptanalysis Bounties 2021

Ethereum Foundation

Help us understand the security of new hash functions better

Terms

  • Task: find X1, X2, Y1, Y2 such that

Perm(X1,X2,0)= (Y1,Y2,0)

where Perm is the inner sponge permutation (bijective mapping) of the hash function the challenge list.

  • Solutions should be sent to Dmitry Khovratovich dmitry.khovratovich@ethereum.org before November 30th 2022.

  • First come first win.

  • Within 1 month after the submission the authors should provide a technical report with the attack description, which should be released to the public domain at latest December 1st 2022. The code should be also made public before this date.

  • Total Bounty Budget -- $200 000.

  • Parameters are fixed on November 23d 2021.


Rescue Prime

Design Spec

  • p=18446744073709551557 ~ 2^64

  • m=3

  • alpha=3

  • Number of rounds N

  • Brute force attack complexity 2^64

We expect that a variant with s bits of security to withstand attacks of complexity up to 2^(1.5s) time (function calls) and memory.

Reference implementation and bounty instances

Feistel-MIMC

Design Spec

  • p=18446744073709551557 ~ 2^64

  • alpha=3

  • Task: find X,Y such that Feistel-MiMC(X,0)=(Y,0)

  • Number of rounds r

  • Brute force attack complexity 2^64

We expect that a variant with s bits of security to withstand attacks of complexity up to 2^(2s) time (function calls) and memory.

The initial parameters were broken and were replaced.

Reference implementation and bounty instances

Poseidon

Design Spec

  • p=18446744073709551557 ~ 2^64

  • d=3

  • t=3

  • Number of full rounds RF=8

  • Number of partial rounds RP varies (see below)

  • Brute force attack complexity 2^64

We expect that a variant with s bits of security to withstand attacks of complexity up to 2^(s+37) time (function calls) and memory.

Reference implementation and bounty instances

Reinforced Concrete

Design Spec

  • Number of layers as in the original design

  • Different prime field

  • The best attack we have found for these variants is exhaustive search.

  • Groebner basis challenges might be declared additionally.

We expect that a variant with s bits of security to withstand attacks of complexity up to 2^(2s) time (function calls) and memory.

Decomposition and alpha/beta values

Reference implementation and bounty instances