Применение параллельных и распределенных алгоритмов решения проблемы булевой выполнимости (SAT) к криптоанализу, поиску комбинаторных структур и исследованию дискретных моделей коллективного поведения

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 16-11-10046

НазваниеПрименение параллельных и распределенных алгоритмов решения проблемы булевой выполнимости (SAT) к криптоанализу, поиску комбинаторных структур и исследованию дискретных моделей коллективного поведения

Руководитель Семенов Александр Анатольевич, Кандидат технических наук

Организация финансирования, регион федеральное государственное бюджетное учреждение науки Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук , Иркутская обл

Конкурс №13 - Конкурс 2016 года на получение грантов по приоритетному направлению деятельности РНФ «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-403 - Распределенные вычисления и GRID-технологии. Сверхмасштабируемые программные комплексы и алгоритмы. Испытание и оценка надежности.

Ключевые слова Задача о булевой выполнимости (SAT), криптоанализ, комбинаторные структуры, дискретно-автоматные модели коллективного поведения

Код ГРНТИ50.33.04

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Проблема булевой выполнимости (SAT) является одной из наиболее популярных среди исследователей, занимающихся комбинаторными алгоритмами. Несмотря на то что SAT –вычислительно сложная проблема (NP-трудна в общем случае), спектр ее практического применения чрезвычайно широк, благодаря эффективным редукциям к SAT комбинаторных задач из самых различных областей (символьная верификация, биоинформатика, вычислительная комбинаторика, криптоанализ и др.). В последние 10 лет наблюдается впечатляющий рост производительности алгоритмов решения SAT. Благодаря этим алгоритмам удается решать частные случаи SAT с десятками тысяч переменных и сотнями тысяч ограничений-дизъюнктов. Современные алгоритмы решения SAT успешно справляются даже с такими аргументированно трудными задачи, какими являются задачи обращения криптографических функций. Следует отметить, что интерес к разработке параллельных алгоритмов решения SAT стал заметен лишь с 2008 года, причем статей по данному вопросу относительно немного в общей массе публикаций по SAT-тематике. Исследований по реализации алгоритмов решения SAT в распределенных средах со слабо связанными вычислительными узлами и того меньше. Между тем в условиях интенсивного развития высокопроизводительных вычислительных систем актуальной представляется разработка именно распределенных алгоритмов решения SAT с последующим их применением к трудным задачам, решение которых может потребовать дней и даже месяцев работы вычислительной среды. Основная новизна планируемых результатов будет состоять, во-первых, в новых стратегиях распараллеливания SAT, во-вторых в оригинальных техниках использования накапливаемой на различных вычислительных узлах информации для ускорения общего процесса решения задачи. Наконец, разработанные алгоритмы решения SAT планируется применить к исследованию открытых вопросов криптоанализа, открытых задач существования некоторых комбинаторных структур, а также исследовать дискретно-автоматные модели коллективов с 1000 и более участниками (в частности, исследовать с дискретно-автоматных позиций процессы развития атак в компьютерных сетях).

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Семенов А.А., Заикин О.С., Отпущенников И.В., Кочемазов С.Е., Игнатьев А.С. On cryptographic attacks using backdoors for SAT AAAI 2018 Proceedings, Pp. 6641-6648 (год публикации - 2018)

2. Грибанова И.А., Семенов А.А. Using Automatic Generation of Relaxation Constraints to Improve the Preimage Attack on 39-step MD4 Proceedings of 41th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO-2018), Pp. 1174-1179 (год публикации - 2018)
10.23919/MIPRO.2018.8400213

3. Кочемазов С.Е., Заикин О.С. ALIAS: A Modular Tool for Finding Backdoors for SAT Proceedings of the 21st International Conference on Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science, vol. 10929 (SAT-2018), Pp. 419-427 (год публикации - 2018)
10.1007/978-3-319-94144-8_25

4. Кочемазов Степан Comparative Study of Combinatorial Algorithms for Solving the Influence Maximization Problem in Networks under a Deterministic Linear Threshold Model Procedia Computer Science, Vol. 136, Pp. 190-199 (год публикации - 2018)
10.1016/j.procs.2018.08.252

5. Семенов А.А., Горбатенко Д.Е., Кочемазов С.Е. Computational Study of Activation Dynamics on Networks of Arbitrary Structure Springer Proceedings in Mathematics and Statistics, Vol. 247, Pp. 205-220 (год публикации - 2018)
10.1007/978-3-319-96247-4_15

6. Белей Е.Г., Семенов А.А. О вычислительном поиске квазиортогональных систем латинских квадратов, близких к ортогональным системам International Journal of Open Information Technologies, Vol. 6. No. 2. Pp. 22-30 (год публикации - 2018)

7. Семенов А.А. Атаки из класса "угадывай и определяй" и автоматические способы их построения Прикладная дискретная математика. Приложение., № 11. С. 81-86 (год публикации - 2018)

8. Горбатенко Д.Е., Семенов А.А. Эффективный алгоритм построения множества кратчайших атак в рамках одной модели развития атак в компьютерной сети. Прикладная дискретная математика. Приложение., №11. С. 90-96 (год публикации - 2018)
10.17223/2226308X/11/28

9. Грибанова И.А. Новый алгоритм порождения ослабляющих ограничений в задаче обращения криптографической хеш-функции MD4-39 Прикладная дискретная математика. Приложение, №11. С. 139-141 (год публикации - 2018)
10.17223/2226308X/11/43

10. Отпущенников И.В., Семенов А.А., Заикин О.С. Пропозициональное кодирование прямых и обратных раундовых преобразований в атаках на некоторые блочные шифры Прикладная дискретная математика. Приложение., №11. С. 76-79 (год публикации - 2018)
10.17223/2226308X/11/24

