ВВЕДЕНИЕ 4
ГЛАВА 1. КРИПТОГРАФИЧЕСКАЯ ХЕШ-ФУНКЦИЯ 6
1.1 Основные определения и понятия 6
1.2 Требования к криптографическим хеш-функциям 7
1.3 Степень сложности 8
1.4 Структура Меркла — Дамгарда 9
1.5 Семейство хеш-функций MD и SHA 10
1.5.1 Семейство хеш-функций Message Digest (MD) 10
1.5.2 Семейство хеш-функций SHA 12
ГЛАВА 2. АЛГОРИТМ ХЕШИРОВАНИЯ MD5 15
2.1 История и криптоанализ хеш-функции MD5 15
2.2 Безопасность хеш-функции MD5 17
2.3 Атака коллизией на хеш-функцию MD5 17
2.4 Алгоритм хеширования MD5 18
2.5 Радужные таблицы и MD5 22
ГЛАВА 3. КОЛЛИЗИИ 27
3.1 Классическая атака коллизией 27
3.2 Атака коллизией с заданным префиксом 28
3.3 Примеры коллизий 30
3.4 Создание двух различных исполняемых файлов с одинаковым хешем 32
ГЛАВА 4. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ 35
4.1 Используемое оборудование для вычислений 35
4.2 Основы параллельных вычислений 36
4.3 Технологии параллельного программирования 38
ГЛАВА 5. АЛГОРИТМ МАРКА СТИВЕНСА ПОИСКА ОДНОБЛОЧНОЙ КОЛЛИЗИИ 40
5.1 Оригинальный алгоритм Марка Стивенса поиска одноблочной коллизии 40
5.2 Параллельный алгоритм Марка Стивенса поиска одноблочной коллизии 42
5.3 Реализация параллельной версии алгоритма Марка Стивенса поиска одноблочной коллизии 44
5.4 Анализ скорости работы реализаций, результаты 45
ЗАКЛЮЧЕНИЕ 47
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 48
ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ 54
ПРИЛОЖЕНИЕ 1 56
ПРИЛОЖЕНИЕ 2
Хеш-функции играют огромную роль в криптографии и часто используются в ЭЦП, аутентификации, обеспечении целостности данных. В силу того, что криптографические хеш-функции используются для проверки неизменности исходной информации, то даже потенциальная возможность нахождения коллизии в хеш-функции может обернуться компрометацией. Допустим, если есть возможность найти коллизию хеш-функции, использующуюся в электронной подписи, то это порождает возможность подделывания её. Поэтому мерой криптостойкости хеш-функции считается трудоемкость нахождения коллизии и прообраза. Чтобы достаточно хорошо разобраться в данном вопросе пришлось изучить большое количество материалов, значительная часть которых написана на английском языке, а именно работы: Марка Стивенса, Кузнецова А.А, Властимила Клима, Тао Се (Tao Xie) и Фэн Дэнго (Feng Dengguo) и работы других исследователей.
Целью работы является реализация параллельного алгоритма Марка Стивенса поиска коллизий в алгоритме хеширования MD5 на основе последовательного и сравнение скорости их работы.
Объектом исследования является алгоритм хеширования MD5.
Предметами исследования являются различные уязвимости данной хеш- функции, ранее реализованные атаки, найденные коллизии, алгоритмы, использованные для атак на хеш-функцию.
Для достижения указанной цели в дипломной работе решаются следующие исследовательские задачи:
1. Изучение материалов, связанных с созданием и использованием хеш- функций.
2. Изучение материалов, связанных с историей и криптоанализом хеш- функций.
3. Изучение уязвимостей и атак в алгоритме хеширования MD5.
4. Попытки реализации атак на алгоритм хеширования MD5.
5. Изучение алгоритма генерации одноблочных коллизий в MD5 Марка Стивенса.
6. Изучение и анализ способов распараллеливания данной атаки.
7. Создание параллельной реализации алгоритма Марка Стивенса.
Актуальность работы заключается в том, что MD5 до сих пор может где- то использоваться в качестве криптографической хеш-функции, а это большой риск. Кроме того, криптоанализ старых хеш-функций, улучшения атак на них, могут повлиять на создание новых хеш-функций. Ведь при создании новой устойчивой хеш-функции необходимо учитывать все возможные атаки на неё. Без коллизий хеш-функция обойтись не может в связи с принципом Дирихле, а устойчивая хеш-функция должна свести их вероятность нахождения к минимуму.
В процессе дипломной работы был реализован параллельный алгоритм Марка Стивенса поиска коллизий в MD5. Самая большая сложность, возникшая при работе, это нехватка ресурсов, а именно: ограниченное время и нехватка вычислительных мощностей. Другими проблемами стали нестабильность некоторых систем, а так же отключение электроэнергии (отсутствие источников бесперебойного питания). Из имеющегося оборудования ноутбук меньше всего подходил под мои цели: он быстро нагревался, снижалась его производительность из-за механизма дросселирования тактов (throttling). Был проведен анализ скорости работы при различных конфигурациях компьютера с использованием разных реализаций программ. Так же были успешно произведены атаки на хеш-функцию MD5.
Благодаря данной выпускной квалификационной работе, я получил много знаний и навыков, как в плане изучения криптостойкости алгоритмов хеширования, так и в плане использования технологий параллельного программирования. Появилось желание работать дальше в данном направлении, изучая криптографические хеш-функции, использующиеся сегодня, к примеру, SHA-2.
Я считаю, что нужно серьезно относиться к рекомендациям использования новых криптографических хеш-функций взамен старых. Так же уделять достаточное внимание публикациям о нахождении новых уязвимостях и удачных атаках. С каждым годом производительность вычислительных устройств растет, а значит, должны обновляться и криптографические хеш-функции, криптостойкость которых должна расти.
