New algorithm for relaxation constrains generation in the inversion problem of MD4-39

The paper presents the preimage attack on 39-step variant of the MD4 cryptographic hash-function (MD4-39) using new approach which can be considered as a development of the ideas proposed earlier by H. Dobbertin. Particularly, we search for special relaxation constraints which are used to simplify the equations corresponding to the problem of finding a preimage for a random MD4-39 hash value. These equations supplemented with the relaxation constraints are reduced to the Boolean Satisfiability Problem (SAT) and then solved using the SAT solvers. We suggest a new method for automatic generation of relaxation constraints by applying the black-box optimization to the function of a special kind, which evaluates the effectiveness of a set of relaxation constraints. The proposed method allows to find new relaxation constraints using which we manage to construct preimage attack on MD4-39 which in dozens of times outperforms the best known attack for considered function.