Paper 2024/1900
Opening the Blackbox: Collision Attacks on Round-Reduced Tip5, Tip4, Tip4' and Monolith
Fukang Liu
, Institute of Science Tokyo, Tokyo, Japan
Katharina Koschatko
, Graz University of Technology, Graz, Austria
Lorenzo Grassi
, Ponos Technology, Zug, Switzerland, Ruhr University Bochum, Bochum, Germany
Hailun Yan, University of Chinese Academy of Sciences, Beijing, China
Shiyao Chen, Digital Trust Centre, Nanyang Technological University, Singapore, Singapore
Subhadeep Banik
, Universita della Svizzera Italiana, Lugano, Switzerland
Willi Meier, University of Applied Sciences and Arts Northwestern Switzerland, Windisch, Switzerland
Abstract
A new design strategy for ZK-friendly hash functions has emerged since the proposal of at CCS 2022, which is based on the hybrid use of two types of nonlinear transforms: the composition of some small-scale lookup tables (e.g., 7-bit or 8-bit permutations) and simple power maps over . Following such a design strategy, some new ZK-friendly hash functions have been recently proposed, e.g., , , and the family. All these hash functions have a small number of rounds, i.e., rounds for , , and , and rounds for (recently published at ToSC 2024/3). Using the composition of some small-scale lookup tables to build a large-scale permutation over - which we call S-box - is a main feature in such designs, which can somehow enhance the resistance against the Gröbner basis attack because this large-scale permutation will correspond to a complex and high-degree polynomial representation over .
As the first technical contribution, we propose a novel and efficient algorithm to study the differential property of this S-box and to find a conforming input pair for a randomly given input and output difference. For comparison, a trivial method based on the use of the differential distribution table (DDT) for solving this problem will require time complexity .
For the second contribution, we also propose new frameworks to devise efficient collision attacks on such hash functions. Based on the differential properties of these S-boxes and the new attack frameworks, we propose the first collision attacks on -round , , and , as well as -round - and -, where the -round attacks on are practical. In the semi-free-start (SFS) collision attack setting, we achieve practical SFS collision attacks on -round , , and . Moreover, the SFS collision attacks can reach up to -round and -round -. As far as we know, this is the first third-party cryptanalysis of these hash functions, which improves the initial analysis given by the designers.
Note: This paper is an extended version of the original paper accepted at ToSC 2024.4. All code is provided in our repository: https://github.com/IAIK/ca-tip5family-monolith.