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

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

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

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

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

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

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

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

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

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

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

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

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

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