Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions md4 | Applied Discrete Mathematics. Supplement. 2020. № 13. DOI: 10.17223/2226308X/13/37

Using inverse backdoors sets to construct guess-and-determine attacks on hash-functions md4

In the paper, we propose new preimage attacks on hash-functions MD4-k, k > 39. These attacks, related to the class of guess-and-determine attacks, are based on the idea of inverse backdoor set. We use SAT solvers to solve the cryptanalysis problems weakened by substitution of guessed bits to SAT encodings of the considered functions. The problem of search for an inverse backdoor set with relatively small complexity estimation is considered as a minimization problem of a special pseudo-Boolean function. To solve this problem, we apply several metaheuristic algorithms: tabu search algorithm, (1+1)-FEA^, and a variant of genetic algorithm. These algorithms produce attacks on the considered functions with close complexity estimations. For the full-round compression function MD4 the best attack is constructed using the genetic algorithm.

Download file

Counter downloads: 83

Keywords

задача поиска прообразов криптографической хеш-функции, атаки из класса «угадывай и определяй», инверсные лазейки, SAT, preimage attack on hash function, guess-and-determine attacks, MD4, inverse backdoor sets, SAT

Authors

Name	Organization	E-mail
Gribanova I. A.	V.M. Matrosov Institute of Dynamics and Control Theory SB RAS	the42dimension@gmail.com
Semenov A. A.	V.M. Matrosov Institute of Dynamics and Control Theory SB RAS	biclop.rambler@yandex.ru

Всего: 2

References

Semenov A., Zaikin O., Otpuschennikov I., et al. On cryptographic attacks using backdoors for SAT // Proc. 32nd AAAI Conf. 2018. P. 6641-6648.

Bard G. Algebraic Cryptanalysis. Springer Publishing Company, Inc., 2009. 356 p.

Semenov A., Otpuschennikov I., Gribanova I., et al. Translation of algorithmic descriptions of discrete functions to SAT with application to cryptanalysis problems // Log. Methods Comput. Sci. 2020. V. 16. Iss. 1. P. 29:1-29:42.

Цейтин Г. С. О сложности вывода в исчислении высказываний // Записки научных семинаров ЛОМИ АН СССР. 1968. Т. 8. С. 234-259.

Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. 360 с.

Boros E. and Hammer P. L. Pseudo-Boolean optimization // Discrete Appl. Math. 2002. V. 123(1-3). P. 155-225.

Феллер У. Введение в теорию вероятностей и ее приложения. Т. 1. М.: Мир, 1964. 500c.

Semenov A. and Zaikin O. Algorithm for finding partitionings of hard variants of Boolean satisfiability problem with application to inversion of some cryptographic functions // SpringerPlus. 2016. V. 5 (1). P. 1-16.

Glover F. and Laguna M. Tabu Search. Norwell: Kluwer Academic Publishers, 1997. 401 p.

Doerr B., Le H., Makhmara R., et al. Fast genetic algorithms // Proc. GECCO'17. 2017. P. 777-784.

Pavlenko A., Semenov A., and Ulyantsev V. Evolutionary computation techniques for constructing SAT-based attacks in algebraic cryptanalysis // LNCS. 2019. V. 11454. P. 237-253.

Muhlenbein H. How genetic algorithms really work: Mutation and hill climbing // Proc. PPSN-II. 1992. P. 15-26.

Wegener I. Theoretical aspects of evolutionary algorithms // ICALP 2001. LNCS. 2001. V. 2076. P. 64-78.

Droste S., Jansen T., and Wegener I. On the analysis of the (1+1) evolutionary algorithm // Theor. Comput. Sci. 2002. V. 276 (1-2). P. 51-81.

Luke S. Essentials of Metaheuristics. Second Edition. 2015. 261 p. https://cs.gmu.edu/ ~sean/book/metaheuristics/Essentials.pdf.

Rivest R.L. The MD4 message digest algorithm // CRYPT0'90. LNCS. 1990. V. 537. P. 303-311.

Dobbertin H. The first two rounds of MD4 are not one-way // FSE 1998. LNCS. 1998. V. 1372. P. 284-292.

De D., Kumarasubramanian A, and Venkatesan R. Inversion attacks on secure hash functions using SAT Solvers // FSE 2007. LNCS. 2007. V.4501. P. 377-382.

Gribanova I. and Semenov A. Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4 // Proc. 41st Intern. Convention MIPRO 2018. Opatija, 2018. P. 1174-1179.

Грибанова И. А., Семёнов А. А. Об аргументации отсутствия свойств случайного оракула у некоторых криптографических хеш-функций // Прикладная дискретная математика. Приложение. 2019. №12. С. 95-98.

Gribanova I. A. and Semenov A. A. Parallel guess-and-determine preimage attack with realistic complexity estimation for MD4-40 cryptographic hash function // Труды XIII Меж-дунар. конф. «Параллельные вычислительные технологии», Калининград, 02-04 апреля 2019. С. 8-18.

Иркутский суперкомпьютерный центр СО РАН. http://hpc.icc.ru.