Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis

Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis

Автор: Gribanova I.A., Zaikin O.S., Otpuschennikov I.V., Semenov A.A.

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Рубрика: Дискретная математика и математическая кибернетика

Статья в выпуске: 3 т.6, 2017 года.

Бесплатный доступ

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 39inclusive). Our method significantly outperforms previously existing approaches to solving these problems.

Еще

Cryptanalysis, hash function, inversion problem, md4, sat, parallel computing, mpi

Короткий адрес: https://sciup.org/147160623

IDR: 147160623   |   DOI: 10.14529/cmse170302

Список литературы Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis

  • Wang X., Lai X., Feng D., Chen H., Yu X. Cryptanalysis of the Hash FunctionsMD4 and RIPEMD//Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques. EUROCRYPT’05. Berlin, Heidelberg: Springer-Verlag, 2005. P. 1-18 DOI: 10.1007/11426639_1
  • Wang X., Yu H. How to Break MD5 and Other Hash Functions//Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques. EUROCRYPT’05. Berlin, Heidelberg: Springer-Verlag, 2005. P. 19-35 DOI: 10.1007/11426639_2
  • Dobbertin H. The First Two Rounds of MD4 are Not One-Way//Fast Software Encryption/Ed. by Serge Vaudenay. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1998. Vol. 1372. P. 284-292 DOI: 10.1007/3-540-69710-1_19
  • Rivest R.L. The MD4 Message Digest Algorithm//Advances in Cryptology -CRYPTO’90,Proceedings/Ed. by Alfred Menezes, Scott A. Vanstone. Lecture Notes in Computer Science. Springer, 1990. Vol. 537. P. 303-311 DOI: 10.1007/3-540-38424-3_22
  • Damg˚ard I.B. A Design Principle for Hash Functions//Proceedings on Advances inCryptology. CRYPTO ’89. New York, NY, USA: Springer-Verlag New York, Inc., 1989. P. 416-427 DOI: 10.1007/0-387-34805-0_39
  • Merkle R.C. A Certified Digital Signature//Proceedings on Advances in Cryptology.CRYPTO ’89. New York, NY, USA: Springer-Verlag New York, Inc., 1989. P. 218-238 DOI: 10.1007/0-387-34805-0_21
  • Tseitin G.S On the Complexity of Derivation in Propositional Calculus//Automation of Reasoning:2:ClassicalPapers on ComputationalLogic1967-1970. Berlin,Heidelberg: Springer Berlin Heidelberg,1983. P. 466-483 DOI: 10.1007/978-3-642-81955-1_28
  • Erk¨ok L., Matthews J. High assurance programming in Cryptol//Fifth Cyber Security and Information Intelligence Research Workshop, CSIIRW’09, Knoxville, TN, USA, April 13-15, 2009/Ed. by Frederick T. Sheldon, Greg Peterson, Axel W. Krings ACM, 2009. P. 60 DOI: 10.1145/1558607.1558676
  • Janicic P. URSA: a System for Uniform Reduction to SAT//Logical Methods in ComputerScience. 2012. Vol. 8, No. 3. P. 1-39 DOI: 10.2168/lmcs-8(3:30)2012
  • Soos M., Nohl K., Castelluccia C. Extending SAT Solvers to Cryptographic Problems//SAT/Ed. by Oliver Kullmann. Lecture Notes in Computer Science. Springer, 2009. Vol. 5584. P. 244-257 DOI: 10.1007/978-3-642-02777-2_24
  • Otpuschennikov I., Semenov A., Gribanova I., Zaikin O., Kochemazov S. EncodingCryptographic Functions to SAT Using TRANSALG System//ECAI 2016 -22nd European Conference on Artificial Intelligence, 29 August -2 September 2016, The Hague, The Netherlands -Including Prestigious Applications of Artificial Intelligence (PAIS 2016)/Ed. by Gal A. Kaminka, Maria Fox, Paolo Bouquet . Frontiers in Artificial Intelligence and Applications. IOS Press, 2016. Vol. 285. P. 1594-1595.
  • Marques-Silva J.P., Sakallah K.A. GRASP: A Search Algorithm for PropositionalSatisfiability//IEEE Trans. Computers. 1999. Vol. 48, No. 5. P. 506-521 DOI: 10.1109/12.769433
  • Marques-Silva J.P., Lynce I., Malik S. Conflict-Driven Clause Learning SAT Solvers//Handbook of Satisfiability/Ed. by Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh. Frontiers in Artificial Intelligence and Applications. IOS Press, 2009. Vol. 185. P. 131-153
  • Hyv¨arinen A.E.J. Grid Based Propositional Satisfiability Solving. Ph. D. thesis, AaltoUniversity, 2011
  • Mironov I., Zhang L. Applications of SAT Solvers to Cryptanalysis of Hash Functions//SAT/Ed. by Armin Biere, Carla P. Gomes. Lecture Notes in Computer Science. Springer, 2006. Vol. 4121. P. 102-115 DOI: 10.1007/11814948_13
  • De D., Kumarasubramanian A., Venkatesan R. Inversion Attacks on Secure Hash FunctionsUsing SAT Solvers//Theory and Applications of Satisfiability Testing -SAT 2007, Proceedings/Ed. by Jo˜ao Marques-Silva, Karem A. Sakallah. Lecture Notes in Computer Science. Springer, 2007. Vol. 4501. P. 377-382 DOI: 10.1007/978-3-540-72788-0_36
  • E´en N., S¨orensson N. Temporal Induction by Incremental SAT Solving//Electr. NotesTheor. Comput. Sci. 2003. Vol. 89, No. 4. P. 543-560 DOI: 10.1016/s1571-0661(05)82542-3
  • Semenov A., Zaikin O. Algorithm for Finding Partitionings of Hard Variants of BooleanSatisfiability Problem with Application to Inversion of Some Cryptographic Functions//SpringerPlus. 2016. Vol. 5, No. 1. P. 1-16 DOI: 10.1186/s40064-016-2187-4
  • Bogachkova (Gribanova) I., Zaikin O., Kochemazov S., Otpuschennikov I., Semenov A.,Khamisov O. Problems of Search for Collisions of Cryptographic Hash Functions of the MD Family as Variants of Boolean Satisfiability Problem//Numerical Methods and Programming. 2015. Vol. 16, No. 1. P. 61-77.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp