Построение коллизии для 75-шаговой версии хеш-функции SHA-1 с использованием ГПУ-кластеров
Гречников Е.А., Адинец А.В.

Криптографические хеш-функции, в частности SHA-1, в настоящее время широко используются в современных информационных технологиях. Важным свойством таких функций является устойчивость к коллизиям, т.е. сложность построения двух различных входных сообщений, значения хеш-функции от которых совпадают. Предложено развитие метода разностных (дифференциальных) атак для поиска коллизий хеш-функции SHA-1 и ее сокращенных вариантов. Описывается реализация метода характеристик для хеш-функции SHA-1 на кластере из графических процессоров. Использование различных оптимизаций позволило достичь эффективности ГПУ-реализации до 50% и ускорения в 39 раз по сравнению с реализацией на одном ядре ЦПУ. Оптимизации включают в себя модификацию метода поиска характеристик. На текущий момент предложенные улучшения метода и использование ГПУ-раздела суперкомпьютера "Ломоносов" позволили найти коллизию для SHA-1, сокращенной до 75 шагов (полная функция состоит из 80), что является мировым рекордом. Статья рекомендована к публикации Программным комитетом Международной научной конференции "Параллельные вычислительные технологии" (ПаВТ-2012; http://agora.guru.ru/pavt2012).

Ключевые слова: криптоанализ, криптографические хеш-функции, построение коллизий, SHA-1, графические процессоры, кластеры, параллельные вычисления

Название статьи, аннотация и ключевые слова на английском языке

Гречников Е.А., аспирант, e-mail: grechnik@mccme.ru - Московский государственный университет им. М.В. Ломоносова, механико-математический факультет, Ленинские горы, 119899, Москва;
Адинец А.В., науч. сотр., e-mail: adinetz@gmail.com - Научно-исследовательский вычислительный центр Московского государственного университета им. М.В. Ломоносова, Ленинские горы, 119991, Москва