Geodesic
On the argument of the absence of properties of a random oracle for some cryptographic hash functions
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 95-98.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDMA_2019_12_a29,
     author = {I. A. Gribanova and A. A. Semenov},
     title = {On the argument of the absence of properties of a random oracle for some cryptographic hash functions},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {95--98},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a29/}
}
TY  - JOUR
AU  - I. A. Gribanova
AU  - A. A. Semenov
TI  - On the argument of the absence of properties of a random oracle for some cryptographic hash functions
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 95
EP  - 98
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a29/
LA  - ru
ID  - PDMA_2019_12_a29
ER  - 
%0 Journal Article
%A I. A. Gribanova
%A A. A. Semenov
%T On the argument of the absence of properties of a random oracle for some cryptographic hash functions
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 95-98
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a29/
%G ru
%F PDMA_2019_12_a29
I. A. Gribanova; A. A. Semenov. On the argument of the absence of properties of a random oracle for some cryptographic hash functions. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 95-98. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a29/

[1] Bellare M., Rogaway P., “Random oracles are practical: a paradigm for designing efficient protocols”, Proc. CCS'93, ACM, N.Y., 1993, 62–73

[2] Pointcheval D., Stern J., “Security proofs for signature schemes”, EUROCRYPT'96, LNCS, 1070, 1996, 387–398 | MR | Zbl

[3] Pointcheval D., Stern J., “Security arguments for digital signatures and blind signatures”, J. Cryptology, 13:3 (2000), 361–396 | DOI | Zbl

[4] Rivest R. L., “The MD4 message digest algorithm”, CRYPTO'90, LNCS, 537, 1990, 303–311

[5] Gribanova I., Semenov A., “Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4”, Proc. MIPRO-2018, IEEE, 2018, 1174–1179

[6] Gribanova I. A., “Novyi algoritm porozhdeniya oslablyayuschikh ogranichenii v zadache obrascheniya khesh-funktsii MD4-39”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 139–141

[7] Dobbertin H., “The first two rounds of MD4 are not one-way”, Proc. FSE'1998, LNCS, 1372, 1998, 284–292 | Zbl

[8] De D., Kumarasubramanian A., Venkatesan R., “Inversion attacks on secure hash functions using SAT solvers”, Proc. FSE'2007, LNCS, 4501, 2007, 377–382 | Zbl

[9] Boros E., Hammer P. L., “Pseudo-boolean optimization”, Discr. Appl. Math., 123:1–3 (2002), 155–225 | DOI | MR | Zbl

[10] Irkutskii superkompyuternyi tsentr SO RAN, http://hpc.icc.ru