Криптоанализ блочных шифров

Эпиграф
Существует только один путь стать хорошим разработчиком криптографических алгоритмов --- быть хорошим криптоаналитиком и взламывать алгоритмы. Множество. Снова и снова. Только после того, как обучающийся продемонстрирует способности к криптоанализу чужих алгоритмов, он сможет серьезно браться за разработку собственных алгоритмов. Брюс Шнайер (Bruce Schneier)

План
Часть 1: Блочные шифры
Часть 2: Криптоанализ
Часть 3: Различные атаки
Выводы
Источники дополнительных сведений

Часть 1: Блочные шифры
Симметричная криптосистема
Блочные криптосистемы разбивают текст сообщения на отдельные блоки и затем осуществляют преобразование этих блоков с использованием ключа.
Преобразование должно использовать следующие принципы:
Рассеивание (diffusion) - т.е изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;
Перемешивание (confusion) - использование преобразований, затрудняющих получение статистических зависимостей между шифротектстом и открытым текстом.

Параметры блочного шифра
Числовые параметры алгоритма:
- размер шифруемого блока данных
- размер ключа
- размер “шагового” ключа
- число раундов шифрования
Функция шифрования
Набор функций для выработки шаговых ключей
Фиксированные перестановки

Алгоритм DES
Data
Encryption
Standard
Американский
стандарт шифрования
на протяжении 1974-2000 г.г.
Длина блока 64 бит
Длина ключа 56 бит
Размер ключегого элемента 48 бит
Число раундов 16
Сеть Файстеля

Алгоритм DES: более подробно

Блоки подстановки (S-boxes)
S-boxes созданы для того, чтобы запутать зависимость между текстом и шифротекстом
В DES S-boxes c помощью фиксированных таблиц преобразуют 6-битовый вход в 4-битовый выход, соответственно 48 бит преобразуются в 32
В ГОСТ используются переменные S-boxes
DES S-boxes

Криптоанализ – это отрасль знаний, целью которой является поиск и исследование методов взлома криптографических алгоритмов, а также сама процедура взлома.
Вопрос: Что же такое криптоанализ?
Часть 2: Криптоанализ

Часть 2: Криптоанализ
Различные типы
Ciphertext Only – анализ на основе только шифротекста
Known Plaintext – анализ на основе невыбранного открытого текста
Chosen Plaintext – анализ на основе выбранного открытого текста
Chosen Ciphertext – анализ на основе выбранного шифротекста

Часть 2: Криптоанализ
На практике
Реальный криптоанализ основан на трех вещах:
Изучение системы шифрования в целом
Изучение особенностей исходного текста
Изучение особенностей ключевой системы

Свойство дополнительности
(Complementation property)
Взаимосвязь между парами текст-шифротекст при обращении текста и ключа
Например, в DES:
Если то

Часть 2: Криптоанализ
Восстановление ключа
Brutal-Force Attack – атака методом “грубой силы”, т.е. полным перебором ключей
Основная цель любого метода криптоанализа – улучшить время Brutal-Force Attack, или улучшить имеющееся соотношение время/память
Key-recovery – метод нахождения наиболее вероятного раундового ключа,
с помощью перебора различных исходных текстов. Используется в большинстве методов криптоанализа

Часть 3: Различные атаки
Дифференциальный криптоанализ
Линейный криптоанализ
Модификации дифференциального и линейного анализов
Интерполяционный криптоанализ
Методы, основанные на слабости ключевых разверток

Дифференциальный анализ:
История
Разработан в 1990 году израильскими криптографами Эли Бихамом (Eli Biham) и Али Шамиром (Ali Shamir)
Эли Бихам
Али Шамир

Дифференциальный анализ:
Основные идеи
Chosen-plaintext метод
Выбираем пары входных текстов с фиксированной разностью, смотрим, как отличаются шифры от них
ΔX = X1⊕X2 ΔY = Y1⊕Y2
Анализируя много таких пар, находим наиболее вероятный ключ

Дифференциальный анализ: Более подробно
Пусть в алгоритме есть S-box c n-битовым входом и m-битовым выходом
Дифференциал – это пара: разность входных данных и разность выходных данных нашего преобразования
Если Q - это количество различных пар входов, дающих этот дифференциал, то p=Q/2n – вероятность этого дифференциала
Дифференциальная характеристика – это последовательность разностей после каждого раунда
Построив дифференциальную характеристику на раундах с 1го по предпоследний, проводим Key-recovery атаку на последнем раунде.
Для взлома DES необходимо 247 выбираемых нами входных текстов
Защита – минимизировать максимальные вероятности p, максимизировать количество S-boxes в каждой дифференциальной характеристике

Линейный анализ:
История
Разработан Митцуру Матцуи
(Mitsuru Matsui) в 1992 г.
Митцуру Матцуи

Линейный анализ:
Основные идеи
Known plaintext attack
Ищем линейную зависимость между исходным текстом, шифротекстом и ключом
Затем проделываем key-recovery

Линейный анализ:
Более подробно
Анализируем нелинейные
компоненты шифра, находим
вероятности линейных зависимостей между входными и выходными битами
Комбинируем полученные зависимости так, чтобы
остались только биты исходного текста, шифротекста и ключа
Вероятность нахождения такой комбинации =
(Piling-Up Lemma)
Key-recovery на DES проходит при использовании 243 известных исходных текстов
Защита – минимизировать вероятностные смещения (bias), максимизировать число S-boxes, или иных нелинейных элементов

Развитие методов дифференциального и линейного анализа
Дифференциально-линейный криптоанализ
- chosen plaintext
- использует результаты линейного анализа для нахождения дифференциальной характеристики
- 10 бит ключа 8-раундового DES вскрываются с помощью всего 512 входных текстов
- защита – быстрое перемешивание (на первых 2-3 раундах)
Усеченные (truncated) дифференциалы
- следим лишь за частью битов
Дифференциалы высших порядков
- обобщение понятия дифференциальной характеристики
- например, против f(x)=(x+k)^2 mod p
- защита – много раундов, функции более высоких порядков
Невозможные дифф-лы (Miss-in-the-middle attack)
- ищем дифференциалы, которые заведомо не встретятся, получаем целые классы неподходящих ключей
Метод бумеранга
- ищем 2 дифф.характеристики с хорошими вероятностями, покрывающие весь шифр (необходима атака типа chosen-ciphertext)

Интерполяционная атака
Авторы – Т.Джекобсен и Л.Кнудсен,
1997 год
Known-text attack
Предполагаем, что раундовая функция – многочлен. Тогда весь шифр может быть записан как многочлен, коэфф-ты зависят от ключа.
Интерполируем этот многочлен по достаточно большому количеству исходных текстов

Методы, основанные на слабости ключевых разверток
Метод согласования (Meet-in-the-middle)
- биты ключа, используемые на 1м и последнем раундах не пересекаются)
Слабые (weak) и полу-слабые (semi-weak) ключи
- ключи, для которых результат шифрования сообщения совпадает с результатом расшифрования
- таких ключей немного, их просто нужно избегать
Метод связанных ключей
- Chosen-plaintext attack
- у нас есть возможность шифровать несколькими ключами, связанными между собой

Будущее криптоанализа
Алгоритм AES (Rijndael) – современный американский стандарт шифрования
Он фактически защищен от всех представленных выше атак
Однако, и на него уже делаются попытки атак, использующие сложные алгебраические теории: Square-saturation-integral-multiset attacks
Например Square attack, созданный против алгоритма Square – атакует . Chosen plaintext attack, основанный на хорошем выборе множества исходных текстов
- основной используемый объект - мультимножество
- особенность: информация получается лишь при рассмотрении всего множества исходных текстов
Vincent Rijmen
J. Daemen