Статья

Название статьи ПРИМЕНЕНИЕ МЕТОДОВ АЛГЕБРАИЧЕСКОГО АНАЛИЗА ДЛЯ ЗАДАЧ ОЦЕНКИ ЗАЩИЩЕННОСТИ ИНФОРМАЦИИ
Автор Л.К. Бабенко, Е.А. Маро
Рубрика РАЗДЕЛ I. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И ЗАЩИТА ИНФОРМАЦИИ
Месяц, год 09, 2016
Индекс УДК 681.03.245
DOI 10.18522/2311-3103-2016-9-3750
Аннотация Описано применение методов алгебраического анализа для оценки защищенности информации при использовании криптографического преобразования данных симметричными блочными алгоритмами шифрования. В качестве исследуемых алгоритмов выбраны стандарты ГОСТ 34.12-2015 (n=64) и PRESENT. За основу алгебраического анализа взят метод сведения шифрования к задаче булевой выполнимости формул (SAT). Разработаны алгоритмы формирования систем булевых нелинейных уравнений для произвольных заполнений блоков замены и различного числа раундов шифров на основе сети Фейстеля и SP-сети. Предложена методика проведения алгебраического анализа с помощью SAT-решателя CryptoMiniSat, позволяющая предварительно вычислять ожидаемую сложность нахождения наборов решений систем булевых нелинейных уравнений с помощью методов сведения к SAT-задаче. Выделены исследуемые критерии оценки защищенности информации на основе алгебраического анализа криптографических алгоритмов. Разработанные в ходе выполнения исследования алгоритмы и методика могут быть в дальнейшем использованы для оценки защищенности произвольных преобразований на основе операций замены и сложения по модулю при алгебраическом анализе. В ходе моделирования алгебраического анализа была оценена защищенности данных при сокращенном числе раундов шифрования данных алгоритмов (вычисления проводились с использованием вычислительных ресурсов SageMath Cloud). Для 8 раундов алгоритма «Магма» (ГОСТ 34.12-2015, n=64) ключ шифрования удалось вычислить при известных 4 текстах за 3029,56 сек. Для 4 раундов шифрования PRESENT (ISO 29192-2:2012) 16 наборов ключей были вычислены при наличии 8 текстов за 3268,42 сек.

Скачать в PDF

Ключевые слова Оценка защищенности информации; алгебраический анализ; симметричные блочные алгоритмы шифрования; ГОСТ 34.12-2015; PRESENT; задача булевой выполнимости формул (SAT); решатель CryptoMiniSat, алгебраическая нормальная форма (АНФ), конъюнктивная нормальная форма (КНФ).
Библиографический список 1. Семенов А.А., Заикин О.С., Беспалов Д.В., Ушаков А.А. SAT-подход в криптоанализе некоторых систем поточного шифрования // Вычислительные технологии. – 2008.
– Т. 13, № 6.
2. Семенов А.А. Алгоритмы решения задачи о булевой выполнимости (SAT) и их применение в криптоанализе // PHDays 2015.
3. Soos M., Nohl K., Castelluccia C. Extending SAT Solvers to Cryptographic Problems // Theory and Applications of Satisfiability Testing – SAT, 2009. – P. 244-257.
4. Sepehrdad P. Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-lightweight Symmetric Primitives: PhD Dissertation, 2012. – 180 p.
5. Erickson J., Ding J., Christensen C. Algebraic Cryptanalysis of SM4: Grobner Basis Attack and SAT Attack Compared // 12th International Conference, Seoul, Korea, 2009. – P. 73-86.
6. Albrecht M. Tools for Algebraic Cryptanalysis // Proceedings of the ECRYPT Workshop on Tools for Cryptanalysis. – 2010. – P. 13-14,
7. Courtois N. Algebraic Complexity Reduction and Cryptanalysis of GOST.
–http://www.nicolascourtois.com/papers/gostac11.pdf.
8. Weinmann R.-P. Algebraic Methods in Block Cipher Cryptanalysis. PhD Dissertation, 2009.
– 113 p.
9. Bulygin S. Algebraic cryptanalysis of the round-reduced and side channel analysis of the full PRINTCipher-48. – http://eprint.iacr.org/2011/287.pdf.
10. Otpuschennikov I., Semenov A., Gribalova I., Zaikin O., Kochemazov S. Encoding Crypto-graphic functions to SAT Using TRANSALG system // ECAI 2016: 22nd European Confer-ence on Artificial Intelligence. – 2016. – P. 1594-1595.
11. Soos M. CryptoMiniSat 2.5.1. – http://www.msoos.org/wordpress/wp-content/uploads/2010/
08/cryptominisat-2.5.1.pdf.
12. Bard G., Courtois N., Jefferson C. Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers // Cryptology ePrint Archive. – 2007. – Vol. 24. – https://eprint.iacr.org/2007/024.pdf.
13. SageMath, the Sage Mathematics Software System, The Sage Developers, 2016.
– http://www.sagemath.org.
14. ГОСТ Р 34.12-2015. Криптографическая защита информации. – http://tc26.ru/standard/ gost/GOST_R_3412-2015.pdf.
15. Бабенко Л.К., Маро Е.А. Анализ стойкости блочных алгоритмов шифрования к алгебраическим атакам // Известия ЮФУ. Технические науки. – 2011. – № 12 (125). – C. 110-119.
16. Babenko L. K., Maro E.A., Anikeev M.V. Modeling of algebraic analysis of GOST+ cipher in SageMath // 7th international conference on Security of information and networks. – 2016.
– P. 100-103.
17. Babenko L.K., Ishchukova E.A., Maro E.A. Algebraic analysis of GOST encryption algorithm // 4th International conference on Security of information and networks. – 2011. – P. 57-62.
18. Бабенко Л.К., Ищукова Е.А Анализ алгоритма ГОСТ 28147-89: поиск слабых блоков // Извести ЮФУ. Технические науки. – 2014. – № 2 (151). – C. 129-138.
19. Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J., Seurin B., Vikkelsoe C. PRESENT: An ultra-light--weight block cipher // Cryptographic Hardware and Embedded Systems- -CHES ’07, 9th International Workshop, Vienna, Austria, 2007.
– Vol. 4727. – P. 450-466.
20. Bard G. Algebraic Cryptanalysis. – 2009. – 356 p.
21. Nakahara J., Sepehrdad P., Zhang B., Wang M. Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT // 8th International Conference on Cryptology and Network Secu-rity, CANS ’09, New York, 2009. – P. 58-75.

Comments are closed.