On the argument of the absence of properties of a random oracle for some cryptographic hash functions

The paper presents new preimage attacks related to the class of algebraic attacks on hash functions MD4-k, 39 ^ k ^ 48. Hash function MD4-k consists of first k steps used in MD4 algorithm. To solve the corresponding systems of algebraic equations, SAT-solvers are used. The proposed attacks demonstrate that MD4-k functions are not random oracles. More precisely, we estimate the fraction of easy-invertible outputs of these functions and show that even for full-round version of hash function MD4, the obtained fraction is very big. To construct such estimations with each function of the kind MD4-k, we associate a special function, which input length is much smaller than 512. In most cases the preimage finding problem for such function is significantly simpler than the original one. We show that any value of the special function is the value of function MD4-k and estimate the fraction of these values in {0,1}¹²⁸. This approach allows us to obtain an estimation for the fraction of easy-invertible outputs of original hash function MD4-k.

Keywords

Authors

References