'

Коллизии хеш-функций

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





Слайд 0

Коллизии хеш-функций MD5, SHA-0, SHA-1 Московский физико-технический институт (ГУ МФТИ) Факультет Радиотехники и Кибернетики


Слайд 1

Функция хеширования X h(x) H данные хеши


Слайд 2

Функция хеширования Свойства: Необратимость Стойкость к коллизиям Слабая Сильная Применение в криптографии ЭЦП, пароли и т.д.


Слайд 3

Алгоритм Меркла-Дамгарда 1 2 . . . N pad IV h h . . . h h hash Выравнивание сообщения определённым образом – существенный аспект безопасности


Слайд 4

Коллизии хеш-функций Практически любая хеш-функция имеет коллизии В хороших х.ф. коллизии крайне редки «Идеальная х.ф.» - если заранее известны все значения входных данных


Слайд 5

Коллизии хеш-функций


Слайд 6

Типы атак на хеш-функции Для n-битной хеш-функции Атака на обнаружение коллизий Требует ~ 2n/2 операций (парадокс дней рождения) Атака на нахождение прообраза Требует ~ 2n операций


Слайд 7

MD5 Доббертин (1996г) Псевдоколлизия – использовал свои IV Если MD5(x) = MD5(y), то MD5(x||S) = MD5(y||S) Ванг и Ю Мощный метод нахождения коллизий, основанный на дифференциальной атаке. ~ 240 операций Были приведены некоторые коллизии и написана программа для генерирования архивов и документов PDF с одинаковыми хешами


Слайд 8

SHA-0 Ванг Атака методом дифференциальных путей Используется возможность создания локальных коллизий в SHA-0 Сложность «прямой» реализации ~ 242 операций Можно заранее составить таблицу подходящих сообщений, тогда сложность составляет ~ 239 операций


Слайд 9

SHA-1 Ванг, Йинг, Ю Расширимые сообщения – разновидность множественной коллизии. Атака с использованием очень длинных сообщений Находят все промежуточные хеши для очень длинного сообщения и перебирают около 2106 блоков до совпадения с одним из исходных. Находят расширимое сообщение и расширяют его до длины исходного. Получают второй прообраз.


Слайд 10

Опасность коллизий Пример про Алису и её Босса Б А


Слайд 11

Опасность коллизий Пример про Алису и её Босса, прод. А


Слайд 12

Спасибо за внимание


×

HTML:





Ссылка: