Abstract:
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$.