# Bounties Extra Material

## RC hash Groebner

#### Gröbner Basis Challenges (not yet declared)
* Various small primes $p$ and their decomposition into $n=2,3$ buckets
* $s_1,\ldots,s_n$ are the sizes of the small S-Boxes
* Algebraic model of $\texttt{Concrete}$ - $\texttt{Bars}$ - $\texttt{Concrete}$ in the CICO setting; $6n+8$ equations with $6n+6$ variables
* $d_{reg}$ is degree of regularity of an overdefined equation system given by the index of the first non-positive coefficient in
\begin{equation*}
S_{k,l}(z) = \frac{\prod_{i=1}^k (1-z^{d_i})}{(1-z)^l},
\end{equation*}
where $k$ denotes the number of equations, $d_i$ the degree of equation $1\leq i\leq k$ and $l$ the number of variables
* $C_{bit}$ ($d_{reg}$) is the bit complexity estimate of GB computation with (theoretical) degree of regularity
* $C_{bit}$ ($d_{mag}$) is the bit complexity estimate of GB computation with (extrapolated) degree $d_{mag}$ reached by Magma; table uses $d_{reg} = 3\cdot d_{mag}$
* Est. $C_{bit}$ is the estimated (and extrapolated) bit complexity from available data points; table uses $C_{bit}$ ($d_{mag}$) $=2$ $\cdot$ Est. $C_{bit}$

| p | $s_1,\ldots,s_n$ | $d_{reg}$ | Est. $d_{mag}$ | \# vars | $C_{bit}$ ($d_{reg}$) | $C_{bit}$ ($d_{mag}$) | Est. $C_{bit}$ |
| - | - | - | - | - | - | - | - |
| 41 | [6, 7] | 25 | 9 | 18 | 79 | 45 | 23 |
| 47 | [8, 8] | 33 | 11 | 18 | 90 | 51 | 26 |
| 71 | [9, 8] | 35 | 12 | 18 | 92 | 53 | 27 |
| 53 | [9, 9] | 38 | 13 | 18 | 96 | 56 | 28 |
| 71 | [10, 9] | 40 | 14 | 18 | 98 | 58 | 29 |
| 79 | [10, 10] | 43 | 15 | 18 | 101 | 60 | 30 |
| 109 | [11, 10] | 45 | 15 | 18 | 103 | 60 | 30 |
| 97 | [11, 11] | 48 | 16 | 18 | 106 | 63 | 32 |
| 131 | [12, 11] | 50 | 17 | 18 | 107 | 65 | 33 |
| 107 | [12, 12] | 53 | 18 | 18 | 110 | 67 | 34 |
| 107 | [13, 12] | 55 | 19 | 18 | 112 | 69 | 35 |
| 181 | [14, 13] | 60 | 20 | 18 | 116 | 70 | 35 |
| 167 | [14, 14] | 63 | 21 | 18 | 118 | 72 | 36 |
| 167 | [15, 14] | 65 | 22 | 18 | 119 | 74 | 37 |
| 193 | [15, 15] | 68 | 23 | 18 | 121 | 76 | 38 |
| 239 | [16, 16] | 72 | 24 | 18 | 124 | 77 | 39 |
| 271 | [16, 17] | 75 | 25 | 18 | 126 | 79 | 40 |
| 269 | [17, 17] | 77 | 26 | 18 | 127 | 80 | 40 |
| 379 | [20, 19] | 90 | 30 | 18 | 134 | 86 | 43 |
| 359 | [20, 20] | 92 | 31 | 18 | 135 | 87 | 44 |
| 419 | [20, 21] | 95 | 32 | 18 | 137 | 89 | 45 |
| 461 | [21, 22] | 100 | 34 | 18 | 139 | 91 | 46 |
| 439 | [22, 22] | 102 | 34 | 18 | 140 | 91 | 46 |
| 503 | [24, 23] | 110 | 37 | 18 | 144 | 95 | 48 |
| 599 | [25, 25] | 117 | 39 | 18 | 147 | 97 | 49 |
| 647 | [26, 27] | 125 | 42 | 18 | 150 | 100 | 50 |
| 727 | [28, 27] | 130 | 44 | 18 | 152 | 102 | 51 |
| 839 | [30, 30] | 142 | 48 | 18 | 156 | 106 | 53 |
| 929 | [31, 30] | 144 | 48 | 18 | 157 | 106 | 53 |
| 929 | [31, 31] | 147 | 49 | 18 | 158 | 107 | 54 |
| 929 | [32, 31] | 149 | 50 | 18 | 159 | 107 | 54 |
| 1087 | [34, 34] | 162 | 54 | 18 | 163 | 111 | 56 |
| 1087 | [35, 34] | 164 | 55 | 18 | 163 | 112 | 56 |
| 1117 | [35, 35] | 167 | 56 | 18 | 164 | 113 | 57 |
| 1151 | [35, 36] | 169 | 57 | 18 | 165 | 113 | 57 |
| 1187 | [36, 36] | 172 | 58 | 18 | 166 | 114 | 57 |
| 1481 | [40, 39] | 189 | 63 | 18 | 170 | 118 | 59 |
| 1559 | [40, 40] | 192 | 64 | 18 | 171 | 119 | 60 |
| 1597 | [41, 41] | 197 | 66 | 18 | 172 | 120 | 60 |
| 1847 | [44, 44] | 212 | 71 | 18 | 176 | 123 | 62 |
| 1889 | [45, 45] | 216 | 72 | 18 | 177 | 124 | 62 |
| 251 | [6, 6, 7] | 38 | 13 | 24 | 113 | 64 | 32 |
| 293 | [7, 7, 7] | 43 | 15 | 24 | 120 | 70 | 35 |
| 433 | [8, 8, 7] | 48 | 16 | 24 | 126 | 72 | 36 |
| 383 | [8, 8, 8] | 51 | 17 | 24 | 129 | 75 | 38 |
| 647 | [9, 9, 9] | 58 | 20 | 24 | 137 | 82 | 41 |
| 647 | [10, 9, 9] | 61 | 21 | 24 | 140 | 84 | 42 |
| 859 | [11, 11, 10] | 71 | 24 | 24 | 149 | 90 | 45 |
| 2027 | [13, 13, 13] | 89 | 30 | 24 | 162 | 101 | 51 |
| 2339 | [14, 14, 13] | 95 | 32 | 24 | 166 | 104 | 52 |
| 2351 | [14, 14, 14] | 97 | 33 | 24 | 167 | 106 | 53 |
| 3359 | [15, 15, 15] | 105 | 35 | 24 | 172 | 109 | 55 |
| 3329 | [16, 16, 15] | 110 | 37 | 24 | 175 | 112 | 56 |
| 3583 | [16, 16, 16] | 113 | 38 | 24 | 177 | 113 | 57 |
| 3583 | [17, 16, 16] | 115 | 39 | 24 | 178 | 115 | 58 |
| 4591 | [17, 17, 16] | 118 | 40 | 24 | 180 | 116 | 58 |
| 7219 | [20, 19, 19] | 138 | 46 | 24 | 190 | 124 | 62 |
| 7561 | [20, 20, 19] | 141 | 47 | 24 | 191 | 125 | 63 |
| 7159 | [20, 20, 20] | 144 | 48 | 24 | 192 | 126 | 63 |

## Supplementary Materials

### Interpolation Attack

Suppose the inner sponge permutation $F$ of the hash function $H$ has degree $D$. Then a preimage to $H(\cdot)=Y$ can be found in about $D\log^3 D$ time as follows:
* Evaluate $F$ on $D+1$ points in time $D$.
* Obtain polynomial coefficients for $f(X)$ being interpolant of $F$ using FFT in time $D\log D$.
* Solve $f(X)=Y$ in $D\log^3 D$ time using multiplication estimate $M(n)=n\log n$
* Check at most $D$ solutions to the above in time $D$.

As a concrete example, roots for $D\approx 2^{17}, q\approx 2^{26}$ were found in 0.8 ms, i.e. in about $2^{10}$ calls to $F$ (about $2^{15}$ field operations). We have
$$
D\log^3 D \approx 2^{29}
$$
so the real complexity is closer to $D$ rather than to $D\log^3 D$.

## Screenshots

von zur Gathen, Gerhard "Modern Computer Algebra" (2013)


Roy-Andreeva-Sauer "Interpolation Cryptanalysis of Unbalanced
Feistel Networks with Low Degree Round
Functions" (2020)