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

I. A. Gribanova ; A. A. Semenov

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 95-98

Résumé

The paper presents new preimage attacks related to the class of algebraic attacks on hash functions $\mathrm{MD4}$-$k$, $39 \leq k \leq 48$. Hash function $\mathrm{MD4}$-$k$ consists of first $k$ steps used in $\mathrm{MD4}$ algorithm. To solve the corresponding systems of algebraic equations, SAT-solvers are used. The proposed attacks demonstrate that $\mathrm{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 $\mathrm{MD4}$, the obtained fraction is very big. To construct such estimations with each function of the kind $\mathrm{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 $\mathrm{MD4}$-$k$ and estimate the fraction of these values in $\{0,1\}^{128}$. This approach allows us to obtain an estimation for the fraction of easy-invertible outputs of original hash function $\mathrm{MD4}$-$k$.

Détail

Keywords: cryptographic hash functions, preimage attack on hash functions, $\mathrm{MD4}$, $\mathrm{MD4}$-$39$, SAT.