Computational methods in discrete mathematics

The inversion of cryptographic hash functions using unbalanced approximations of round functions

I. A. Gribanova

Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk

Abstract: The report presents the results of solving the inversion problem of the truncated variant of cryptographic hash-function MD4 using new technique which includes the following steps: the substitution of some round subfunctions of MD4 by unbalanced Boolean functions; the solution of obtained (modified) problem; moving to the solution of original problem by taking into account the information from the solution of the corresponding modified problem. Suggested technique is combined with the additional conditions on chaining variables used previously by H. Dobbertin. Computational experiments illustrate the applicability of the proposed approach to the inversion problem of the $39$-step version of MD4 (MD4-39).

Keywords: cryptanalysis, inversion problem of hash functions, MD4, SAT.

UDC: 519.7

DOI: 10.17223/2226308X/10/61