[en] In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs (ZKP) and multiparty computations (MPC). We managed to find collisions for 3 instances of 91-bit hash functions. The method used is the classic parallel collision search with distinguished points from van Oorshot and Wiener (1994). As this is a general attack on hash functions, it does not exhibit any particular weakness of the chosen hash functions. The crucial part is to optimize the implementations to make the attack cost realistic, and we describe several arithmetic tricks.
Research center :
ULHPC - University of Luxembourg: High Performance Computing
Disciplines :
Computer science
Author, co-author :
Udovenko, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Language :
English
Title :
Optimized Collision Search for STARK-Friendly Hash Challenge Candidates
Publication date :
January 2020
Focus Area :
Security, Reliability and Trust
FnR Project :
FNR11684537 - Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts, 2017 (01/08/2018-31/07/2021) - Alex Biryukov