Optimized Collision Search for StarkWare Hash Challenge
This repository contains an implementation of the generic collision search method applied to 91-bit hash functions from the StarkWare Hash Challenge.
The attack and optimizations are discussed in the blog post.
The code can be used to break small and large instances of GMiMC-erf and small instance of Poseidon in about 1000-2000 core-days.
Running the attack
The following example is for small instance of GMiMC-erf, which is labelled gmimc1. The other instances are gmimc2 and pos1.
The first step is to compile the code.
$ make gmimc1 take=50 dist=20
takedefines the number of bits in the hash functon (default is 92);
distdefines the number of zero bits in distinguished points (default is 25).
The second step is to run many instances of the program to collect distinguished points:
$ ./gmimc1 [worker_id] worker 1 dist 20 take 50 worker 000000001: 00000000000000000000001 -> 00000000001c82513d00000 ( 318309 calls in 0.90 seconds, 2.8328762 microseconds per permutation call) worker 000000001: 00000004f2c983207d89bd8 -> 000000000003f5516300000 ( 2386364 calls in 6.87 seconds, 2.8805392 microseconds per permutation call) worker 000000001: 0000000d0bf060e183ffbfe -> 0000000000128ed4f400000 ( 78798 calls in 0.23 seconds, 2.9581461 microseconds per permutation call) ...
[worker_id] is an integer seed to randomize the worker.
Finally, the collected pool of distinguished points is checked for a collision:
$ make gmimc1check ... Collision: steps 315173 298519 (0x00000000001bcb0673eaca2, 0, ...) -> 00007e309caf5769 (0x000000000029d327c4c9d54, 0, ...) -> 00007e309caf5769