Параллельный алгоритм подбора одноблочной MD5-коллизии
Автор: Кузнецов Антон Александрович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 3 (26) т.6, 2015 года.
Бесплатный доступ
В работе описан параллельный алгоритм поиска коллизий хэшфункции MD5 и его имплементация с результатами прогона на вычислительном кластере. Параллельная программа поиска коллизии реализована на языке Си++ с использованием библиотеки MPI. Исходный код программы базируется на последовательной версии пограммы поика коллизий от нидерландского ученого Марка Стивенса. Автор уверен что алгоритм распараллеливания может быть применен для разработки эффективных параллельных программ поиска коллизий хэш-функций, алгоритм работы которых основан на разностном методе Вань. В ходе данного исследования с использованием высокопроизводительного кластера открыта новая пара одноблочных сообщений, MD5-дайджесты которых совпадают (образуют коллизию).
Криптоанализ, параллельное программирование, ускорители вычислений, хэш-функции.
Короткий адрес: https://sciup.org/14336159
IDR: 14336159
Список литературы Параллельный алгоритм подбора одноблочной MD5-коллизии
- R. L. Rivest. The MD5 Message-Digest Algorithm, Internet Request for Comments: RFC 1321, https://www.ietf.org/rfc/rfc1321.txt, April 1992.
- X. Wang, D. Feng, X. Lai, H. Yu. Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive, Report 2004/199, https://eprint.iacr.org/2004/199.pdf, 2004.
- T. Xie, D. Feng. Construct MD5 Collisions Using Just A Single Block Of Message, Cryptology ePrint Archive, Report 2010/643, https://eprint.iacr.org/2010/643, 2010.
- M. Stevens. Single-block collision attack on MD5, Cryptology ePrint Archive, Report 2012/040, https://marc-stevens.nl/research/md5-1block-collision/, 2012.
- P. C. Van Oorschot, M. J. Wiener. Parallel collision search with cryptanalytic applications//Journal of Cryptology, 12 (1999). P. 1-28.
- http://supercomputer.susu.ac.ru/computers/tornado/.
- http://www.botik.ru/~botik/rnd/message1ak, http://www.botik.ru/~botik/rnd/message2ak.
- http://marc-stevens.nl/research/md5-1block-collision/.
- A. A. Kuznetsov. An algorithm for MD5 single-block collision attack using high-performance computing cluster, Cryptology ePrint Archive, Report 2014/871, https://eprint.iacr.org/2014/871, 2014.
- H. Dobbertin. The status of MD5 after a recent attack//CryptoBytes, V. 2. No. 2. (1996), 6 p.
- А. А. Кузнецов. Исследование криптостойкости протокола аутентификации BotikKey к компрометации уязвимостей алгоритма хеширования MD5//Программные системы: теория и приложения, Т. 6, №. 1. (2015). С. 135-145, URL http://psta.psiras.ru/read/psta2015_1_135-145.pdf.
