Разработка и исследование алгоритмов оценки защищенности информации на основе алгебраического анализа Маро Екатерина Александровна

Содержание к диссертации

Введение

1. Исследование методов оценки защищенности информации 14

1.1 Метод полного перебора на ключевом пространстве 18

1.2 Дифференциальный анализ 20

1.3 Линейный анализ 23

1.4 Алгебраические методы анализа 27

1.5 Выводы 30

2. Методы алгебраического анализа преобразований на основе замены и сложения по модулю 2n 32

2.1 Решение систем булевых алгебраических уравнений с помощью методов линеаризации 32

2.1.1 Метод линеаризации. 32

2.1.2 Метод расширенной линеаризации 33

2.1.3 Метод разреженной расширенной линеаризации 39

2.1.4 Алгоритм исключения Гаусса для булевых уравнений

2.2 Решение системы булевых алгебраических уравнений с помощью SAT- решателей 43

2.3 Выводы 49

3. Разработка алгоритмов алгебраического анализа оценки защищенности преобразований на основе замены и сложения по модулю 2n 50

3.1 Разработка алгоритмов формирования систем булевых уравнений для нелинейных преобразований 50

3.1.1 Разработка алгоритма формирования системы булевых уравнений для нелинейных преобразований замены 50

3.1.2 Разработка алгоритма формирования булевых уравнений для нелинейных преобразований сложения по модулю 2n 58

3.2 Разработка алгоритмов решения систем булевых нелинейных уравнений 61

3.2.1 Разработка алгоритма решения системы булевых уравнений с помощью методов линеаризации 62

3.2.2 Разработка алгоритма поиска решений с использованием SAT-решателя CryptoMiniSat в среде SageMath 64

3.3 Методики проведения алгебраического анализа 67

3.4 Выводы 70

4. Применение алгоритмов алгебраического анализа для оценки защищенности информации при использовании алгоритмов ГОСТ 28147-89 (ГОСТ 34.12-2015 п =64) и Present 72

4.1 Описание алгоритма ГОСТ 28147-89 (ГОСТ Р 34.12-2015 п =64) 72

4.2 Разработка алгоритма вычисления таблиц подстановок секретных блоков замены ГОСТ 28147-89 74

4.3 Разработка алгоритма алгебраического анализа двух раундов ГОСТ 28147-89 с использованием фиксированных блоков замены 84

4.4 Разработка алгоритма алгебраического анализа трех раундов ГОСТ с фиксированными блоками замены 88

4.5 Разработка алгоритма алгебраического анализа трех раундов ГОСТ 28147-89 с фиксированными блоками замены 92

4.6 Разработка алгоритма алгебраического анализа четырех раундов ГОСТ с фиксированными блоками замены 95

4.7 Разработка алгоритма алгебраического анализа пяти раундов ГОСТ с фиксированными блоками замены 98

4.8 Алгебраический анализ алгоритма «Магма» 100

4.9 Алгебраический анализ алгоритма «Магма» со «слабыми» блоками замены 101

4.10 Разработка алгоритма поиска открытых текстов, для которых уменьшено число выполняемых раундов преобразований

4.10.1 Экспериментальные результаты поиска подходящих открытых текстов для алгоритма ГОСТ 28147-89 104

4.10.2 Экспериментальные результаты поиска подходящих открытых текстов для алгоритма ГОСТ 34.12-2015 (п =64)

4.11 Алгебраический анализ алгоритма Present Ill

4.12 Оценка защищенности информации на основе алгебраического анализа 116

4.13 Выводы 122

Библиографический список

• Линейный анализ
• Метод разреженной расширенной линеаризации
• Разработка алгоритма формирования системы булевых уравнений для нелинейных преобразований замены
• Разработка алгоритма алгебраического анализа четырех раундов ГОСТ с фиксированными блоками замены

Введение к работе

Актуальность темы исследования. В сфере обеспечения информационной безопасности важной задачей является исследование методов оценки защищенности конфиденциальной информации. Для многих систем защиты информации оценка защищенности информации может быть сведена к поиску решений систем булевых нелинейных уравнений и анализу трудоемкости различных методов решения подобных систем. В виде систем булевых нелинейных уравнений могут быть представлены, например, следующие задачи, возникающие в сфере обеспечения информационной безопасности:

аудит состояния защищаемого объекта;

проверка корректности функционирования программ;

анализ надежности систем защиты конфиденциальной информации (в том числе при использовании криптографических преобразований).

