Abstract:
In this paper we study the inversion problem of MD4 cryptographic hash function developed by R. Rivest in 1990. By MD4-k we denote a truncated variant of MD4 hash function in which k represents a number ofsteps used to calculate a hash value (the full version of MD4 function corresponds to MD4-48). H. Dobbertin hasshowed that MD4-32 hash function is not one-way, namely, it can be inverted for the given image of a randominput. He suggested to add special conditions to the equations that describe the computation of concrete steps(chaining variables) of the considered hash function. These additional conditions allowed to solve the inversionproblem of MD4-32 within a reasonable time by solving corresponding system of equations. The main result ofthe present paper is an automatic derivation of “Dobbertin’s conditions” using parallel SAT solving algorithms.We also managed to solve several inversion problems of functions of the kind MD4-k (for k from 31 up to 39 inclusive). Our method significantly outperforms previously existing approaches to solving these problems.
This research was funded by Russian Science Foundation (project No. 16-11-10046). Oleg Zaikin and Ilya Otpuschennikov are partially funded by Council for Grants of the President of the Russian Federation (stipends SP-1184.2015.5 and SP-4751.2016.5 respectively).
Received: 04.05.2017
Bibliographic databases:
Document Type:
Article
UDC:
004.056.55, 003.26
Language: English
Citation:
I. A. Gribanova, O. S. Zaikin, I. V. Otpushchennikov, A. A. Semenov, “Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis”, Vestn. YuUrGU. Ser. Vych. Matem. Inform., 6:3 (2017), 16–27
\Bibitem{GriZaiOtp17}
\by I.~A.~Gribanova, O.~S.~Zaikin, I.~V.~Otpushchennikov, A.~A.~Semenov
\paper Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis
\jour Vestn. YuUrGU. Ser. Vych. Matem. Inform.
\yr 2017
\vol 6
\issue 3
\pages 16--27
\mathnet{http://mi.mathnet.ru/vyurv169}
\crossref{https://doi.org/10.14529/cmse170302}
\elib{https://elibrary.ru/item.asp?id=30016525}
Linking options:
https://www.mathnet.ru/eng/vyurv169
https://www.mathnet.ru/eng/vyurv/v6/i3/p16
This publication is cited in the following 1 articles:
Aleksey I. Pakhomchik, Vladimir V. Voloshinov, Valerii M. Vinokur, Gordey B. Lesovik, “Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis”, Algorithms, 15:2 (2022), 33
Citation in format AMSBIB
Contact us: