IX Международная студенческая научная конференция Студенческий научный форум - 2017

Совсем недавно вступил в силу ГОСТ Р 34.12 2015 в нем описаны два алгоритма шифрования, Кузнечик с длиной текста n=128 и Магма с длиной текста равной n=64. Магма является изменённой версией ГОСТ 28147-89 с фиксированными блоками замены и нуждается во всестороннем анализе.

Метод невозможных дифференциалов – метод криптоанализа блочных шифров разработанный в 1998 году Эли Бихамом, Эди Шамиров и Алексом Бирюковым. Метод применялся к таким шифрам как IDEA, AES, Khufu и Khafre, Skipjack, MISTY и KASUMI, S-AES [1 – 5].

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

Симметричный блочный шифр Магма описан в новом российском стандарте шифрования ГОСТ Р 34.12 2015. Шифр построен на основе сети Фейстеля и имеет 32 раунда и раундовую функцию состоящую из трех преобразований: побитовый сдвиг на 11 позиций влево, замена при помощи S-блоков, и сложение по модулю . Но анализ будет проводится над измененным алгоритмом Магма, в котором операция сложения по модулю заменена на побитовое сложение по модулю 2.

Для анализа необходимо посмотреть, как меняется разность двух текстов после прохождения F-блока. Будем рассматривать разности в полубайтах, а не в отдельных битах. В общем случае можно сказать, что разность в полубайте N после прохождения F-блока может дать разность в N+2 и N+3. Но для анализа будем использовать особенность, найденную Ищуковой Е.А и Калмыковым И.А в [7], в шестом S-блоке, суть которой заключается в том, что при разности ΔА=9, после прохождения S-блока у разности ΔС младший бит всегда будет равен 0. Это значит, что после прохождения F-блока, разность затронет 1 полубайт. Зная эти особенности можно построить дифференциальную схему для восьми раундов представленную на рисунке 1. На схема синий цвет – разность между текстами равна 9, красный цвет – неизвестно есть ли разность, черный цвет – разность есть, белый цвет – разности нет.

Рисунок 1. Схема для 8 раундов

Анализ будет проводится на алгоритме шифрования Магма, в котором операция сложения с подключом осуществляется по модулю 2 и усеченного до восьми раундов. Процесс отбрасывания неправильных ключей происходит следующим образом: тесты с разностями в первом полубайте левой половины и с разностью равной 9 в шестом полубайте правой половины шифруется, из них оставляются только те, которые после 8 раундов не имеют разности в шестом полубайте левой половины и третьем и четвёртом полубайте правой половины. Затем, начинается перебор ключей, перебирается только шестой полубайт ключа, остальной ключ можно зафиксировать. Мы заново шифруем оставшиеся тексты одним раундом, но те ключи, которые после этого раунда приводят к разности текстов только в шестом полубайте правой половины равную девяти являются неверными и отбрасываются.

Некоторые результаты эксперимента представлены в таблице 1.

Таблица 1 – Результаты экспериментов

Ключ	Всего текстов	Количество подходящих тестов	Количество неправильных ключей	Время, секунды
9152111	5114984	1000	6	5.22
3128457	3856569	1000	8	4.35
16681	3636971	1000	8	3.65
52678425	3112081	1000	2	4.13
52644712	4363655	1000	10	4.12
101177462	2442746	1000	8	2.98

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

Список литературы

1. E. Biham, A. Biryukov, A. Shamir, Miss in the Middle Attacks on IDEA, Khufu, and Khafre // 6th International Workshop on Fast Software Encryption (FSE 1999). Rome: Springer-Verlag. pp. 124–138.

2. E. Biham, A. Biryukov, A. Shamir, Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials // Advances in Cryptology - EUROCRYPT '99. Prague: Springer-Verlag. pp. 12–23.

3. J. Lu, O. Dunkelman, N. Keller, J. Kim, New impossible differential attacks on AES

4. J. Cheon, M. Kim, K. Kim, and J. Lee, Improved Impossible Differential Cryptanalysis of Rijndael and Crypton // 4th International Conference on Information Security and Cryptology (ICISC 2001).Seoul: Springer-Verlag. pp. 39–49.

5. Raphael C.-W. Phan (October 2003). "Impossible Differential Cryptanalysis of Mini-AES"/ Cryptologia. XXVII (4): pp. 283–292

6. М.В Письменский, Е.А Ищукова, Криптоанализ S-AES с помощью метода невозможных дифференциалов // VIII Международная студенческая электронная научная конференция «Студенческий научный форум» - 2016. // Актуальные проблемы информационной безопасности. – http://www.scienceforum.ru/2016/pdf/24173.pdf

7. Е.А. Ищукова, И.А. Калмыков Дифференциальные свойства S-блоков замены для алгоритма ГОСТ 28147-89 // Инженерный вестник Дона, №4 (2015) ivdon.ru/ru/magazine/archive/n4y2015/3284

Код для цитирования: Скопировать