Inverting 43-step MD4 via Cube-and-Conquer
Authors: Oleg Zaikin
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this study, 40-, 41-, 42-, and 43-step versions of MD4 are successfully inverted. The problems are reduced to SAT and solved via the Cube-and-Conquer approach. Two algorithms are proposed for this purpose. The first one generates inversion problems for MD4 by adding special constraints. The second one is aimed at finding a proper threshold for the cubing phase of Cube-and-Conquer. While the first algorithm is focused on inverting MD4 and similar cryptographic hash functions, the second one is not area specific and so is applicable to a variety of classes of hard SAT instances. ... Experimental results on inverting the truncated versions of MD4 are given in Section 6. |
| Researcher Affiliation | Academia | Oleg Zaikin Swansea University o.s.zaikin@swansea.ac.uk |
| Pseudocode | Yes | Algorithm 1 Algorithm for inverting MD4 or its truncated version via Dobbertin-like constraints... Algorithm 2 Finding a cutoff threshold with minimal estimated runtime of the conquer phase |
| Open Source Code | Yes | The implementation, as well as all the constructed CNFs are available online at https://github.com/olegzaikin/MD4-CnC. |
| Open Datasets | No | The paper does not use a traditional dataset for training in the machine learning sense that requires public availability. It aims to find preimages for specific hashes (0128 and 1128) for MD4, which are explicitly defined within the paper as the target for inversion. |
| Dataset Splits | No | The paper does not describe dataset splits for training, validation, or testing, as it focuses on inverting cryptographic hash functions rather than training a machine learning model on a dataset with such partitions. |
| Hardware Specification | Yes | All experiments were held on a personal computer equipped with the 12-core CPU AMD 3900X and 48 Gb of RAM. |
| Software Dependencies | Yes | the MARCH CU lookahead solver [Heule et al., 2011]; the KISSAT CDCL solver of version sc2021 [Biere et al., 2021]; |
| Experiment Setup | Yes | As for Algorithm 2, the following parameters were used: the MARCH CU lookahead solver [Heule et al., 2011]; the KISSAT CDCL solver of version sc2021 [Biere et al., 2021]; max t = 5 000 seconds; k = 10; max cubes = 1 000 000; min refuted = 500; N = 1 000; cpu cores = 12. |