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

Ширяев

СПбГУ, 2005

г.

хорошим криптоаналитиком и взламывать алгоритмы. Множество. Снова и снова. Только

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

атаки
Выводы
Источники дополнительных сведений

отдельные блоки и затем осуществляют преобразование этих блоков с использованием

ключа.
Преобразование должно использовать следующие принципы:

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

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

для выработки шаговых ключей
Фиксированные перестановки

Американский

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

Сеть Файстеля

текстом и шифротекстом
В DES S-boxes c помощью фиксированных таблиц преобразуют

6-битовый вход в 4-битовый выход, соответственно 48 бит преобразуются в 32
В ГОСТ используются переменные S-boxes

DES S-boxes

исследование методов взлома криптографических алгоритмов, а также сама процедура взлома.
Вопрос:

Что же такое криптоанализ?

Часть 2: Криптоанализ

шифротекста
Known Plaintext – анализ на основе невыбранного открытого текста
Chosen

Plaintext – анализ на основе выбранного открытого текста
Chosen Ciphertext – анализ на основе выбранного шифротекста

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

системы

ключа
Например, в DES:
Если

то

т.е. полным перебором ключей
Основная цель любого метода криптоанализа – улучшить

время Brutal-Force Attack, или улучшить имеющееся соотношение время/память
Key-recovery – метод нахождения наиболее вероятного раундового ключа, с помощью перебора различных исходных текстов. Используется в большинстве методов криптоанализа

криптоанализ
Методы, основанные на слабости ключевых разверток

(Eli Biham) и Али Шамиром (Ali Shamir)
Эли Бихам
Али Шамир

разностью, смотрим, как отличаются шифры от них ΔX = X1⊕X2

ΔY = Y1⊕Y2
Анализируя много таких пар, находим наиболее вероятный ключ

входом и m-битовым выходом
Дифференциал – это пара: разность входных данных

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

Для взлома DES необходимо 247 выбираемых нами входных текстов
Защита – минимизировать максимальные вероятности p, максимизировать количество S-boxes в каждой дифференциальной характеристике

шифротекстом и ключом
Затем проделываем key-recovery

входными и выходными битами
Комбинируем полученные зависимости так, чтобы остались только биты

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

результаты линейного анализа для нахождения дифференциальной характеристики - 10 бит ключа

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

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

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

используемые на 1м и последнем раундах не пересекаются)
Слабые (weak) и

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

защищен от всех представленных выше атак
Однако, и на него уже

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

Vincent Rijmen

J. Daemen

Block Cipher Cryptanalysis”, 2000 http://www.counterpane.com/self-study.html - курс молодого бойца, т.е. для

тех, кто хочет реально заняться криптоанализом
http://www.distributed.net - знаменитые взломщики RC5 – просто посмотреть и насладиться =)
Francois-Xavier Standaert & others “Cryptanalysis of Block Ciphers: the Survey”, 2001 http://logic.pdmi.ras.ru/~yura/crypto/01crypto.pdf - самый полный обзор методов криптоанализа, однако много опечаток и непонятных мест
Dave Rudolf “Development and Analysis of Block Ciphers and the DES System”, 2002 http://www.cs.usask.ca/grads/dtr467/400 - очень понятное введение в основы блочных шифров, внятно описан DES
М. Анохин, «Блочные криптографические алгоритмы» http://www.cryptography.ru/db/msg.html?mid=1162999&uri=node4.html - отличный краткий обзор истории и современного состояния криптоанализа, ко всему прочему (УРА!) на русском языке