Computational methods in discrete mathematics

Revisiting Dobbertin constraints for SAT-based preimage attacks on round-reduced MD4 compression function

S. E. Kochemazov, O. S. Zaikin


Abstract: MD4 was one of the first cryptographic hash functions. Due to some structural features, its compression function is vulnerable to collision attacks and, to a lesser degree, to preimage attacks. Key investigations in this area were carried out by Hans Dobbertin. In particular, he proposed special constraints that made it possible to invert the first 32 steps of the MD4 compression function. Later, these constraints were encoded to SAT and helped to invert up to 43 steps of this compression function. We analyze the influence of Dobbertin's constraints on such SAT-based preimage attacks and propose a new runtime estimation for inverting the 44-step MD4 compression function.

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

UDC: 004.8

DOI: 10.17223/2226308X/18/57