Algebraic cryptanalysis of round-reduced lightweight ciphers simon and Speck.pdf Низкоресурсная криптография - направление исследований, представляющее интерес в настоящее время. Это связано с тем, что влияние и использование RFID-меток, ПЛИС, смарт-карт, мобильных телефонов, сенсорных сетей и других криптографических алгоритмов для устройств с ограничениями на используемые ресурсы постоянно растёт и приобретает всё большую важность. Низкоресурсные криптографические примитивы предназначены для обеспечения эффективности и безопасности при ограниченном объёме ресурсов. В этом случае возникает проблема поиска компромисса между безопасностью и эффективностью. В 2013 г. Агентство национальной безопасности США представило семейства Simon и Speck низкоресурсных блочных шифров. Шифр Simon был оптимизирован для производительности на аппаратных устройствах, а Speck - для производительности в программном обеспечении. Но было подчеркнуто, что оба семейства работают исключительно хорошо как в аппаратном, так и в программном обеспечении, обеспечивая гибкость платформы, требуемую будущими приложениями. По состоянию на октябрь 2018 г. шифры Simon и Speck были стандартизированы Международной организацией по стандартизации (ISO) в рамках стандарта радиоинтерфейса RFID (радиочастотной идентификации). Эти шифры являются представителями LRX- и ARX-структур блочных шифров, основой которых является явное использование нелинейных алгебраических операций вместо S-блоков. Это обуславливает интерес к алгебраическому анализу данных шифров. Алгебраический анализ Simon проведён в [1], комбинация алгебраического и усечённого дифференциального криптоанализа шифра Simon от малого числа раундов рассмотрена в [2]. Алгебраические атаки представлены SAT-решателем и алгоритмом ElimLin. Основная идея алгебраического криптоанализа состоит в составлении сложной системы булевых уравнений, описывающих преобразование шифра. Система строится на основе полностью известного алгоритма шифрования. Зашифрование на неизвестном криптоаналитику ключе некоторого количества открытых текстов позволяет провести подстановку в уравнения системы значений векторов открытых текстов и шифртек-стов. На следующем этапе осуществляется решение системы с помощью различных методов относительно битов ключа. Для анализа шифров было автоматизировано построение системы уравнений, описывающей преобразования раундов шифров. Simon - семейство низкоресурсных блочных шифров, разработанных для оптимальной производительности аппаратного обеспечения [3]. Имеет структуру классической схемы Фейстеля, на каждом раунде 2п-битный вход раунда делится на две n-битные половины. К левой половине L применяется раундовая нелинейная небиективная функция F : Fn Fn. К выводу функции применяется операция XOR с правой половиной R и ключом k, и две половины меняются местами (рис. 1). Для шифра Simon, вводя новую переменную для каждого выхода побитовой операции ©, для описания T раундов получаем n(T - 2) квадратичных уравнений с n(T - 2) + k неизвестными, где n - размер слова; T - количество раундов; k - длина ключа. При генерации ключа получается n(T - m) уравнений. В результате для шифра Simon с T раундами генерируется n(T - m) + n(T - 2) уравнений. Количество ключей m зависит от размера входного блока 2n и количества раундов T. Speck - семейство низкоресурсных блочных шифров, обеспечивающих отличную производительность как в аппаратном, так и в программном обеспечении, но оптимизированных для работы на микроконтроллерах [3]. В каждом раунде 2п-битных входа делятся на две n-битные половины. Каждый раунд Speck применяет операции конъюнкции, циклического сдвига влево и вправо, а также сложения по модулю 2n. Параметры имеют следующие значения: а = 7 и в = 2, если n =16 (размер блока равен 32) и а = 8 и в = 3 в противном случае. На рис. 2 представлена схема шифрования данного шифра. Ключевое расписание шифра Speck использует раундовую функцию для генерации раундовых ключей. Рис. 1. Схема раундового преобразования Рис. 2. Схема раундового преобразования шифра Simon [3] шифра Speck [3] В шифре Speck, вводя на каждом раунде новые переменные, получим следующие количества уравнений и неизвестных: (7n - 3)(T - 1) + (8n - 3)(T - 1) + 2n, 2(8n - 3)(T - 1) + 2n, m=1, m = 2, 3 , 4 , n(5T - 4), n(6T - 5), m=1, m = 2, 3 , 4 . где e - число уравнений; u - число неизвестных. 1. Линеаризация Проведение криптоанализа на небольшом количестве раундов (например, 3 и 4) с выбором стандартных характеристик нецелесообразно, так как ключи не строятся на основе исходных и между ними не будет никакой связи. Поэтому в данной работе рассматриваются шифры с m = 1 для T G {3, 4}. Рассмотрены атаки, основанные на линеаризации. Идея простой линеаризации состоит в том, чтобы присвоить каждому одночлену исходной системы новую переменную. Система после переобозначения становится линейной и решается, например, методом Гаусса. Затем для решений линейной системы проверяется, являются ли они решениями исходной нелинейной системы уравнений. Количество различных одночленов в исходной системе определяет количество переменных П в системе линейных уравнений, эффективность линеаризации зависит от ранга r этой системы. Множество решений не пусто, его мощность равна 2п-г 0, поэтому для оценки производительности необходимо проанализировать границы значений nz и r. Рассматривая алгоритм шифрования, можем оценить количество различных мономов для каждого раунда шифра Simon. Для каждой операции вводятся новые переменные и проводится переобозначение при замене Li+1 и Ri+1; в результате получаем следующую оценку количества мономов M: M < 6nT. В шифре Speck основным методом сохранения степени является введение новых переменных для выходных битов нелинейных операций. В этом случае степень не будет превышать 2. На каждом раунде вводится 28n новых переменных. В системе уравнений, описывающей сложение по модулю 2п, имеется всего 5(7n - 8) мономов. На практике оказалось, что различных мономов в системе уравнений сложения по модулю 2п не больше 25n - 18. Таким, образом, количество различных мономов на каждом раунде шифра Speck не больше 28n - 18. Итоговая оценка числа различных мономов, исключая такие, которые образуются при генерации ключей (все уравнения линейны), имеет вид M < (28n - 18)T. XL-атака представлена в [4, 5]. На вход поступает система из m полиномиальных уравнений от n неизвестных степени d, выбирается степень D > d, все уравнения исходной системы умножаются на одночлены степени D - d или меньше, система линеаризуется и на выходе получаем одно или несколько решений. Для случая d = 2 и D = d + 1 анализ этой атаки [6] показывает, что единственное решение, вероятно, будет найдено, если m n2/6. Алгоритм ElimLin описан в [7]. Его суть-поиск скрытых линейных уравнений, существующих в идеале, порождённом данной системой уравнений. Этот алгоритм состоит из двух последовательных шагов: 1) исключение Гаусса: в линейной оболочке исходной системы отыскиваются все линейные уравнения; 2) замена: переменные итеративно выражаются с помощью найденных линейных уравнений, получаемые выражения подставляются в исходную систему. В табл. 1 и 2 приведены результаты для простой линеаризации, XL-метода и ElimLin. Полученные данные позволяют сравнить эффективность этих методов для Simon и Speck. Для XL-метода D = 3. Сложность полного перебора составляет 216 (при n = 16, m = 1). Как видно из табл. 1, метод линеаризации начиная с 4-5 раундов даёт худшие результаты, чем атака полным перебором. Использование метода простой линеаризации для T 4 и XL-метода для пяти раундов (шифра Simon) не улучшает поиск решения по сравнению с полным перебором. Т а б л и ц а 1 Результаты применения атак, основанных на линеаризации Шифр, параметры Метод Кол-во уравнений Кол-во переменных Кол-во мономов Кол-во решений Simon, T = 3, m =1 Линеаризация 48 32 48 4, только одно явл-ся ключом XL-метод 1584 32 992 1 Simon, T = 4, m =1 Линеаризация 64 48 80 65536 XL-метод 3136 48 2616 256, только одно явл-ся ключом Simon, T = 5, m =1 Линеаризация 80 64 112 232 XL-метод 5200 64 5008 2336 Speck, T = 3, m =1 Линеаризация 500 176 1236 - XL-метод 88500 176 185216 - Т а б л и ц а 2 Результаты применения метода ElimLin Шифр, параметры (Кол-во уравнений, кол-во лин. уравнений) (Кол-во уравнений, кол-во лин. уравнений) после ElimLin Simon, T = 3, m =1 (48, 32) (48, 32) Simon, T = 5, m =1 (80, 32) (80, 48) Speck, T = 3, m =1 (500, 132) (307, 137) Speck, T = 5, m = 2 (1032, 296) (654, 297) 2. SAT-решатели Задача булевой выполнимости (SAT)-это задача принятия решения, в которой для произвольной булевой формулы возникает вопрос, существует ли такое значение переменных, что формула имеет значение true. Эта задача является NP-трудной. Криптоанализ на основе SAT предполагает два этапа: на первом этапе обеспечивается кодирование SAT, например перевод данной системы из алгебраической нормальной формы (АНФ) в конъюнктивную нормальную форму. Мы используем конвертер anf2cnf [8] из библиотеки PolyBoRi, интегрированной в Sage. На втором этапе полученный экземпляр SAT-задачи решается с помощью SAT-решателя. Для криптографических систем часто применяются SAT-решатели CryptoMiniSat [9] и Lingering (с его параллельными версиями Plingeling и Treengeling) [10]. Мы применяем SAT-решатели CryptoMiniSat (в Sage ver. 6.10) и Lingeling, Plingeling, Treengeling на ПК со следующими параметрами: Core i5-4690 CPU 3,5 ГГц (х4), 12 Гбайт оперативной памяти. Экспериментальные результаты для шифров Simon и Speck представлены в табл. 3 и 4. Рассмотрены два генератора систем уравнений в форме АНФ для шифра Simon: в одном все раундовые ключи являются независимыми переменными, в другом все они представлены алгоритмом ключевого расписания. Та б л и ц а 3 Результаты SAT-решателя для шифра Simon Параметры Кол-во ур-ий Кол-во неизв. Параметры SAT SAT Время, c RAM, Мбайт CryptoMiniSat - - T = 8 , m = 2 224 224 384 лит., Plingeling 69811,9 120,5 (с раунд. ключом) 2528 клоз Treengeling 4775,5 260,3 Lingeling 12702,81 182 CryptoMiniSat - - T = 8 , m = 2 128 128 368 лит., Plingeling 845,4 26,6 (ключ. расписание) 4448 клоз Treengeling 1188,8 169,2 Lingeling 4426,12 95 CryptoMiniSat - - T = 9 , m = 2 144 144 480 лит., Plingeling >260174,3 >180,7 (ключ. расписание) 6448 клоз Treengeling 47799,2 620,3 Lingeling 24547,91 172 CryptoMiniSat - - T = 10 , m = 2 160 160 560 лит., Plingeling - - (ключ. расписание) 8096 клоз Treengeling 17554,9 458,8 Lingeling 60776,91 234 Та б л и ц а 4 Результаты SAT-решателя для шифра Speck Параметры Кол-во Кол-во Параметры SAT Время, c RAM, ур-ий неизв. SAT * Мбайт CryptoMiniSat 0,56 T = 3 , m = 1 500 176 1460 лит., 11020 клоз Plingeling Treengeling 0,9 0,97 9,6 4 Lingeling 0,2 1,9 CryptoMiniSat 21,4 T = 4 , m = 2 782 320 2492 лит., Plingeling 3,0 17,3 17380 клоз Treengeling 8,25 15 Lingeling 61,4 14,8 CryptoMiniSat - - T = 5 , m = 2 1032 416 3312 лит., Plingeling - - 23184 клоз Treengeling 14448,17 278 Lingeling - - CryptoMiniSat - - T = 6 , m = 2 1282 512 4132 лит., Plingeling - - 28988 клоз Treengeling 123353,82 546 Lingeling - - Прочерки в таблицах означают, что SAT-решателю не удалось найти решение системы; для шифра Speck CryptoMiniSat при T = 3. 4 не выдал размер файла. 3. Метод Раддума - Семаева Данный подход к решению разреженных полиномиальных систем уравнений над полем F2 был представлен Г. Раддумом и И. Семаевым в работе [11]. Анализ и некоторые свойства можно найти в [12]. По исходной системе уравнений строится граф. Вершины соответствуют каждому уравнению (верхний набор вершин), также присутствуют вершины, образуемые пересечением наборов переменных соответствующих уравнений (нижний набор вершин). Каждой вершине приписан список возможных означиваний соответствующих переменных. Обработка и поиск решения осуществляется с помощью так называемой процедуры Agreeing-Gluing (согласования-склейки). Процедура согласования берет две соседние вершины и обновляет их списки, удаляя векторы, которые имеют разные подвекторы для общих переменных. Процедура склеивания заменяет две вершины новой вершиной с обновлённым списком означиваний. В качестве результатов использования этого алгоритма для атаки на Simon и Speck мы приводим только максимальное количество раундов, для которых алгоритм завершился за допустимое время. Стоит отметить, что временная сложность сильно зависит от эвристики, используемой для запуска процесса согласования, будь то (частичное) разделение или склейка. Для шифра Simon максимальное число переменных в уравнении зависит от количества раундов и ключей. Для шести переменных количество уравнений равно n(T - 2) + n(T - m). Благодаря введению новых переменных в каждый раунд шифра Speck количество переменных на каждом раунде не зависит от количества раундов T и ключей m. Максимальное количество переменных в одном уравнении равно 6; количество уравнений и переменных представлено в табл. 5 для m = 1 и табл. 6 для m = 2. 3. 4. Т а б л и ц а 5 Количество переменных каждого уравнения шифра Speck, m = 1 Кол-во переменных Кол-во уравнений 6 2(T - 1)(2n - 4) 5 2(T - 1)n 4 6(T - 1)n +(T - 2)n 3 2(n + 1)(T - 1) 2 3n Т а б л и ц а 6 Количество переменных каждого уравнения шифра Speck, m = 2, 3, 4 Кол-во переменных Кол-во уравнений 6 2(T - 1)(2n - 4) 5 2(T - 1)n 4 6(T - 1)n +(T - 2)n 3 2(n +1)(T - 1) 2 (T - 1)n + 3n Алгоритм Agreeing-Gluing был запущен для Simon до 9 раундов, для Speck - до 6 (табл. 7). Таб лица 7 Параметры алгоритма Раддума - Семаева для шифров Simon и Speck Параметры Количество уравнений Количество неизвестных Верхний набор Нижний набор Шифр Simon T = 7, m = 2 112 112 112 800 T = 8, m = 2 128 128 128 1072 T = 9, m = 2 144 144 144 1600 Шифр Speck T = 3, m = 1 500 176 500 558 T = 4, m = 2 782 320 782 749 T = 5, m = 2 1032 416 1032 1005 T = 6, m = 2 1282 512 1282 1229 4. Анализ полученных результатов и заключение В работе предпринята попытка оценить устойчивость шифра Speck к алгебраическому криптоанализу с помощью различных методов. Экспериментальные результаты показывают, что методы алгебраического анализа являются перспективным способом анализа надёжности современных шифров (в частности, низкоресурсных). Применительно к шифрам Simon и Speck показано, что методы, основанные на линеаризации, неэффективны уже при малом количестве раундов. С использованием SAT-решателя для шифра Simon решение найдено до 10 раундов включительно, для шифра Speck - до 6 раундов. Применение алгоритма Раддума - Семаева даёт результат для шифра Simon до 9 раундов, Speck - до 6. Результаты алгебраического анализа показывают, что включение дополнительных нелинейных операций (например, операции сложения по модулю 2n) значительно увеличивает время атаки и объём используемой памяти. Поэтому рассмотренные методы более эффективны для криптоанализа шифра Simon, чем для Speck. В то же время разреженность систем уравнений, описывающих шифры Simon и Speck, достаточно высока, что приводит к мысли о целесообразности использования метода Раддума - Семаева, разработанного специально для таких систем. В дальнейшем планируется провести теоретическую оценку сложности алгебраического анализа для полнораундовых шифров Simon и Speck, а также оценить эффективность использования алгоритма Бухбергера.

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