This article is cited in 1 paper

Mathematical Methods of Cryptography

Preimage attack on 44-step MD4 compression function with weakened last step

O. S. Zaikin<sup>ab

a</sup> Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk
^b Mathematical Center in Akademgorodok, Novosibirsk

Abstract: The main component of the cryptographic hash function MD4 is a 48-step compression function. In 2007, a preimage of the 39-step MD4 compression function was found via CDCL — the main complete SAT solving algorithm. In 2022, a preimage of the 43-step MD4 compression function was found via the parallel SAT solving algorithm Cube-and-Conquer. In the present paper, 44-step compression function MD4 is studied such that the 44th step is weakened in different ways. Preimages of several such functions were found via Cube-and-Conquer. Based on these results, a runtime estimate of a preimage attack on the 44-step MD4 compression function is calculated.

Keywords: cryptographic hash function, MD4, preimage attack, logical cryptanalysis, SAT.

UDC: 004.8

DOI: 10.17223/2226308X/17/20