Algebraic Hash Function Bounties

Common Rules

  • Task: find \(X_1,X_2,Y_1,Y_2\in F_p\) such that
    \[ (X_1,X_2,0)\xrightarrow{Hash} (Y_1,Y_2,0) \]
    where Hash is one of function-parameter sets from 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.

  • All Easy and Medium submissions will be rewarded. Hard bounties are rewarded only till the bounty budget is exhausted.

  • Total Bounty Budget 30 ETH.

  • Bounties are fixed on November 1st 2021.

2. Concrete Functions

2.1 Rescue Prime

Design Spec

  • \(p=18446744073709551557\approx 2^{64}\)
  • \(m=3\)
  • \(\alpha=3\)
  • Brute force attack complexity \(2^{64}\)
Category Parameters Security Level (bits) Estimated Attack Cost Bounty Real Attack Cost
Easy \(N=4,m=3\) 25 \(2^{39}\) $2000 \(2^{43}\) (4 days)
Easy \(N=6,m=2\) 25 \(2^{41}\) $4000 est. \(2^{53}\)
Medium \(N=7,m=2\) 29 \(2^{49}\) $6000 est. \(2^{62}\)
Medium \(N=5,m=3\) 30 \(2^{51}\) $12000 est. \(2^{57}\)
Hard \(N=8,m=2\) 33 \(2^{56}\) $26000 est. \(2^{72}\)

How we obtained security level and attack cost

  1. Attack cost: we substitute \(\alpha,N,m\) into the Groebner basis complexity estimate (Section 2.5 of the spec)
  2. Security level: we substitute \(\alpha,2N/3,m\) into the Groebner basis complexity estimate.

2.2 Poseidon

Design Spec

  • \(p=18446744073709551557\approx 2^{64}\)
  • \(t=3\)
  • \(\alpha=3\)
  • \(R_F=8\)
  • Number of partial rounds \(R_P\)
Category Parameters Security Level (bits) Estimated Attack Cost Bounty Real Attack Cost
Medium \(R_P=3\) 8 \(2^{40}\) $2000 \(2^{26}\) (1 sec)
Medium \(R_P=8\) 16 \(2^{49}\) $4000 \(2^{35}\) (13 min)
Hard \(R_P=13\) 24 \(2^{58}\) $6000 \(2^{44}\) (36 hr)
Hard \(R_P=19\) 32 \(2^{69}\) $12000 est. \(2^{54}\)
Hard \(R_P=24\) 40 \(2^{77}\) $26000 est. \(2^{62}\)

2.3 Feistel-MiMC

Design Spec

  • \(p=18446744073709551557\approx 2^{64}\).
  • \(\alpha=3\)
  • Task: find \(X,Y\) such that Feistel-MiMC\((X,0)=(Y,0)\)
  • Number of rounds \(r\)
Category Parameters Security Level (bits) Estimated Attack Cost Bounty Real Attack Cost
OLD \(r=14\) 12 \(2^{24}\) $6000 \(2^{33}\) (3 min)
OLD \(r=18\) 15 \(2^{32}\) $12000 \(2^{40}\) (6hr)
Easy \(r=22\) 18 \(2^{36}\) $2000 est. \(2^{47}\)
Easy \(r=25\) 20 \(2^{40}\) $4000 est. \(2^{52}\)
Medium \(r=30\) 24 \(2^{48}\) $6000 est. \(2^{60}\)
Hard \(r=35\) 28 \(2^{56}\) $12000
Hard \(r=40\) 32 \(2^{64}\) $26000

Notes on estimated attack cost:

  • Full 64-bit security requires 81 rounds (\(64\cdot \log_3 4\), Section 2.1) ;
  • We are not aware of anything better than equation solving which costs about \(3^r\) for \(r\) rounds.

2.4 Reinforced Concrete

Design Spec

Full Hash Challenges

Category Parameters \(\log_2(p)\) Security Level (bits) Estimated Attack Cost Bounty Real Attack Cost
Easy \(p=281474976710597\) 48 24 \(2^{48}\) $4000
Medium \(p=72057594037926839\) 56 28 \(2^{56}\) $6000
Hard \(p=18446744073709551557\) 64 32 \(2^{64}\) $12000

Decomposition parameters:

Decomposition program

  • Easy:
    \begin{align} &s_1 =267,\; s_2= 267,\; s_3 = 267,\;s_4 = 244,\;s_5=258,\;s_6=235,\;v=223.\\ &f(x)=(x==0)?0:1/x\pmod{v} \end{align}
    \((\alpha_1,\alpha_2,\beta_1,\beta_2)=(1,2,3,4)\)
  • Medium:
    \begin{align} &s_1 =638,\; s_2= 659,\; s_3 = 635,\;s_4 = 646,\;s_5=659,\;s_6=634,\;v=617.\\ &f(x)=(x==0)?0:1/x\pmod{v} \end{align}
    \((\alpha_1,\alpha_2,\beta_1,\beta_2)=(1,3,2,4)\)
  • Hard:
    \begin{align} &s_1 =570,\; s_2= 577,\; s_3 = 549,\;s_4 = 579,\;s_5=553,\;s_6=577,\;s_7=553,\;v=541.\\ &f(x)=(x==0)?0:1/x\pmod{v} \end{align}
    \((\alpha_1,\alpha_2,\beta_1,\beta_2)=(1,3,2,4)\)
Select a repo