1 Криптоанализ блочных шифров Дмитрий Ширяев СПбГУ, 2005 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25 Источники дополнительных сведений Что и где почитать: Bruce Schneier Self-Study Course in Block Cipher Cryptanalysis, курс молодого бойца, т.е. для тех, кто хочет реально заняться криптоанализом знаменитые взломщики RC5 – просто посмотреть и насладиться =) Francois-Xavier Standaert & others Cryptanalysis of Block Ciphers: the Survey, самый полный обзор методов криптоанализа, однако много опечаток и непонятных мест Dave Rudolf Development and Analysis of Block Ciphers and the DES System, очень понятное введение в основы блочных шифров, внятно описан DEShttp:// М. Анохин, «Блочные криптографические алгоритмы» - отличный краткий обзор истории и современного состояния криптоанализа, ко всему прочему (УРА!) на русском языке