# 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 [e-mail] 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](https://www.esat.kuleuven.be/cosic/publications/article-3259.pdf)

* $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](https://www.esat.kuleuven.be/cosic/publications/article-3259.pdf))
2. Security level: we substitute $\alpha,2N/3,m$ into the Groebner basis complexity estimate.

### 2.2 Poseidon

[Design Spec](https://eprint.iacr.org/2019/458.pdf)
* $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](https://eprint.iacr.org/2016/492.pdf)
* $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](https://eprint.iacr.org/2021/1038.pdf)

#### 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](https://gist.github.com/khovratovich/97f33072e709c06ba07f70fa1734b253)
* 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)$