Слайд 2План доклада
Что это такое
Зачем оно надо
Примеры
![План доклада Что это такое Зачем оно надо Примеры](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-1.jpg)
Слайд 3Hash-функция
Пример не из криптографии – Хранение словаря
Слово
0 12080 20000
hash
12080
Word
![Hash-функция Пример не из криптографии – Хранение словаря Слово 0 12080 20000 hash 12080 Word](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-2.jpg)
Слайд 4Коллизии
Пример не из криптографии – Хранение словаря
Слово
0 12080 20000
hash
12080
Word
Зебра
hash
![Коллизии Пример не из криптографии – Хранение словаря Слово 0 12080 20000](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-3.jpg)
Слайд 5Практическое использование
Банкомат
Цифровая подпись
Быстро вычислимые
Не обратимые
Зная M сложно вычислить N такое, что
![Практическое использование Банкомат Цифровая подпись Быстро вычислимые Не обратимые Зная M сложно](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-4.jpg)
H(M)=H(N)
Кроме того, сложно найти такие P и Q, что H(P)=H(Q)
Авторизация клиент-сервер
Слайд 6Пример взлома
Контракт 1
Контракт 2
232
232
![Пример взлома Контракт 1 Контракт 2 232 232](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-5.jpg)
Слайд 7Нахождение коллизий
Метод дней рождений
Сколько человек должно быть в комнате, чтобы вероятность того,
![Нахождение коллизий Метод дней рождений Сколько человек должно быть в комнате, чтобы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-6.jpg)
что найдется человек родившийса с вами в один день была равна 0.5 ???
Сколько человек должно быть в комнате, чтобы вероятность того, чтобы нашлась пара людей, родившихся в один день была 0.5 ???
Слайд 8Требования к функции
Актуальный размер кэша
Для 16 байтогого кэша (128 бит) 264 различных
![Требования к функции Актуальный размер кэша Для 16 байтогого кэша (128 бит)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-7.jpg)
документов
Secure Hash Standard 160 бит 264
Специальный метод для удлиннения хэш-значений
Прибавить хэш значение к исходному сообщению, а затем повторить все заново
Отсутствие коллизий осмысленных строк
Слайд 9Немного примеров из истории
Snefru Ральф Меркл
N-hash 1990
MD4, MD5 Рон Ривест
SHA
RIPE-MD
HAVAL
ГОСТ Р 34.11.94
Использование
![Немного примеров из истории Snefru Ральф Меркл N-hash 1990 MD4, MD5 Рон](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-8.jpg)
блочных шифров
Слайд 11Взломы и попытки взломов
Некоторые алгоритмы были вломаны
Найдены алгоритмы нахождения коллизий
Некоторые почти взломаны
Найдены
![Взломы и попытки взломов Некоторые алгоритмы были вломаны Найдены алгоритмы нахождения коллизий](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-10.jpg)
алгоритмы нахождения
предколлизий
коллизий за меньшее время
коллизий в укороченных версиях
Атака на 7 из 10 уровней AES
Антуан Жу – работа о мульти хэш-функциях
Слайд 12MAC
Message authentication code
Хэш функция зависит от ключа
Можно менять ключ для дополнительной проверки
В
![MAC Message authentication code Хэш функция зависит от ключа Можно менять ключ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-11.jpg)
качестве МАС можно использовать обычный хэш
H(K,H(K,M))
H(K,p,H,M)
Сложно подобрать ключ
Вычислить значение хэша для другого ключа
Слайд 13Определения
Определение hash-функции
Функция H
Или семейство
Пользуясь предыдущим примером:
D строчки русских букв
R число от 0
![Определения Определение hash-функции Функция H Или семейство Пользуясь предыдущим примером: D строчки](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-12.jpg)
до 20000
H: K ×D → R.
HK: D → R
Слайд 14Определения
Обратная функция
Коллизия
HK−1 (y) = { x ∈ D : HK(x) = y
![Определения Обратная функция Коллизия HK−1 (y) = { x ∈ D :](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-13.jpg)
Слайд 15Нахождение коллизий
Три типа устойчивости
CR2-KK
Collision free, collision resistant
CR1-KK
Universal one-way
CR0
Universal
![Нахождение коллизий Три типа устойчивости CR2-KK Collision free, collision resistant CR1-KK Universal one-way CR0 Universal](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-14.jpg)
Слайд 16Три вида атак на нахождение коллизий
CR2-KK
Найти коллизии для конкретной функции
CR1-KK
Подобрать пару к
![Три вида атак на нахождение коллизий CR2-KK Найти коллизии для конкретной функции](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/444450/slide-15.jpg)
заданному значению, образующую коллизию для конкретгой функции.
СК0
Найти коллизию для семейства функций