Opening the Blackbox: Collision Attacks on Round-Reduced Tip5, Tip4, Tip4’ and Monolith

A new design strategy for ZK-friendly hash functions has emerged since the proposal of Reinforced Concrete 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 Fp. Following such a design strategy, some new ZK-friendly hash functions have been recently proposed, e.g., Tip5, Tip4, Tip4’, and the Monolith family. All these hash functions have a small number of rounds, i.e., 5 rounds for Tip5, Tip4, and Tip4’, and 6 rounds for Monolith (recently published at ToSC 2024/3). Using the composition of some small-scale lookup tables to build a large-scale permutation over Fp – 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 Fp.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 O(p2).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 3-round Tip5, Tip4, and Tip4’, as well as 2-round Monolith-31 and Monolith-64, where the 2-round attacks on Monolith are practical. In the semi-free-start (SFS) collision attack setting, we achieve practical SFS collision attacks on 3-round Tip5, Tip4, and Tip4’. Moreover, the SFS collision attacks can reach up to 4-round Tip4 and 3-round Monolith-64. 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.