The inversion of cryptographic hash functions using unbalanced approximations of round functions
The report presents the results of solving the inversion problem of the truncated variant of cryptographic hash-function MD4 using new technique which includes the following steps: the substitution of some round subfunctions of MD4 by unbalanced Boolean functions; the solution of obtained (modified) problem; moving to the solution of original problem by taking into account the information from the solution of the corresponding modified problem. Suggested technique is combined with the additional conditions on chaining variables used previously by H. Dobbertin. Computational experiments illustrate the applicability of the proposed approach to the inversion problem of the 39-step version of MD4 (MD4-39).
Download file
Counter downloads: 211
Keywords
криптоанализ, обращение хеш-функций, MD4, SAT, cryptanalysis, inversion problem of hash functions, MD4, SATAuthors
| Name | Organization | |
| Gribanova I. A. | Institute of Dynamics of Systems and Control Theory. V.M. Matrosov of the SB RAS | the42dimension@gmail.com |
References
Rivest R. L. The MD4 message digest algorithm // LNCS. 1990. V. 537. P. 303-311.
Merkle R. A. Certified digital signature // LNCS. 1990. V.435. P. 218-238.
Damgard I. A. A design principle for hash functions // LNCS. 1990. V. 435. P. 416-427.
Wang X., LaiX., Feng D., et al. Cryptanalysis of the hash functions MD4 and RIPEMD // LNCS. 2005. V. 3494. P. 1-18.
Dobbertin H. The first two rounds of md4 are not one-way // LNCS. 1998. V. 1372. P. 284-292.
De D., Kumarasubramanian A, and Venkatesan R. Inversion attacks on secure hash functions using SAT solvers // LNCS. 2007. V.4501. P. 377-382.
Gribanova I., Zaikin O., Otpuschennikov I., and Semenov A. Using parallel SAT solving algorithms to study the inversion of MD4 hash function // Параллельные вычислительные технологии. XI Междунар. конф. ПаВТ'2017, г. Казань, 3-7 апреля 2017 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2017. С. 100-109.
Otpuschennikov I., Semenov A., Gribanova I., et al. Encoding cryptographic functions to SAT using TRANSALG system // ECAI 2016-22nd European Conference on Artificial Intelligence. Frontiers in Artificial Intelligence and Applications. 2016. V. 285. P. 1594-1595.
Biere A. Lingeling essentials. A tutorial on design and implementation aspects of the the SAT solver lingeling // Proc. Fifth Pragmatics of SAT Workshop. 2014. V. 27. P. 88.
http://hpc.icc.ru - Иркутский суперкомпьютерный центр СО РАН. Иркутск: ИДСТУ СО РАН.
