STARK-Friendly Hash Challenge
StarkWare Giving Away ETH! (fine print below)
The Ethereum Foundation (EF) asked StarkWare to recommend a STARK-Friendly Hash (SFH). Following that, StarkWare will release an efficient, production-quality software implementation for a STARK prover and verifier under a license approved by EF during the 3rd quarter of 2020. This software will subsequently be used by the Ethereum developers’ ecosystem (more details here).
The StarkWare hash challenge is a public competition to evaluate the security of proposed SFH candidates. The challenge is proposed at four security levels: low-security, medium-security, target-security, and high-security in multiple scenarios we are interested in.
We invite all interested parties to take part in the challenge and try to solve the puzzles provided. In return, we will be giving away ETH as a reward to the first person to solve each puzzle. Not the first to solve the puzzle? Don’t worry, there may still be prizes for you.
Details
Each of the four security levels consists of several puzzles to solve and they will be released according to the tentative timeline specified below. for each puzzle, we challenge you to find a pair of distinct values mapping to the same output (collision attack). For some of the puzzles we will encode the puzzle as a smart contract (released according to tentative timeline specified below), so you can claim your prize easily. In other cases we will ask you to send us an email with your solution.
In addition to the prizes we are offering for directly solving the puzzles, we will reward, at our discretion, any new information you will be providing us with (see “I Solved a Puzzle” section below).
Algorithms
The challenge features three families of algorithms developed by leading researchers in the field of symmetric-key cryptography:
All these hash functions were vetted by leading cryptanalysts and no obvious weaknesses were found in them. Now, before moving on to the next step in our plan, we want to crowdsource the cryptanalytic effort and hear what YOU can do with them.
Cryptanalysis
In the first week of November 2019, a committee of expert cryptanalysts, headed by Prof. Anne Canteaut, convened in Paris to judge the suggested hash functions. The committee deliberated for 3 days and produced a comprehensive report on the soundness and possible attack vectors of each algorithm.
STARK Friendly Hash -- Survey And Recommendation
Eli Ben-Sasson, Lior Goldberg and David Levit
Report on the Security of STARK-friendly Hash Functions
Anne Canteaut (ed.), Tim Beyne, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaetan Leurent, María Naya Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, Friedrich Wiemer
Report On The Security Of The Rescue Hash Function
Tim Beyne, Anne Canteaut, Gregor Leander, María Naya-Plasencia, Léo Perrin and Friedrich Wiemer
Farther Reading
Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems
Tim Beyne and Anne Canteaut and Itai Dinur and Maria Eichlseder and Gregor Leander and Gaëtan Leurent and María Naya-Plasencia and Léo Perrin and Yu Sasaki and Yosuke Todo and Friedrich Wiemer
Mind the Middle Layer: The HADES Design Strategy Revisited
Nathan Keller and Asaf Rosemarin
The Challenge
Each security level consists of 2—6 puzzles featuring different field sizes (n), capacity (c), rate (r), and number of field elements per state (m=c+r). In each puzzle, all candidate algorithms are compared with respect to the same parameter set. The exact parameters can be found in our reference implementation, released according to the tentative timeline specified below.
Finding a Collision
A collision over a value y with respect to a hash function H(*) is a pair of distinct values x and x’ such that H(x) = H(x’). Collisions must exist because H(*) has more inputs than outputs (this is the Pigeonhole Principle). We do not know of any specific collisions for the functions we’re considering. But maybe you can help us find them.
I Solved A Puzzle, Now What?
First of all – congratulations! Assuming you’re the first to it, there are two ways for you to claim your prize and everlasting glory: the simple way and the cool one. The simple way, which applies to all challenges, is to email us the colliding pair (at [email protected]). Your email must include, in addition to the colliding pair, the name of the function (e.g., Starkad), the field size, and the parameters m, c, and r so we can easily identify which puzzle you solved. You should also tell us if you want us to add your name to our website and the wallet address to which we should send the ETH to.
We’ll then check it, send you the prize, and update the website with your name (that’s the everlasting glory part). The cool way, which will apply only to some of the puzzles (the ones defined over prime fields) is to feed your collision pair directly to an Ethereum smart contract and be automatically rewarded by it.
Fine print: (1) Rewards are guaranteed only to the very first solver of each challenge and only if the solution is submitted before the end of March 2020. (2) Even if you are not the first to solve, if you have interesting additional information to supply to the public (such as new attack vectors), please share it with us (at [email protected]) and we may decide (at our discretion) to reward you.
Timeline
15 Aug 2019
SFH challenge announced
26 Aug 2019
Reference implementations released
9 Sep 2019
Smart Contracts published
16 Sep 2019
SFH discussion at StarkWare Sessions
31 Mar 2020
SFH challenge ends (and smart contracts expire)
Links to smart contracts and Hall of Fame of collision solvers will appear in the tables below.
Low Security
45 bit
1 Ether for each solution
Medium Security
80 bit
2 Ether for each solution
MiMCHash
n≈160, m=2, c=1, r=1
Target Security
128 bit
4 Ether for each solution
MiMCHash
n≈256, m=2, c=1, r=1
High Security
256 bit
8 Ether for each solution
Our Fields
Our Fields
n≈64
Binary: GF(2)[x] mod x63+x+1
Prime: 261 + 20·232 + 1
n≈80
Binary: GF(2)[x] mod x81+x+1
Prime: 281 + 80·264 + 1
n≈90
Binary: GF(2)[x] mod x63+x+1
Prime: 291 + 5·264 + 1
n≈128
Binary: GF(2)[x] mod x127+x+1
Prime: 2125 + 266·264 + 1
n≈160
Binary: GF(2)[x] mod x161+x18+1
Prime: 2161 + 23·2128 + 1
n≈256
Binary: GF(2)[x] mod x255+x5+x3+x21
Prime: 2253 + 2199 + 1
FAQs
We will not be able to answer all emails. Certain emails will certainly not be answered (including ICO inquiries, token sales and proofs of P=NP).
See the tentative timeline.