This article is cited in 1 paper

Mathematical Methods of Cryptography

Inverting 29-step MD5 compression function via SAT

O. S. Zaikin

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

Abstract: The cryptographic hash function MD5 was proposed in 1992. Its key component is a 64-step compression function. The compression function is still preimage resistant, that is why its step-reduced versions are usually investigated in this context. In 2007, the 26-step version of the MD5 compression function was inverted via SAT. In 2012, 27- and 28-step versions were inverted via SAT as well. In the paper, an approach to forming 32 intermediate inversion problems between two subsequent steps of the MD5 compression function is proposed. SAT encodings of such problems were constructed between 28 and 29 steps. Several simplest problems were leveraged for tuning a modern SAT solver. As a result, the 29-step version of the MD5 compression function was inverted for the first time.

Keywords: cryptographic hash function, MD5, algebraic cryptanalysis, logical cryptanalysis, SAT.

UDC: 004.8

DOI: 10.17223/2226308X/16/10