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

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