[Resource Topic] 2024/1900: Opening the Blackbox: Collision Attacks on Round-Reduced Tip5, Tip4, Tip4' and Monolith

Welcome to the resource topic for 2024/1900

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

Authors: Fukang Liu, Katharina Koschatko, Lorenzo Grassi, Hailun Yan, Shiyao Chen, Subhadeep Banik, Willi Meier

Abstract:

A new design strategy for ZK-friendly hash functions has emerged since the proposal of \mathsf{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 \mathbb{F}_p. Following such a design strategy, some new ZK-friendly hash functions have been recently proposed, e.g., \mathsf{Tip5}, \mathsf{Tip4}, \mathsf{Tip4}' and the \mathsf{Monolith} family. All these hash functions have a small number of rounds, i.e., 5 rounds for \mathsf{Tip5}, \mathsf{Tip4}, and \mathsf{Tip4}', and 6 rounds for \mathsf{Monolith} (recently published at ToSC 2024/3). Using the composition of some small-scale lookup tables to build a large-scale permutation over \mathbb{F}_p - 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 \mathbb{F}_p.

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 \mathcal{O}(p^2).

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 \mathsf{Tip5}, \mathsf{Tip4}, and \mathsf{Tip4}', as well as 2-round \mathsf{Monolith}-31 and \mathsf{Monolith}-64, where the 2-round attacks on \mathsf{Monolith} are practical. In the semi-free-start (SFS) collision attack setting, we achieve practical SFS collision attacks on 3-round \mathsf{Tip5}, \mathsf{Tip4}, and \mathsf{Tip4}'. Moreover, the SFS collision attacks can reach up to 4-round \mathsf{Tip4} and 3-round \mathsf{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.

ePrint: https://eprint.iacr.org/2024/1900

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .