- •Карондеев а.М. Козлов а.А. Силков а.А. Сложение по модулю в блочном шифровании
- •Введение
- •Линейные статистические аналоги сложения по модулю
- •Особенности использования линейных статистических аналогов при анализе блочных шифров
- •Нелинейные статистические аналоги сложения по модулю
- •Криптоанализ на основе нелинейных статистических аналогов
- •Описание метода криптоанализа
- •Оценка сложности
- •Использованная литература
-
Криптоанализ на основе нелинейных статистических аналогов
-
Описание метода криптоанализа
Общая идея – получить соотношение связывающие некоторые биты открытого текста, шифртекста и ключа, которое выполняется с преобладанием существенно больше нуля. Соотношения (7) и (8) не являются линейными, поэтому и итоговое соотношение будет нелинейным. Покажем, что это не мешает использовать лемму о накапливании. Действительно как было показано в леммах 1, 2 для фиксированного ключа, наибольшее преобладание достигается при фиксированном , при проведении анализа будем перебирать всевозможные и на одном из них итоговое соотношение будет выполнятся с наибольшим преобладанием. При подстановке этого , итоговое соотношение сведется к линейному для которого применима лемма о накапливании. По сути, перебирая всевозможные , мы выбираем из нескольких линейных соотношений то, которое выполняется с наибольшим преобладанием. С учетом вышесказанного произведем криптоанализ блочного шифра описанного в 3 части, более детальная схема которого изображена на рисунке 9.
На рисунке 9 приведен путь используемой аппроксимации:
Рисунок 9. Схема нелинейной аппроксимации
Согласно приведенной схеме активными S-блоками являются:
, , , ,
Итоговое соотношение имеет вид:
(9)
где Vij – j-й выход i-го слоя S-блоков.
Согласно лемме о накапливании, соотношение (9) на истинном ключе выполняется с преобладанием больше чем соответственно для проведения криптоанализа будет достаточно иметь порядка 16 тысяч пар открытый текст – шифртекст. Для проведения анализа необходимо перебрать 16 бит первого раундового ключа, 5 бит четвертого, 8 бит пятого, а также значения ().
Ход криптоаналиаза:
-
Для восстанавливаемого ключа сгенерировать 16000 случайных пар открытый текст – шифртекст
-
Для сгенерированных пар и всевозможных значений части ключа и параметров вычислить преобладание, с которым выполняется соотношение 9
-
Значения части ключа, на котором соотношение 9 выполняется с наибольшим преобладанием, с высокой долей вероятности совпадает с соответствующими битами искомого ключа
-
Оставшиеся биты находим тотальным опробованием
-
Оценка сложности
Результатом криптоанализа будет нахождение 29 бит истинного ключа, соответственно оставшиеся биты находятся перебором.
Сложность по времени:
Сложность по памяти:
-
Выводы
Проведенный выше анализ использования сложения по модулю 2n в блочном шифровании показывает:
-
Замена блока смешения с ключом со сложения по модулю 2 на сложение по модулю 2n существенно осложняет линейный криптоанализ.
-
Cуществуют алгоритмы взлома такого шифра быстрее полного перебора при этом наилучшие результаты дает использование нелинейных аппроксимаций.
-
При проведении криптоанализа возможно комбинирование описанных методов. Сначала воспользоваться методом линейных аппроксимаций, а при неудачном исходе использовать нелинейные.