Многие современные средства защиты конфиденциальной информации основываются на использовании примитивов замены и сложения по модулю 2ⁿ. Учитывая обширность применения подобных средств защиты информации, следует уделять внимание их надежности, в том числе и стойкости используемых преобразований к различным видам анализа. В ходе проведенного исследования методов оценки защищенности конфиденциальной информации при использовании средств на основе примитивов замены и сложения по модулю 2ⁿ было отмечено, что в научном сообществе разрабатываются и активно исследуются алгебраические методы анализа, основанные на описании процесса защиты информации в виде систем булевых нелинейных уравнений и последующем их решении¹. В отличие от статистических методов линейного и дифференциального анализа, применение алгебраических методов позволяет вычислять секретную информацию при наличии меньшего числа известных данных. Также важным преимуществом алгебраических методов по сравнению со статистическими методами является то, что эффективный алгоритм алгебраического анализа шифров требует меньших вычислительных ресурсов.

¹ M. Albrecht, C. Cid «Algebraic Techniques in Differential Cryptanalysis» // 16th International Workshop, FSE 2009 Leuven, Belgium, February 22-25, 2009, pp. 193-208.

G.Bard «Algebraic Cryptanalysis» // Springer US, 2009.

N. T. Courtois, B. Debraize «Specific S-Box Criteriain Algebraic Attacks on Block Ciphers with Several Known Plaintexts» // Second Western European Workshop, WEWoRC 2007, Bochum, Germany, July 4-6, 2007.

А.А. Семенов, О.С. Заикин, Д.В. Беспалов, А.А. Ушаков «SAT-подход в криптоанализе некоторых систем поточного шифрования» // Вычислительные технологии Том 13, № 6, 2008.

N. T. Courtois, G. Bard «Algebraic Cryptanalysis of the Data Encryption Standard» // 11-th IMA Conference, 2007, pp. 152-169.

А.А. Семенов «Алгоритмы решения задачи о булевой выполнимости (SAT) и их применение в криптоанализе» // PHDays 2015.

Так как в общем виде оценку защищенности информации в разрабатываемых и используемых средствах защиты информации с помощью алгебраических методов анализа можно свести к оценке сложности нахождения решения системы булевых уравнений, то целесообразно еще на этапе разработки средства защиты учитывать структуру подобной системы. В научной литературе не представлены алгоритмы и программные средства, позволяющие формировать и исследовать структуру системы булевых нелинейных уравнений для произвольного заполнения таблиц замены и длин входных векторов преобразований на основе примитивов замены и сложения по модулю 2^П Поэтому каждый раз необходимо проводить отдельный анализ исследуемого преобразования, направленный на предварительную оценку вычислительной сложности и объемов задействованной оперативной памяти, что усложняет решение основной задачи - непосредственное проведение алгебраического анализа преобразования. Учитывая выше сказанное, важной задачей является разработка эффективных универсальных алгоритмов формирования систем булевых нелинейных уравнений для наиболее распространенных примитивов, используемых в средствах защиты информации, а также исследование методов решения подобных систем. Моделирование алгебраического анализа преобразований, основанных на примитивах замены и сложения по модулю 2^П, было проведено на примере алгоритмов Магма (сложение по модулю 2³²) и ГОСТ Ф (сложение по модулю 2), построенных по принципу сети Фейстеля.

Целью работы является разработка и исследование алгоритмов оценки защищенности информации на основе формирования и анализа систем булевых нелинейных уравнений при использовании преобразований замены и сложения по модулю 2^П.

Исходя из поставленной цели, определяется перечень основных задач:

- разработка и реализация алгоритмов формирования систем булевых

нелинейных уравнений для преобразований замены и операции сложения по модулю 2^П;

- разработка и исследование алгоритмов решения сформированных систем

булевых нелинейных уравнений;

- применение разработанных алгоритмов для моделирования оценки

защищенности информации на основе алгебраического анализа блочного преобразования, на примере алгоритмов ГОСТ Ф и «Магма».

Данное научное направление исследования относится к областям исследований пункты 9, 10 Паспорта специальности 05.13.19 «Методы и системы защиты информации, информационная безопасность».

Объектом исследования являются методы оценки защищенности информации на основе оценки сложности нахождения решения системы булевых нелинейных уравнений для наиболее распространенных примитивов, используемых в средствах защиты информации.

Предметом исследования являются алгоритмы формирования и решения систем булевых нелинейных уравнений, описывающих операции замены и сложения по модулю 2^П.

Методы исследования. При выполнении диссертационного исследования использованы: теория вероятностей, теория конечных полей, теория множеств, теория кодирования информации. При программной реализации разработанных алгоритмов формирования систем булевых уравнений использовались средства MS Visual Studio C++. Экспериментальная проверка разработанных алгоритмов алгебраического анализа реализована с использованием системы компьютерной алгебры SageMath.

Научная новизна полученных в диссертации основных результатов заключается в следующем:

1. Разработаны алгоритмы формирования и решения систем булевых нелинейных уравнений для преобразований замен и операции сложения по модулю 2ⁿ, отличающиеся от существующих тем, что позволяют обрабатывать произвольные длины векторов, а также выполнять предварительную оценку времени решения и требуемых объемов памяти при проведении алгебраического анализа.

2. Предложен алгоритм и впервые определена вычислительная сложность решения систем булевых нелинейных уравнений для различного числа раундов преобразований на примере алгоритмов ГОСТ и «Магма» с помощью метода расширенной линеаризации.

3. Получены сравнительные оценки защищенности информации к алгебраическому анализу методами SAT-решения и расширенной линеаризации на примере алгоритмов ГОСТ Ф и «Магма».

4. Проведены обширные эксперименты по моделированию оценки защищенности информации на основе алгебраического анализа, показывающие высокую эффективность предложенных алгоритмов формирования и решения систем уравнений для сокращенного числа раундов алгоритмов, на примере ГОСТ и «Магма».

Практическая значимость.

5. Разработан программный модуль формирования и решения систем булевых нелинейных уравнений для преобразований замены и операции сложения по модулю 2ⁿ, используемый для оценки защищенности информации.

6. Разработан программный модуль, позволяющий вычислить размеры системы булевых нелинейных уравнений и проводить оценку защищенности информации для задаваемой структуры преобразований на основе операций замены и сложения по модулю 2ⁿ.

7. Разработан программный модуль восстановления таблиц блоков замены.

8. Разработан программный модуль поиска открытых текстов, сокращающих количество реально выполняемых преобразований алгоритма «Магма» с 32 до 16 раундов при фиксированных ключах.

Основные результаты, выносимые на защиту: 1. Разработанный универсальный алгоритм формирования систем булевых нелинейных уравнений для преобразований замены и сложения по модулю 2ⁿ, отличающийся от известных возможностью обработки этих примитивов с произвольной длиной векторов.

2. Разработанные универсальные алгоритмы решения систем булевых нелинейных уравнений для различного числа раундов преобразований на основе операций замены и сложения по модулю 2^П, позволяющие выполнять предварительную оценку сложности решения системы и проводить оценку защищенности информации методами алгебраического анализа.

3. Методики алгебраического анализа, позволяющие эффективно производить алгебраический анализ для наиболее распространенных преобразований замены и сложения по модулю 2^П, используемых при защите конфиденциальной информации.

4. Численные результаты моделирования алгебраического анализа криптографических алгоритмов в зависимости от количества раундов, показывающие высокую эффективность разработанных алгоритмов. При моделировании алгебраического анализа пяти раундов преобразований алгоритма «Магма» разработанные алгоритмы позволили вычислить 160-битный ключ за 24,96 сек. при известных 3 парах текстов.

Внедрение результатов работы. Результаты, полученные в ходе работы над диссертацией, использованы:

1. В грантах РФФИ:

№ 09-07-00245-а «Разработка и исследование параллельных алгоритмов оценки криптографической стойкости защиты информации».

№ 12-07-31032-мол_а «Разработка и исследование методов алгебраического анализа симметричных алгоритмов шифрования».

№12-07-31120-мол_а «Разработка и исследование последовательных и параллельных алгоритмов анализа стойкости современных симметричных алгоритмов шифрования».

№12-07-33007-мол_а_вед «Оценка уязвимости современных криптосистем с использованием методов анализа, основанных на решении систем уравнений».

№15-37-20007 молавед «Разработка и исследование последовательных и параллельных алгоритмов оценки стойкости проектного стандарта шифрования ГОСТ».

2. В учебном процессе в Южном федеральном университете (ЮФУ) на кафедре
Безопасности информационных технологий по дисциплине
«Криптографические методы и средства обеспечения информационной
безопасности».

Использование результатов диссертационной работы подтверждено актами об использовании.

Апробация работы. Основные результаты, полученные в ходе работы над диссертацией, докладывались и обсуждались на следующих Всероссийских и Международных конференциях: 1. Всероссийская молодежная конференция по проблемам информационной

безопасности «Перспектива» (ТТИ ЮФУ, г. Таганрог, 2009г.). 2. XI Международная научно-практическая конференция «Информационная безопасность» (ТТИ ЮФУ, г. Таганрог, 2010г.).

3. X Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТТИ ЮФУ, г. Таганрог, 2010г.).

4. XV Всероссийская научно-техническая конференция студентов, молодых ученых и специалистов (Рязанский государственный радиотехнический университет, г. Рязань, 2010 г.).

5. Конференция «РусКрипто’2011» (г. Москва, 2011г.).

6. Конгресс по интеллектуальным системам и информационным технологиям «IS&IT’11» (ТТИ ЮФУ, п. Дивноморский, 2011г.).

7. The 4th international conference on Security of information and networks (г. Сидней, 14-19 ноября 2011г.).

8. XII Международная научно-практическая конференция «Информационная безопасность » (ТТИ ЮФУ, г. Таганрог, 2012г.).

9. XI Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТТИ ЮФУ, г. Таганрог, 2012г.).

10. The 5th international conference on Security of information and networks (г. Джайпур, 22-27 сентября 2012г.).

11. Всероссийский конкурс научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий (г. Белгород, 2012г.).

12. XIII Международная научно-практическая конференция «Информационная безопасность» (ТТИ ЮФУ, г. Таганрог, 2013г.).

13. VII Международная научно-практическая конференция по всем наукам «Актуальные вопросы мировой науки в ХХI веке» (г. Казань, 2013г.).

14. IV Научный форум студентов, магистрантов, аспирантов и молодых ученых «Наука в исследованиях молодых» (г. Таганрог, 2013г.).

15. XII Всероссийская научная конференция молодых ученых аспирантов и студентов «Информационные технологии, системный анализ и управление» (ЮФУ, г. Таганрог, 2014 г.)

16. VII Международная интернет-конференция молодых ученых, аспирантов, студентов «Инновационные технологии: теория, инструменты, практика (INNOTECH)» (г. Пермь, 2015 г.)

17. The 6th international workshop on Cryptography, Robustness, and Provably Secure Schemes for Female Young Researchers (CrossFyre) (г. Дармштадт, 2016 г.)

Публикации. Результаты, полученные в диссертационной работе, нашли отражение в 31 печатных трудах, среди них 16 статей (6 статей опубликованы в журналах, рекомендованных ВАК для представления основных результатов кандидатский и докторский диссертационных работ; 5 статей опубликованы в изданиях, индексируемых в базе данных Scopus), разделы в двух монографиях, материалы 13 докладов. Имеется свидетельство об официальной регистрации программ для ЭВМ.

Объем и структура диссертации.

Диссертация состоит из введения, 4 глав, заключения, библиографического списка и 12 приложений. Объем диссертации 228 страниц, включая 24 рисунка и 31 таблицу. Объем приложений 96 страниц. Список литературы включает 80 наименований.

Линейный анализ

Стойкость системы защиты можно задать двумя характеристиками: надежность самого алгоритма защиты и длина ключа. Стойкость алгоритма к методу полного перебора определяется длиной ключа и скоростью выполнения операции преобразования. Метод полного перебора на ключевом пространстве заключается в проверке всех возможных значений ключа на множестве целых чисел {0,...,2к -1), где к- длина ключа шифрования. С учетом теории вероятностей в 50% случаях правильный ключ будет найден за 2 "1 попыток. Метод полного перебора на ключевом пространстве заключается в расшифровании шифртекста и проверке, получился ли для используемого значения ключа верный открытый текст. Таким образом, для анализа алгоритма блочного шифрования AES, длина ключа которого может быть равна 128, 192 и 256 битам, вычислительная сложность анализа методом полного перебора будет составлять 2, 2 и 2 соответственно, так как потребуется проверить все возможные значения ключей шифрования. Для алгоритма ГОСТ 28147-89 вычислительная сложность анализа методом полного перебора на ключевом пространстве составит 2 . Рассчитаем примерное время вычисления ключа алгоритмов шифрования AES и ГОСТ 28147-89. Пусть на данный момент компьютеры способны обработать 10 миллионов 127/9 ключей AES28 в секунду, тогда с вероятностью ключ будет найден за 2 10 97 128/1 998 2 секунд, гарантированно ключ будет вычислен за 2 02 секунд. Опираясь на работу [18], можно сократить сложность нахождения ключа с вероятностью 126 190 254 1 методом полного перебора до 2 , 2 , 2 для алгоритмов AES28, 192, 256 соответственно. Для алгоритма ГОСТ 28147-89 в режиме простой замены с вероятностью ключ будет найден за 2 операций шифрования и с вероятностью

Для повышения быстродействия алгоритмов полного перебора на ключевом пространстве применяют методы параллельного программирования. Пусть задача поиска ключа шифрования выполняется на N процессорах. Тогда все множество ключей К следует разбить на непересекающиеся подмножества K1,...,KN. Затем кластер из N процессоров перебирает ключи таким образом, что каждый /-ый процесс перебирает ключи из подмножества Kt, /є{1,2,...,7V}. Как только на одном из процессоров кластера находится верный ключ шифрования, работа программы поиска завершается. В случае произвольного разбиения множества всех возможных ключей на подмножества для параллельной проверки сложность (среднее число шагов) поиска составит \К\/ N, гдеу - мощность множества возможных ключей, N - количество процессоров. Даже с учетом роста вычислительной мощности используемых суперкомпьютеров (рисунок 1), рассматриваемые алгоритмы останутся вычислительно стойкими еще долгое время. Годы Рисунок 1. График роста вычислительной мощности (производительности) суперкомпьютеров (TOP500). Как видно, вычислительная стойкость современных алгоритмов защиты информации к методам полного перебора велика и данные методы не оказывают реального влияния на стойкость. Метод полного перебора является эталонным, поэтому алгоритм шифрования перестает считаться вычислительно стойким в случае появления методов более эффективных, чем метод полного перебора. В настоящее время стойкость алгоритмов в большинстве своем зависит от надежности преобразований самого алгоритма шифрования.

Метод полного перебора на ключевом пространстве может быть применим в сочетании с другими методами анализа шифров. Например, если, используя метод дифференциального анализа, удается сузить область поиска возможных ключей, то дальнейший поиск верного ключа шифрования может быть проведен методом полного перебора в заданной области [19].

Метод дифференциального анализа был предложен в 1990 г. Э. Бихамом и А. Шамиром [2] для анализа систем защиты, подобных Data Encryption Standard (DES). Специалисты продемонстрировали, что исходный алгоритм DES оказался довольно устойчивым к дифференциальному методу анализа, однако внесение даже незначительного изменения структуры алгоритма делает его более уязвимым. Авторы метода нашли способ атаки с помощью дифференциального анализа на выбранном открытом тексте для алгоритма DES, который оказался эффективнее метода полного перебора.

Суть метода дифференциального анализа заключается в изучении пар открытых текстов, между которыми есть некоторая разность (с анг. difference). Для разных алгоритмов шифрования разность можно определять различными методами. Так для алгоритма DES разность формируется операцией сложения по модулю два открытых текстов P 1 и P2, т.е.: А = P 1 Ф P2. Дифференциальный метод требует проведения анализа множества пар текстов с определенной разностью, который позволяет найти фрагмент ключа (или полностью ключ шифрования) с некоторой наибольшей вероятностью

Метод разреженной расширенной линеаризации

Метод расширенной разреженной линеаризации (eXtended Sparse Linearization, XSL) предложили Н. Куртуа и Д. Пейпжик в работе [41]. Этот метод использует такое свойство нелинейных систем уравнений, как разреженность уравнений, т.е. уравнения системы не содержат многих возможных одночленов второй степени. Условие разреженности системы: где t – число одночленов в уравнениях, n – число неизвестных, d – максимальная степень одночленов системы.

Существуют различные версии алгоритма расширенной разреженной линеаризации. Существует два вида подобных методов анализа: в первом случае не используются уравнения алгоритма выработки ключей (здесь необходимо некоторое количество известных пар текстов), второй случай более специализированный, в нем используются уравнения алгоритма выработки ключей (этот способ применим даже с единственной парой открытый текст /шифртекст).

Алгоритм расширенной разреженной линеаризации предложен для работы только со специальными типами шифров. Алгоритм защиты информации должен отвечать следующим требованиям: S-блоки должны быть такими, чтобы их можно было описать с помощью сверхопределенной системы квадратичных уравнений. Для возможности применения второго варианта атаки (включающего алгоритм выработки ключей), необходимо, чтобы данный алгоритм получения ключей имел схожую структуру с алгоритмом шифрования (например, это условие выполняется для шифра Rijndael).

