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

Авторы

  • Е.А. Гречников
  • А.В. Адинец

Ключевые слова:

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2012-09-10

Выпуск

Том 13 (2012): Выпуск 3.

Раздел

Раздел 2. Программирование

Авторы

Е.А. Гречников

Московский государственный университет имени М.В. Ломоносова,
механико-математический факультет
Ленинские горы, 119899, Москва
• аспирант

А.В. Адинец

Московский государственный университет имени М.В. Ломоносова,
Научно-исследовательский вычислительный центр
Ленинские горы, 119991, Москва
• научный сотрудник

Библиографические ссылки

  1. Teat C., Peltsverger S. The security of cryptographic hashes // Proc. of the 49th Annual Southeast Regional Conference. New York: ACM, 2011. 103-108.
  2. National Institute of Standards and Technology (NIST). FIPS-180-2: Secure Hash Standard, August 2002. Available online at http://www.itl.nist.gov/fipspubs/.
  3. Grechnikov E.A., Adinetz A.V. Collision for 75-step SHA-1: intensive parallelization with GPU // Cryptology ePrint Archive: Report 2011/641. Available online at http://eprint.iacr.org/2011/641.
  4. Dobbertin H. Cryptanalysis of MD4 // Fast Software Encryption. LNCS 1039. D. Gollmann, Ed. Berlin: Springer, 1996. 53-69.
  5. Wang X., Yu H. How to break MD5 and other hash functions // Proc. of Eurocrypt. Berlin: Springer, 2005. 19-35.
  6. Wang X., Yin Y.L., Yu H. Finding collisions in the full SHA-1 // Proc. of CRYPTO. LNCS 3621. Berlin: Springer, 2005. 17-36.
  7. Chabaud F., Joux A. Differential collisions in SHA-0 // Proc. of CRYPTO. Berlin: Springer, 1998. 56-71.
  8. Biham E., Chem R., Joux A., Carribault P., Lemuet C., Jalby W. Collisions of SHA-0 and Reduced SHA-1 // Proc. of Eurocrypt. Berlin: Springer, 2005. 36-57.
  9. de Canniére C., Rechberger C. Finding SHA-1 characteristics: general results and applications // Proc. of ASIACRYPT. LNCS 4284. Berlin: Springer, 2006. 1-20.
  10. de Canniére C., Mendel F., Rechberger C. Collisions for 70-step SHA-1: on the full cost of collision search // Proc. of Conf. on Selected Areas in Cryptography. LNCS 4876. Berlin: Springer, 2007. 56-73.
  11. Adinetz A.V. NUDA programmer’s guide (http://nuda.sf.net).
  12. Satish N., Kim C., Chhugani J., Nguyen A.D., Lee V.W., Kim D., Dubey P. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort // Proc. of the 2010 Int. Conf. on Management of Data (SIGMOD’10). New York: ACM, 2010. 351-362.
  13. Grechnikov E.A. Collisions for 72-step and 73-step SHA-1: improvements in the method of characteristics. Cryptology ePrint Archive: Report 2010/413. Available at http://eprint.iacr.org/2010/413.