Solving the problem of boolean satisfiability for estimating the security of block ciphers magma and present to algebrai.pdf В современном криптографическом научном сообществе на протяжении последних 15 лет развиваются и совершенствуются методы алгебраического криптоанализа, основанные на использовании нелинейных примитивов алгоритмов шифрования с целью описания алгоритма шифрования в виде систем уравнений, связывающих искомый ключ и известные данные. Повышение производительности современных SAT-решателей привело к возникновению идеи о возможности их применения для вычислительно трудоёмких задач криптоанализа [1-3]. Применяются различные методики проведения алгебраического криптоанализа на основе SAT-решения и построения Binary Decision Diagram (BDD). Одной из часто используемых методик при использовании SAT-решателей является Guess-and-Determine, которая заключается в фиксировании значений некоторых битов ключа, что позволяет существенно сократить общее время поиска решения рассматриваемой задачи криптоанализа. Методика Guess-and-Determine применена, например, в [4-6] к шифру Магма. Результаты проведения алгебраического анализа шифра PRESENT другими авторами представлены в работах [7, 8]. Моделирование алгебраического анализа шифров выполнялось в среде SageMath [9]. Использовались функции библиотеки sage.sat.converters.polybori для преобразования системы уравнений из АНФ в КНФ (CNFEncoder). Решение системы проведено на основе SAT-решателя CryptoMiniSat и осуществлялось с применением библиотеки sage.sat.boolean_polynomials [10]. Для проведения экспериментов в среде Visual Studio С+-+ разработана программа формирования и решения систем булевых нелинейных уравнений второй степени методом XL. В качестве блока замены, являющегося слабым к линейному анализу, взята замена, приведённая в [11]. Получены экспериментальные результаты применения алгебраического криптоанализа к шифрам Магма и PRESENT (см. таблицу) на ПК с процессором IntelCore i5 2,8 ГГц и 8 Гбайт оперативной памяти. Проведён поиск всех выполняющих наборов сформированной SAT-задачи. Найденные значения ключей шифрования оказались эквивалентыми на анализируемых парах открытый текст/шифртекст. При проведении эксперимента для восьми раундов Магма были зафиксированы 68 битов ключа (применялся метод Guess-and-Determine). Результаты экспериментов по алгебраическому анализу шифров PRESENT и Магма SAT-метод XL-метод Число пар открытый текст/ шифртекст Кол-во уравнений Кол-во неизвестных Кол-во литералов Кол-во клозов Кол-во выполняющих наборов Время решения, с Объём памяти, Гбайт Сложность решения, кол-во операций сложения Время решения, с Три раунда шифрования PRESENT 3 3024 576 16083 274534 > 104 73,12 0,98 241,08 23,22 5 5040 832 19968 342522 8 3,74 1,39 243,29 107,39 6 6048 960 23863 410800 1 5,01 1,43 244,08 185,78 Четыре раунда шифрования PRESENT 3 4032 832 18805 313070 > 2 ■ 103 3069,35 1,73 242,33 55,21 5 6720 1216 30585 520686 256 379,58 1,82 244,53 253,51 8 10752 1792 48784 832128 16 527,51 2,79 246,57 1044,72 Пять раундов шифрования Магма (со слабыми к линейному анализу блоками замены) 3 3000 928 5932 39549 4 4,15 1,62 240,64 17,14 7 7000 1952 12459 92707 1 3,36 2,26 244,30 216,27 Пять раундов шифрования Магма (с блоками замены S(X)=X) 3 3000 928 5338 32873 40 520,89 1,73 240,64 17,14 5 5000 1440 8787 54647 1 4,92 1,85 242,85 79,25 Пять раундов шифрования Магма 3 3000 928 10596 152045 1 24,96 1,42 240,64 17,14 Восемь раундов шифрования Магма (со слабыми к линейному анализу блоками замены) 4 5376 2048 15395 110844 4096 1843,67 4,59 243,92 166,3 Восемь раундов шифрования Магма (с блоками замены S(X)=X) 4 5376 2048 13764 92370 1024 1374,12 3,86 243,92 166,3 Восемь раундов шифрования Магма 4 5376 2048 30062 431267 1 416,31 3,6 243,92 166,3

Скачать электронную версию публикации