Алгоритм расширенной разреженной линеаризации состоит из следующих 4 шагов: а) Обработка имеющейся системы уравнений путем выбора конкретного набора одночленов и уравнений, которые будут использоваться в дальнейших этапах алгоритма. б) Произвольный выбор значения параметра G и умножение выбранных на предыдущем этапе уравнений на результаты произведений (G — 1) выбранных одночленов (это основа XSL атаки и необходимо получить большое число уравнений, в которых элементы представляют собой произведения выбранных ранее одночленов). в) Применение Т метода, в котором некоторые выбранные уравнения умножаются на переменные. г) Применение метода линеаризации, путем представления каждого одночлена в виде новой переменной и выполнения метода исключения Гаусса, в результате чего должно быть получено решение для данной системы. Цель Т метода - создание новых уравнений без получения новых одночленов. Данный шаг проделывается с необходимым числом переменных до тех пор, пока система не будет иметь достаточно линейно независимых уравнений для применения метода линеаризации.

Отличие между методами расширенной линеаризации и расширенной разреженной линеаризации заключается в том, что в расширенной линеаризации происходит умножение системы уравнений на все возможные одночлены в степени не превышающей D — 2, где D задано, в то время как алгоритм расширенной разреженной линеаризации предполагает умножение системы уравнений только на отдельные выбранные одночлены. В методе расширенной разреженно линеаризации отдельно рассматриваются системы уравнений, составленные для каждого блока замены.

В первую очередь необходимо задать значение G. Авторы метода не приводят рекомендаций по вычислению эффективного значения данного параметра. Заметим, что при достаточно большом значении G, данный метод будет очень похож на XL анализ. На каждом этапе следует устанавливать один блок замены, который будет являться активным. Все остальные блоки замены будут пассивными для этого этапа. Далее нужно умножить все уравнения системы активного замены на все произведения G — 1 одночленов, встречающихся в пассивных блоках замены. Данную операцию нужно продолжать до тех пор, пока каждый из блоков замены не выступит в роли активного блока один раз.

Заключительным шагом метода расширенной линеаризации является решение линейной системы методом исключения Гаусса. Суть метода исключения Гаусса заключается в приведении системы линейных уравнений к треугольному виду, путем последовательного исключения неизвестные из уравнений. Рассмотрим подробней общий алгоритм решения линейных систем данным способом.

