Страница публикации

Measuring the Effectiveness of SAT-Based Guess-and-Determine Attacks in Algebraic Cryptanalysis

Авторы: Gladush A., Gribanova I., Kondratiev V., Pavlenko A., Semenov A.

Журнал: Communications in Computer and Information Science

Том: 1618

Номер:

Год: 2022

Отчётный год: 2022

Издательство:

Местоположение издательства:

URL:

Проекты:

Теоретические основы, методы и высокопроизводительные алгоритмы непрерывной и дискретной оптимизации для поддержки междисциплинарных научных исследований

DOI: 10.1007/978-3-031-11623-0_11

Аннотация: This paper studies the problem of algebraic cryptanalysis where state-of-the-art SAT solvers are used to invert some cryptographic function. We define a new metric of the hardness of CNF formulas that encode the corresponding cryptanalysis problems. The introduced metric is similar to the well-known tree-like metrics used in the theory of propositional proofs. However, unlike the latter, the new metric can be effectively estimated in application to specific cryptographic functions. The corresponding approach combines the Monte Carlo method and metaheuristic black-box optimization algorithms. The proposed algorithms require a large amount of computational resources, and for their experimental evaluation we used a supercomputer. In the experiments, we applied the proposed metrics to construct estimations of guess-and-determine attacks on the compression function of the well-known MD4 cryptographic hash algorithm.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Нет

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0