'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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)


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

25 Источники дополнительных сведений Что и где почитать: Bruce Schneier “Self-Study Course in 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 - отличный краткий обзор истории и современного состояния криптоанализа, ко всему прочему (УРА!) на русском языке


×

HTML:





Ссылка: