RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2019 Issue 12, Pages 95–98 (Mi pdma445)

This article is cited in 2 papers

Mathematical Methods of Cryptography

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

I. A. Gribanova, A. A. Semenov

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

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

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

UDC: 519.7

DOI: 10.17223/2226308X/12/30



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024