Пусть задана система уравнений А х = Ъ над полем GF(2) вида: а11 ... a1n ) (ЪЛ А = х = (x1 х2 ... хп), Ъ \ т J V 1т ... пт где х1,...,хп - неизвестные, а1,...,апт - коэффициенты, принимающие значения 0 или 1, b1,...,bn - свободные члены уравнений, п - число неизвестных системы, т -число уравнений системы. В ходе решения системы над полем GF(2) можно использовать следующие преобразования матрицы: Прибавление одной строки матрицы к другой. Перестановка строк матрицы. Перестановка столбцов матрицы.

Разработка алгоритма формирования системы булевых уравнений для нелинейных преобразований замены

При использовании описанного ранее алгоритма формирования системы булевых уравнений получены линейно независимые уравнения для преобразований замены. Для любого блока замены размером s -бит может быть составлено t -2 линейно независимых уравнений. Рассмотрим применение методов линеаризации на примере шифра ГОСТ, построенного по принципу сети Фейстеля.

В одном раунде шифрования задействованы восемь 4-битных блоков замены. В этом случае, для одного раунда шифрования можно составить систему из 168 линейно независимых уравнений, связывающих входные и выходные векторы блока замены и выполняющихся для всех входных векторов. В данной системе встречаются 64 неизвестных, представляющих собой биты входных и выходных векторов S-блоков. В системе содержатся 288 уникальных одночленов. Используя структуру алгоритма ГОСТ можно сократить число неизвестных до 32 битов входного вектора блока замены, а число одночленов до 48.

Для применения метода линеаризации требуется, чтобы число линейно независимых уравнений в системе было больше или равно числу уникальных одночленов, встречающихся в ней (переменных и их произведений). В случае формирования системы для одного раунда такое условие выполняется и система может быть решена применением метода исключения Гаусса (с переобозначением одночленов). Затем следует решить вспомогательную систему, связывающую исходные и новые обозначения переменных, для проверки найденного решения.

При расширении системы булевых алгебраических уравнений для анализа двух раундов исходная система относительно входных и выходных битов блоков замены содержит 336 уравнений, 128 неизвестных и 576 мономов. Используя структуру алгоритма шифрования, включим в систему биты ключа шифрования. Для алгоритма ГОСТ это можно выполнить, представив входной вектор блока замены как сумму по модулю 2 правой части раундового текста и ключа шифрования. Выполнение замены позволило использовать известные данные об открытом тексте и шифртексте и сократить число неизвестных до 64 вместо 128, а число мономов в системе уменьшится до 160. Подобная система может быть решена методом линеаризации без дополнительных изменений.

Для алгоритма ГОСТ 34.12-2015 в систему необходимо добавить еще 64 уравнения и столько же новых неизвестных битов ключа для описания сложения по модулю 2 . Система содержит 568 уравнений, 64 неизвестных бита входного вектора блоков замены и 64 неизвестных бита ключа. Всего в системе встречается 224 уникальных одночленов.

При трех анализируемых раундах шифрования система содержит 504 уравнения, 192 неизвестных и 672 произведений неизвестных. Для алгоритма ГОСТ можно сократить число неизвестных до 128 неизвестных и 624 уникальных одночленов. Уже при трех раундах система не может быть решена методом линеаризации. Для увеличения числа уравнений в системе обратимся к методу расширенной линеаризации. Сначала определим значение параметра D расширенной линеаризации, предложено рассматривать подсистему каждого блока отдельно, тогда

По алгоритму метода расширенной линеаризации, следует домножать каждое уравнение системы как минимум на одночлены первой степени, т.е. (D - 2 1), следовательно, минимальное значение параметра D равно 3. Исходя алгоритма метода расширенной линеаризации, необходимо умножить все уравнения на одночлены первой степени (исходные неизвестные). Всего в подсистеме для одного блока замены используется 8 неизвестных. Получим для одного блока замены 21 + 8-21 = 189 уравнений с числом неизвестных 8 и к3 + 8 = 92 одночлена. Тогда для трех раундов система содержит v2y 3-8-189 = 4536 уравнений 192 неизвестных и 2208 одночленов. Сложность решения полученной послед расширения системы совпадает со сложность алгоритма гаусса и равна t , где t - число неизвестных в преобразованной к линейному виду системе. Тогда сложность нахождения решения системы булевых уравнений, сформированного для трех раундов шифрования составит

Выполним оценку защищенности информации, используя предложенную методику расчета вычислительной сложности нахождения решения для различного числа раундов шифрования ГОСТ, результат расчета параметров полученных систем булевых уравнений приведены в Таблице 7.

Предложенный в диссертации алгоритм представления преобразований замен позволяет сформировать систему булевых уравнений, описывающих преобразования в произвольном блоке замены. Алгебраический анализ с применением SAT-решателей можно представить алгоритмом, состоящим и из трех основных этапов: - Представление преобразования защиты информации в виде системы булевых уравнений в АНФ. - Перевод системы уравнений из АНФ в КНФ. - Поиск набор решений с помощью SAT-решателей.

После формирования системы уравнений, используя знание структуры исследуемого алгоритма защиты информации, выполняется выражение входных и выходных векторов блока замены через известные тексты. На данном этапе получена система булевых уравнений, представленная в алгебраической нормальной форме (АНФ).

Для перехода к возможности применения SAT-решателей сформированная система булевых уравнений в АНФ должна быть переведена в КНФ. Алгоритм представления уравнений в АНФ, сформированных для блочных алгоритмов, предварительно следует упростить. Воспользуемся следующим алгоритмом [61] приведения сформированной АНФ в КНФ

Разработка алгоритма алгебраического анализа четырех раундов ГОСТ с фиксированными блоками замены

Одна из сложностей алгебраического анализа алгоритма ГОСТ заключается в использовании сложения по модулю 2 раундового ключа и входного вектора раунда. Использование данной операции влечет за собой появление зависимости результата суммы от всех предыдущих битов. Для моделирования алгебраической атаки и изучения ее особенности сначала реализован алгоритм анализа упрощенного шифра ГОСТ Ф. При проектировании алгоритма алгебраического анализа вначале рассмотрим упрощенную версию шифра ГОСТ 28147-89, называемую ГОСТ, единственным отличием данной версии является использование вместо сложения по модулю 2 сложения по модулю 2. Три раунда анализируемого алгоритма шифрования ГОСТ приведены на рисунке 15.

При моделировании алгебраического анализа использовались те же фиксированные значения блоков замен (Таблица 13). Для трех раундов алгоритма ГОСТ исходная система содержит 504 уравнения, 192 неизвестных и 672 произведений неизвестных.

Выполним выражение взаимосвязи входных и выходных битов блоков замены через открытые тексты, шифртексты и раундовые ключи. Для первого раунда входной и выходной векторы блока замены можно выразить следующим образом: XI = PR K\,

Используя приведенные выше равенства можно сократить число неизвестных (71 можно выразить через 73; 72 - известно). Таким образом, неизвестными остаются три раундовых ключа (96 бит) и выходное значение блоков замены в третьем раунде (32 бита). Итоговая система содержит 504 уравнения, 128 неизвестных и 624 уникальных одночленов. Количество одночленов превышает количеств линейно независимых уравнений. Рассмотрим решение данной системы с применением SAT-решателя.

Проведем алгебраический анализ при известных открытом тексте P1=58B7E5E8A13Ah и шифртексте C1=19A445B63BA49DDCh. В первую очередь следует вычислить значение Y2: Y2 = (PR CR) » 11= 9CDBC987h. Подставив вычисленное значение Y2 и выполнив выражение входов выходов блока замены через раундовые ключи, получили систему, приведенную в Приложении 7. Выполнение SAT алгоритма поиска решения не позволило за реальное время найти все возможные наборы решений (не хватило памяти для сохранения обхода дерева поиска). Для сокращения числа возможных раундовых ключей использована еще одна пара открытый текст/шифртекст, зашифрованная на тех же ключах: P2=67BDF1ACFFB83AA7h, C2= 2CB7CAE2CCA24445h. Аналогично в исходной системе для трех раундов выполнена замена известного Y2 и выражена связь векторов S-блока с раундовыми ключами. Получены дополнительные 504 уравнения. При этом число неизвестных в объединенной системе увеличилось на 32 бита - размер выходного вектора блоков замены третьего раунда. Таким образом, получена система из 1008 уравнений с 160 неизвестными (Приложение 8). Применение SAT-решения к данной системе позволило сократить число возможных раундовых ключей до 32 (Приложение 9). В ходе проверки найденных 32 возможных ключей был определен верный ключ K=( C23E5FA0h, 6A4158B2h, CCD6AC3Fh).

Время выполнения анализа (поиска раундовых ключей) трех раундов шифра ГОСТ при двух парах текстов составило 20 сек. при выполнении алгоритма в среде SageMath Cloud. Решение системы заняло 0,26 секунды при двух текстах.

При использовании формирования уравнений для третьей пары открытый текст/шифртекст (P3=359FFACBDABF8846h, C3=D1E00D1623D54938h) было найдено два набора возможных раундовых ключей (Приложение 10): 1) C23E5FA0h, 6A4158B2h, CCD6EC3Fh, 2) C25E5FA0h, A4158B7h, CC46EC3Fh. Система содержит 1512 уравнений и 192 неизвестных. Формирование и решение системы заняло 32,7 секунд при трех используемых парах известных текстов. Непосредственно решение системы с использованием потребовало 0,52 сек.

Проведем анализ шифра при 4 известных парах текстов P4=49FAA533FF691CADh, C4=370ACCF86CD2D333h. Система содержит 2016 уравнений и 224 неизвестных.

При анализе трех раундов с помощью метода SAT-решателя получены следующие результаты моделирования (Таблица 14) Особенностью найденных возможных наборов ключей является то, что они для проверяемых открытых текстов дают разницу в одном бите шифртекстов. Для трех раундов ГОСТ на трех текстах получила два набора решений: K=(C23E5FA0h, 6A4158B2h, CCD6EC3Fh) и K =(C25E5FA0h, 7?A4158B7h, CC46EC3Fh).

Проведем шифрование на ключах K и K для открытых текстов, на которых формировали систему уравнений. При открытом тексте P1=58B7E5E8A13Ah, получены шифртексты ЕК(Р1)= 19A445B63BA49DDCh и EK,(Pl)=lD2445B63BA49DDCh. При P2=67BDFlACFFB83AA7h получены шифртексты EK (P2) =2CB7CAE2CCA24445h и EK,(P2)=2DB7CAE2CCA24445h. При открытом тексте P3=359FFACBDABF8846h получены шифртексты EK(P3)=DlE00D1623D54938h и EK,(PЗ) = D0E00D1623D54938h.

Найденный второй вероятный ключ дает разницу в фиксированной позиции в один бит. Из трех проверяемых открытых текстов, разница в один бит была найдена для двух текстов. Таким образом, решение системы булевых уравнений для трех раундов шифрования ГОСТ позволяет не только найти верный ключ шифрования, но и вычислить ключ, дающий максимально близкий шифртекст.

Используя сформированные ранее линейно независимые булевы алгебраические уравнения, рассмотрим вычисления раундовых ключей шифрования для трех раундов алгоритма ГОСТ 28147-89 (рисунок 16).

Аналогично рассмотренному анализу трех раундов ГОСТ сформируем результирующую систему для нахождения раундовых ключей. Для шифра ГОСТ 28147-89 в системе булевых уравнений оставляем входные и выходные векторы блоков замены, как неизвестные.