home

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.

Algorithm

Implementaion

Common

Vision
+
Rescue

Starkad
+
Poseidon

GMiMCerf

MiMCHash

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

MiMCHash n≈90, m=2, c=1, r=1

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). 

Contact us