Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions MD4

In the paper, we propose new preimage attacks on hash-functions MD4-$k$, $k>39$. These attacks, related to the class of guess-and-determine attacks, are based on the idea of inverse backdoor set. We use SAT solvers to solve the cryptanalysis problems weakened by substitution of guessed bits to SAT encodings of the considered functions. The problem of search for an inverse backdoor set with relatively small complexity estimation is considered as a minimization problem of a special pseudo-Boolean function. To solve this problem, we apply several metaheuristic algorithms: tabu search algorithm, (1+1)-$FEA_{\beta}$, and a variant of genetic algorithm. These algorithms produce attacks on the considered functions with close complexity estimations. For the full-round compression function MD4 the best attack is constructed using the genetic algorithm.