# Using Automatic Generation of Relaxation Constraints to Improve the Preimage Attack on 39-step MD4

arXiv: https://arxiv.org/abs/1802.06940 · HTML: https://mlsanity.com/paper/1802.06940/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2018.

## Built on by (most cited first, 3 of 3)

- [Inverting Cryptographic Hash Functions via Cube-and-Conquer](https://mlsanity.com/paper/2212.02405/) (2022)
- [Decomposing Hard SAT Instances with Metaheuristic Optimization](https://mlsanity.com/paper/2312.10436/) (2023)
- [Efficient Parallel Algorithm for Decomposing Hard CircuitSAT Instances](https://mlsanity.com/paper/2602.17130/) (2026)

## Abstract (arXiv)

In this paper we construct preimage attack on the truncated variant of the MD4 hash function. Specifically, we study the MD4-39 function defined by the first 39 steps of the MD4 algorithm. We suggest a new attack on MD4-39, which develops the ideas proposed by H. Dobbertin in 1998. Namely, the special relaxation constraints are introduced in order to simplify the equations corresponding to the problem of finding a preimage for an arbitrary MD4-39 hash value. The equations supplemented with the relaxation constraints are then reduced to the Boolean Satisfiability Problem (SAT) and solved using the state-of-the-art SAT solvers. We show that the effectiveness of a set of relaxation constraints can be evaluated using the black-box function of a special kind. Thus, we suggest automatic method of relaxation constraints generation by applying the black-box optimization to this function. The proposed method made it possible to find new relaxation constraints that contribute to a SAT-based preimage attack on MD4-39 which significantly outperforms the competition.