Geodesic
Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 6 (2017) no. 3, pp. 16-27 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we study the inversion problem of MD4 cryptographic hash function developed by R. Rivest in 1990. By MD4-k we denote a truncated variant of MD4 hash function in which k represents a number ofsteps used to calculate a hash value (the full version of MD4 function corresponds to MD4-48). H. Dobbertin hasshowed that MD4-32 hash function is not one-way, namely, it can be inverted for the given image of a randominput. He suggested to add special conditions to the equations that describe the computation of concrete steps(chaining variables) of the considered hash function. These additional conditions allowed to solve the inversionproblem of MD4-32 within a reasonable time by solving corresponding system of equations. The main result ofthe present paper is an automatic derivation of “Dobbertin’s conditions” using parallel SAT solving algorithms.We also managed to solve several inversion problems of functions of the kind MD4-k (for k from 31 up to 39 inclusive). Our method significantly outperforms previously existing approaches to solving these problems.
Keywords: hash function, inversion problem, SAT, parallel computing, MPI.
Mots-clés : cryptanalysis, MD4 
@article{VYURV_2017_6_3_a1,
     author = {I. A. Gribanova and O. S. Zaikin and I. V. Otpushchennikov and A. A. Semenov},
     title = {Preimage attack on {MD4} hash function as a problem of parallel sat-based cryptanalysis},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {16--27},
     year = {2017},
     volume = {6},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2017_6_3_a1/}
}
TY  - JOUR
AU  - I. A. Gribanova
AU  - O. S. Zaikin
AU  - I. V. Otpushchennikov
AU  - A. A. Semenov
TI  - Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2017
SP  - 16
EP  - 27
VL  - 6
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2017_6_3_a1/
LA  - en
ID  - VYURV_2017_6_3_a1
ER  - 
%0 Journal Article
%A I. A. Gribanova
%A O. S. Zaikin
%A I. V. Otpushchennikov
%A A. A. Semenov
%T Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2017
%P 16-27
%V 6
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2017_6_3_a1/
%G en
%F VYURV_2017_6_3_a1
I. A. Gribanova; O. S. Zaikin; I. V. Otpushchennikov; A. A. Semenov. Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 6 (2017) no. 3, pp. 16-27. http://geodesic.mathdoc.fr/item/VYURV_2017_6_3_a1/

[1] X. Wang, X. Lai, D. Feng, H. Chen, X. Yu, “Cryptanalysis of the Hash Functions MD4 and RIPEMD”, Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT’05, Springer-Verlag, Berlin, Heidelberg, 2005, 1–18 | DOI

[2] X. Wang, H. Yu, “How to Break MD5 and Other Hash Functions”, Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT’05, Springer-Verlag, Berlin, Heidelberg, 2005, 19–35 | DOI

[3] H. Dobbertin, “The First Two Rounds of MD4 are Not One-Way”, Fast Software Encryption, v. 1372, Lecture Notes in Computer Science, ed. Serge Vaudenay, Springer Berlin Heidelberg, 1998, 284–292 | DOI

[4] R. L. Rivest, “The MD4 Message Digest Algorithm”, Advances in Cryptology - CRYPTO’90, Proceedings, Lecture Notes in Computer Science., 537, Springer, 1990, 303–311 | DOI

[5] I. B. Damgård, “A Design Principle for Hash Functions”, Proceedings on Advances in Cryptology, CRYPTO ’89 (New York, NY, USA), Springer-Verlag New York, Inc., 1989, 416–427 | DOI

[6] R. C. Merkle, “A Certified Digital Signature”, Proceedings on Advances in Cryptology, CRYPTO ’89 (New York, NY, USA), Springer-Verlag New York, Inc., 1989, 218–238 | DOI

[7] G. S. Tseitin, “On the Complexity of Derivation in Propositional Calculus”, Automation of Reasoning: 2: Classical Papers on Computational Logic 1967–1970, Springer Berlin Heidelberg, Berlin, Heidelberg, 1983, 466–483 | DOI

[8] L. Erk\"øk, J. Matthews, “High assurance programming in Cryptol”, Fifth Cyber Security and Information Intelligence Research Workshop, CSIIRW’09 (Knoxville, TN, USA, April 13–15), ed. Frederick T. Sheldon, Greg Peterson, Axel W. Krings, et al., ACM, 2009, 60 | DOI

[9] P. Janicic, “URSA: a System for Uniform Reduction to SAT”, Logical Methods in Computer Science, 8:3 (2012), 1–39 | DOI

[10] M. Soos, K. Nohl, C. Castelluccia, “Extending SAT Solvers to Cryptographic Problems”, SAT, v. 5584, Lecture Notes in Computer Science, ed. Oliver Kullmann, Springer, 2009, 244–257 | DOI

[11] I. Otpuschennikov, A. Semenov, I. Gribanova, O. Zaikin, S. Kochemazov, “Encoding Cryptographic Functions to SAT Using TRANSALG System”, ECAI 2016 - 22nd European Conference on Artificial Intelligence, Including Prestigious Applications of Artificial Intelligence (PAIS 2016) (29 August – 2 September 2016, The Hague, The Netherlands), v. 285, Frontiers in Artificial Intelligence and Applications, ed. Gal A. Kaminka, Maria Fox, Paolo Bouquet et al., IOS Press, 2016, 1594–1595

[12] J. P. Marques-Silva, K. A. Sakallah, “GRASP: A Search Algorithm for Propositional Satisfiability”, IEEE Trans. Computers, 48:5 (1999), 506–521 | DOI

[13] J. P. Marques-Silva, I. Lynce, S. Malik, “Conflict-Driven Clause Learning SAT Solvers”, Handbook of Satisfiability, v. 185, Frontiers in Artificial Intelligence and Applications, ed. Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh., IOS Press, 2009, 131–153

[14] A. E. J. Hyärinen, Grid Based Propositional Satisfiability Solving, Ph. D. thesis, Aalto University, 2011

[15] I. Mironov, L. Zhang, “Applications of SAT Solvers to Cryptanalysis of Hash Functions”, SAT, v. 4121, Lecture Notes in Computer Science, ed. Armin Biere, Carla P. Gomes, Springer, 2006, 102–115 | DOI

[16] D. De, A. Kumarasubramanian, R. Venkatesan, “Inversion Attacks on Secure Hash Functions Using SAT Solvers”, Theory and Applications of Satisfiability Testing - SAT 2007, Proceedings, v. 4501, Lecture Notes in Computer Science, ed. Joao Marques-Silva, Karem A. Sakallah, Springer, 2007, 377–382 | DOI

[17] N. Een, N. Sörensson, “Temporal Induction by Incremental SAT Solving”, Electr. Notes Theor. Comput. Sci., 89:4 (2003), 543–560 | DOI

[18] A. Semenov, O. Zaikin, “Algorithm for Finding Partitionings of Hard Variants of Boolean Satisfiability Problem with Application to Inversion of Some Cryptographic Functions”, SpringerPlus, 5:1 (2016), 1–16 | DOI

[19] I. Bogachkova (Gribanova), O. Zaikin, S. Kochemazov, I. Otpuschennikov, A. Semenov, O. Khamisov, “Problems of Search for Collisions of Cryptographic Hash Functions of the MD Family as Variants of Boolean Satisfiability Problem”, Numerical Methods and Programming., 16:1 (2015), 61–77