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

В данной статье представлен метод невозможных дифференциалов и атака на пятираундовый S-AESс помочью этого метода.

Ключевые слова: криптоанализ, криптография, невозможные дифференциалы, шифрование.

Метод невозможных дифференциалов – это новый способ атак на симметричные блочные шифры, основанный на построении невозможного события, то есть такого события, вероятность которого равна нулю [1, 2]. Тогда мы можем отбрасывать все ключи, которые приводят к невозможным событиям. Для нахождения таких событий можно использовать технику «встреча посередине» [3] (miss-in-the-middletechnique), суть которой заключается в том, чтобы найти два события вероятность которых равна 1 и, совместив их, получить невозможное событие.

S-AES– симметричный блочный шифр, обладающий свойствами обычного AES. Он имеет четыре трансформации: сложение с раундовым ключом AddRoundKey, замена по таблице Sub-HalfBytes,сдвиг строки ShiftRows и перемешивание столбцов MixColumns. Алгоритм состоит из двух раундов, но во втором нет преобразования MixColumns. Подробное описание алгоритма можно найти в работе [4]. Для применения метода невозможных дифференциалов мы расширим количество раундов до пяти.

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

Рис.1 – Четырехраундовый невозможный дифференциал для алгоритма S-AES

После чего мы можем добавить ещё один раунд в начале и получить возможность атаки на пятираундовый S-AES, что показано на рис. 2.

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

Рис.2 – Пятираундовый невозможный дифференциал для алгоритма S-AES

Так же мы можем отбрасывать ключи, которые после первого раунда приводят к ненулевой разности во втором полубайте, построив немного другой невозможный дифференциал, изображенный на рис. 3.

Опишем подробно процесс нахождения первого и четвертого бита ключа для пятираундовогоS-AES.

1. Возьмем пар текстов, которые имеют различие в первом и четвертом полубайте.

2. Зашифруем эти тексты, и оставим только те из них, которые на выходе давали разность в первом и четвертом полубайтахили во втором и третьем полубайтах. У нас останется таких текстов.

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

Рис.3 – Второй вариант построения невозможных дифференциалов для 4 раундов S-AES

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

Рис. 4 – Второй вариант построения невозможных дифференциалов для 5 раундов S-AES

Таким образом, мы нашли первый ключ для пятираундовогоS-AES, используя метод невозможных дифференциалов.

Работа выполнена при поддержке гранта РФФИ № 15-37-20007-мол-а-вед.

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

1. Phan, R. C.-W. 2002. Mini Advanced Encryption Standard (Mini-AES): A Testbed for Cryptanalysis Students. Cryptologia. 26(4).

2. Biham, E., Biryukov, A. and Shamir, A. 2001. Miss in the Middle Attacks on IDEA and Khufu. In Advances of Cryptology – FSE ’99 (Lecture Notes in Computer Science No.1636). 124-138.

3. Phan, R. C. W. 2002. Classes of Impossible Differentials of Advanced Encryption Standard. IEE ElectronicsLetters. 38(11): 508-510.

4. Бабенко Л.К. Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа // Москва, «Гелиос АРВ», 2006. – 376 с.

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