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

Сентябрь 2, 2022

Главная
Алгебра
Криптоанализ блочных шифров

Содержание

2. Эпиграф Существует только один путь стать хорошим разработчиком криптографических алгоритмов --- быть хорошим криптоаналитиком и взламывать
3. План Часть 1: Блочные шифры Часть 2: Криптоанализ Часть 3: Различные атаки Выводы Источники дополнительных сведений
4. Часть 1: Блочные шифры Симметричная криптосистема Блочные криптосистемы разбивают текст сообщения на отдельные блоки и затем
5. Параметры блочного шифра Числовые параметры алгоритма: - размер шифруемого блока данных - размер ключа - размер
6. Алгоритм DES Data Encryption Standard Американский стандарт шифрования на протяжении 1974-2000 г.г. Длина блока 64 бит
7. Алгоритм DES: более подробно
8. Блоки подстановки (S-boxes) S-boxes созданы для того, чтобы запутать зависимость между текстом и шифротекстом В DES
9. Криптоанализ – это отрасль знаний, целью которой является поиск и исследование методов взлома криптографических алгоритмов, а
10. Часть 2: Криптоанализ Различные типы Ciphertext Only – анализ на основе только шифротекста Known Plaintext –
11. Часть 2: Криптоанализ На практике Реальный криптоанализ основан на трех вещах: Изучение системы шифрования в целом
12. Свойство дополнительности (Complementation property) Взаимосвязь между парами текст-шифротекст при обращении текста и ключа Например, в DES:
13. Часть 2: Криптоанализ Восстановление ключа Brutal-Force Attack – атака методом “грубой силы”, т.е. полным перебором ключей
14. Часть 3: Различные атаки Дифференциальный криптоанализ Линейный криптоанализ Модификации дифференциального и линейного анализов Интерполяционный криптоанализ Методы,
15. Дифференциальный анализ: История Разработан в 1990 году израильскими криптографами Эли Бихамом (Eli Biham) и Али Шамиром
16. Дифференциальный анализ: Основные идеи Chosen-plaintext метод Выбираем пары входных текстов с фиксированной разностью, смотрим, как отличаются
17. Дифференциальный анализ: Более подробно Пусть в алгоритме есть S-box c n-битовым входом и m-битовым выходом Дифференциал
18. Линейный анализ: История Разработан Митцуру Матцуи (Mitsuru Matsui) в 1992 г. Митцуру Матцуи
19. Линейный анализ: Основные идеи Known plaintext attack Ищем линейную зависимость между исходным текстом, шифротекстом и ключом
20. Линейный анализ: Более подробно Анализируем нелинейные компоненты шифра, находим вероятности линейных зависимостей между входными и выходными
21. Развитие методов дифференциального и линейного анализа Дифференциально-линейный криптоанализ - chosen plaintext - использует результаты линейного анализа
22. Интерполяционная атака Авторы – Т.Джекобсен и Л.Кнудсен, 1997 год Known-text attack Предполагаем, что раундовая функция –
23. Методы, основанные на слабости ключевых разверток Метод согласования (Meet-in-the-middle) - биты ключа, используемые на 1м и
24. Будущее криптоанализа Алгоритм AES (Rijndael) – современный американский стандарт шифрования Он фактически защищен от всех представленных
26. Скачать презентацию

Слайд 2

Эпиграф
Существует только один путь стать хорошим разработчиком криптографических алгоритмов --- быть хорошим

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

Слайд 3

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

дополнительных сведений

Слайд 4

Часть 1: Блочные шифры
Симметричная криптосистема
Блочные криптосистемы разбивают текст сообщения на отдельные

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

Слайд 5

Параметры блочного шифра
Числовые параметры алгоритма: - размер шифруемого блока данных - размер

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

Слайд 6

Алгоритм DES Data Encryption Standard
Американский
стандарт шифрования
на

протяжении 1974-2000 г.г.
Длина блока 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 = X1⊕X2 ΔY = Y1⊕Y2
Анализируя много таких пар, находим наиболее вероятный ключ

Слайд 17

Дифференциальный анализ: Более подробно
Пусть в алгоритме есть S-box c n-битовым входом

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

Слайд 18

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

Слайд 19

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

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

Слайд 20

Линейный анализ: Более подробно
Анализируем нелинейные компоненты шифра, находим вероятности линейных зависимостей между входными

и выходными битами
Комбинируем полученные зависимости так, чтобы остались только биты исходного текста, шифротекста и ключа
Вероятность нахождения такой комбинации = (Piling-Up Lemma)
Key-recovery на DES проходит при использовании 243 известных исходных текстов
Защита – минимизировать вероятностные смещения (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

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

Содержание

ЭпиграфСуществует только один путь стать хорошим разработчиком криптографических алгоритмов --- быть хорошим

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

Часть 1: Блочные шифрыСимметричная криптосистемаБлочные криптосистемы разбивают текст сообщения на отдельные

Параметры блочного шифраЧисловые параметры алгоритма: - размер шифруемого блока данных - размер

Алгоритм DES Data Encryption Standard Американский стандарт шифрования на

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

Блоки подстановки (S-boxes)S-boxes созданы для того, чтобы запутать зависимость между текстом

Криптоанализ – это отрасль знаний, целью которой является поиск и исследование

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

Часть 2: Криптоанализ На практике Реальный криптоанализ основан на трех вещах:Изучение системы

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

Часть 2: Криптоанализ Восстановление ключаBrutal-Force Attack – атака методом “грубой силы”, т.е.

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

Дифференциальный анализ: Основные идеиChosen-plaintext методВыбираем пары входных текстов с фиксированной разностью,

Дифференциальный анализ: Более подробноПусть в алгоритме есть S-box c n-битовым входом

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

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

Линейный анализ: Более подробноАнализируем нелинейные компоненты шифра, находим вероятности линейных зависимостей между входными

Развитие методов дифференциального и линейного анализаДифференциально-линейный криптоанализ - chosen plaintext - использует результаты

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

Методы, основанные на слабости ключевых развертокМетод согласования (Meet-in-the-middle) - биты ключа, используемые

Будущее криптоанализаАлгоритм AES (Rijndael) – современный американский стандарт шифрованияОн фактически защищен

Похожие презентации