  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.