11. Горбатенко Д.Е., Семенов А.А. Противодействие сговору в дискретных динамических моделях компьютерных сетей Управление большими системами., Выпуск 75. С. 76-102. (год публикации - 2018)
10.25728/ubs.2018.75.4

12. Ватутин Э., Кочемазов С., Заикин О. Applying volunteer and parallel computing for enumerating diagonal Latin squares of order 9 Proceedings of 11th International conference on Parallel computational technologies (PCT-2017). Communications in Computer and Information Science., Vol. 753, p. 114-129 (год публикации - 2017)
10.1007/978-3-319-67035-5_9

13. Семенов А.А., Заикин О.С. On the Accuracy of Statistical Estimations of SAT Partitionings Effectiveness in Application to Discrete Function Inversion Problems Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016), CEUR-WS, vol. 1623, PP. 261-275 (год публикации - 2016)

14. Горбатенко Д.Е., Кочемазов С.Е., Семенов А.А. Об автоматных моделях развития атак в компьютерных сетях и вычислительных алгоритмах их исследования Материалы XVIII международной конференции Проблемы теоретической кибернетики, С. 71-73 (год публикации - 2017)

15. Кочемазов С.Е., Заикин О.С., Семенов А.А. The Comparison of Different SAT Encodings for the Problem of Search for Systems of Orthogonal Latin Squares Proceedings of International Conference on Mathematical and Informational Technologies, MIT-2016, Vrnjacka Banja, Serbia 28.08-31.08, Budva, Montenegro, 01.09-05.09, 2016 (год публикации - 2016)

16. Кочемазов С. Bridging network static properties and activation dynamics Proceedings of the 6th International young scientists conference in high performance computing and simulation 2017 (YSC 2017) - 2017 - Procedia in computer science, Procedia in computer science Vol. 119, p.157-165 (год публикации - 2017)
10.1016/j.procs.2017.11.172

17. Грибанова И.А. Обращение криптографических хеш-функций с использованием несбалансированных приближений раундовых функций Труды всероссийской конференции “XVI Сибирская научная школа-семинар с международным участием “Компьютерная безопасность и криптография”” (SIBECRYPT’17). Прикладная дискретная математика. Приложение, № 10, C. 157-159 (год публикации - 2017)

18. Эдуард Ватутин, Олег Заикин, Степан Кочемазов, Сергей Валяев Using Volunteer Computing to Study Some Features of Diagonal Latin Squares Open Engineering (год публикации - 2018)

19. Грибанова И.А., Заикин О.С., Отпущенников И.В., Семёнов А.А. Preimage attack on MD4 hash function as a problem of parallel SAT-based cryptanalysis Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering., Vol. 6, no. 3, p. 16-27 (год публикации - 2017)
10.14529/cmse170302

20. Вадим Булавинцев, Александр Семёнов, Олег Заикин, Степан Кочемазов A Bitslice Implementation of Anderson's Attack on A5/1 Open Engineering (год публикации - 2018)

21. Заикин О.С., Кочемазов С.Е., Семенов А.А. SAT-based search for systems of diagonal Latin squares in volunteer computing project SAT@home 39th International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO 2016 - Proceedings, P. 293-297 (год публикации - 2016)
10.1109/MIPRO.2016.7522152

22. Кочемазов С., Заикин О., Семёнов А. Improving the effectiveness of SAT approach in application to analysis of several discrete models of collective behavior 2017 40th International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO 2017 - Proceedings, p. 1172-1177 (год публикации - 2017)
10.23919/MIPRO.2017.7973601

23. Олег Заикин, Степан Кочемазов An Improved SAT-Based Guess-and-Determine Attack on the Alternating Step Generator Information Security. ISC 2017. Lecture Notes in Computer Science, Vol. 10599, p.21-38 (год публикации - 2017)
10.1007/978-3-319-69659-1_2

24. Заикин О.С., Манзюк М.О., Кочемазов С.Е., Бычков И.В., Семенов А.А. A Volunteer-Computing-Based Grid Architecture Incorporating Idle Resources of Computing Clusters Lecture Notes in Computer Science (Proceedings of NAA'16: Sixth Conferences on Numerical Analysis and Applications, June 15-22, 2016) (год публикации - 2016)

25. Грибанова И., Заикин О., Кочемазов С., Отпущенников И., Семёнов А. The study of inversion problems of cryptographic hash functions from MD family using algorithms for solving Boolean satisfiability problem Proceedings of conference on Mathematical and Information Technologies (MIT-2016), CEUR Workshop Proceedings, Vol. 1839, p. 98-113 (год публикации - 2017)

26. Кочемазов С., Заикин О., Семёнов А. Runtime estimation for enumerating all mutually orthogonal diagonal Latin squares of order 10 2017 40th International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO 2017 - Proceedings, p. 1378-1383 (год публикации - 2017)
F-1007-2017

27. Булавинцев В., Заикин О., Семёнов А. Implementation of a brute force attack on the A5/1 keystream generator in a GPU-based volunteer computing project Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017) - CEUR Workshop Proceedings, Vol. 1973, p. 94-101 (год публикации - 2017)

28. Отпущенников И.В., Семенов А.А., Грибанова И.А., Заикин О.С., Кочемазов С.Е. Encoding Cryptographic Functions to SAT Using TRANSALG System ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE (Frontiers in Artificial Intelligence and Applications), vol. 285, P. 1594-1595 (год публикации - 2016)
10.3233/978-1-61499-672-9-1594

29. Кочемазов С.Е., Семенов А.А., Заикин О.С. The application of parameterized algorithms for solving SAT to the study of several discrete models of collective behavior 39th International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO 2016 - Proceedings, P. 1561-1565 (год публикации - 2016)
10.1109/MIPRO.2016.7522338

Публикации