Geodesic
Preimage attack on 44-step MD4 compression function with weakened last step
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 90-93.

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

The main component of the cryptographic hash function MD4 is a 48-step compression function. In 2007, a preimage of the 39-step MD4 compression function was found via CDCL — the main complete SAT solving algorithm. In 2022, a preimage of the 43-step MD4 compression function was found via the parallel SAT solving algorithm Cube-and-Conquer. In the present paper, 44-step compression function MD4 is studied such that the 44th step is weakened in different ways. Preimages of several such functions were found via Cube-and-Conquer. Based on these results, a runtime estimate of a preimage attack on the 44-step MD4 compression function is calculated.
Keywords: cryptographic hash function, preimage attack, logical cryptanalysis, SAT.
Mots-clés : MD4 
@article{PDMA_2024_17_a19,
     author = {O. S. Zaikin},
     title = {Preimage attack on 44-step {MD4} compression function with weakened last step},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {90--93},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a19/}
}
TY  - JOUR
AU  - O. S. Zaikin
TI  - Preimage attack on 44-step MD4 compression function with weakened last step
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 90
EP  - 93
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a19/
LA  - ru
ID  - PDMA_2024_17_a19
ER  - 
%0 Journal Article
%A O. S. Zaikin
%T Preimage attack on 44-step MD4 compression function with weakened last step
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 90-93
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a19/
%G ru
%F PDMA_2024_17_a19
O. S. Zaikin. Preimage attack on 44-step MD4 compression function with weakened last step. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 90-93. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a19/

[1] Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V., Osnovy kriptografii, 2-e izd., Gelios ARV, M., 2002

[2] Rivest R., “The MD4 message digest algorithm”, LNCS, 537, 1991, 303–311 | Zbl

[3] Dobbertin H., “Cryptanalysis of MD4”, LNCS, 1039, 1996, 53–69 | MR | Zbl

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

[5] Bard G., Algebraic Cryptanalysis, Springer, N.Y., 2009 | MR | Zbl

[6] Massacci F., Marraro L., “Logical cryptanalysis as a SAT problem”, J. Automated Reasoning, 1 (2000), 165–203 | DOI | MR | Zbl

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

[8] Marques-Silva J., Sakallah K., “GRASP: a search algorithm for propositional satisfiability”, IEEE Trans. Comput., 48:5 (1999), 506–521 | DOI | MR | Zbl

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

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

[11] Zaikin O., “Inverting 43-step MD4 via Cube-and-Conquer”, Proc. IJCAI-ECAI (Vienna), 2022, 1894–1900

[12] Heule M. J. H., Kullmann O., Wieringa S., Biere A., “Cube and Conquer: guiding CDCL SAT solvers by lookaheads”, LNCS, 7261, 2012, 50–65

[13] Zaikin O. S., “Obraschenie 29-shagovoi funktsii szhatiya MD5 pri pomoschi algoritmov resheniya problemy bulevoi vypolnimosti”, Prikladnaya diskretnaya matematika. Prilozhenie, 2023, no. 16, 37–40

[14] Semenov A., Otpuschennikov I., Gribanova I., et al., “Translation of algorithmic descriptions of discrete functions to SAT with application to cryptanalysis problems”, Logical Methods Comput. Sci., 16:1 (2020), 29:1–29:42 | MR | Zbl

[15] Biere A., Fleury M., “Gimsatul, IsaSAT and Kissat entering the SAT Competition 2022”, Proc. SAT Competition. Solver and Benchmark Descriptions, 2022, 10–11