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 o...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/182551 |
| _version_ | 1826115763243581440 |
|---|---|
| author | Liu, Fukang Koschatko, Katharina Grassi, Lorenzo Yan, Hailun Chen, Shiyao Banik, Subhadeep Meier, Willi |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Liu, Fukang Koschatko, Katharina Grassi, Lorenzo Yan, Hailun Chen, Shiyao Banik, Subhadeep Meier, Willi |
| author_sort | Liu, Fukang |
| collection | NTU |
| description | 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. |
| first_indexed | 2025-03-09T11:28:22Z |
| format | Journal Article |
| id | ntu-10356/182551 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-03-09T11:28:22Z |
| publishDate | 2025 |
| record_format | dspace |
| spelling | ntu-10356/1825512025-02-10T15:36:13Z Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith Liu, Fukang Koschatko, Katharina Grassi, Lorenzo Yan, Hailun Chen, Shiyao Banik, Subhadeep Meier, Willi School of Physical and Mathematical Sciences Digital Trust Centre Computer and Information Science Mathematical Sciences Tip5/Tip4/Tip4 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. Info-communications Media Development Authority (IMDA) National Research Foundation (NRF) Published version Fukang Liu has been supported by JSPS KAKENHI Grant Numbers JP22K21282,JP24K20733, as well as the commissioned research (No. JPJ012368C05801) by NationalInstitute of Information and Communications Technology (NICT). Lorenzo Grassi hasbeen supported by the Ethereum Foundation via the Academic Grant Program 2024,and by the German Research foundation (DFG) within the framework of the ExcellenceStrategy of the Federal Government and the States – EXC 2092 CaSa. Hailun Yanhas been supported by the National Key Research and Development Program of China(2022YFB2701900) and the National Natural Science Foundation of China (62202444).This research is supported by the National Research Foundation, Singapore and InfocommMedia Development Authority under its Trust Tech Funding Initiative. 2025-02-10T06:01:27Z 2025-02-10T06:01:27Z 2024 Journal Article Liu, F., Koschatko, K., Grassi, L., Yan, H., Chen, S., Banik, S. & Meier, W. (2024). Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith. IACR Transactions On Symmetric Cryptology, 2024(4), 97-137. https://dx.doi.org/10.46586/tosc.v2024.i4.97-137 2519-173X https://hdl.handle.net/10356/182551 10.46586/tosc.v2024.i4.97-137 4 2024 97 137 en IACR Transactions on Symmetric Cryptology © 2024 Fukang Liu, Katharina Koschatko, Lorenzo Grassi, Hailun Yan, Shiyao Chen, Subhadeep Banik, Willi Meier. This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf |
| spellingShingle | Computer and Information Science Mathematical Sciences Tip5/Tip4/Tip4 Monolith Liu, Fukang Koschatko, Katharina Grassi, Lorenzo Yan, Hailun Chen, Shiyao Banik, Subhadeep Meier, Willi Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith |
| title | Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith |
| title_full | Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith |
| title_fullStr | Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith |
| title_full_unstemmed | Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith |
| title_short | Opening the blackbox: collision attacks on round-reduced Tip5, Tip4, Tip4' and monolith |
| title_sort | opening the blackbox collision attacks on round reduced tip5 tip4 tip4 and monolith |
| topic | Computer and Information Science Mathematical Sciences Tip5/Tip4/Tip4 Monolith |
| url | https://hdl.handle.net/10356/182551 |
| work_keys_str_mv | AT liufukang openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith AT koschatkokatharina openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith AT grassilorenzo openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith AT yanhailun openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith AT chenshiyao openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith AT baniksubhadeep openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith AT meierwilli openingtheblackboxcollisionattacksonroundreducedtip5tip4tip4andmonolith |