Eprint first made available on ORBilu (E-prints, Working papers and Research blog)
Optimized Collision Search for STARK-Friendly Hash Challenge Candidates
Udovenko, Aleksei


Full Text
Author preprint (467.37 kB)

All documents in ORBilu are protected by a user license.

Send to


Keywords :
Symmetric cryptography; Hash functions; Cryptanalysis; Multiparty Computation
Abstract :
[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 :
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
Funders :
FNR - Fonds National de la Recherche [LU]
Available on ORBilu :
since 31 January 2020


Number of views
237 (13 by Unilu)
Number of downloads
249 (8 by Unilu)


Similar publications

Contact ORBilu