Параллельный алгоритм подбора одноблочной MD5-коллизии
Автор: Кузнецов Антон Александрович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 3 (26) т.6, 2015 года.
Бесплатный доступ
В работе описан параллельный алгоритм поиска коллизий хэшфункции MD5 и его имплементация с результатами прогона на вычислительном кластере. Параллельная программа поиска коллизии реализована на языке Си++ с использованием библиотеки MPI. Исходный код программы базируется на последовательной версии пограммы поика коллизий от нидерландского ученого Марка Стивенса. Автор уверен что алгоритм распараллеливания может быть применен для разработки эффективных параллельных программ поиска коллизий хэш-функций, алгоритм работы которых основан на разностном методе Вань. В ходе данного исследования с использованием высокопроизводительного кластера открыта новая пара одноблочных сообщений, MD5-дайджесты которых совпадают (образуют коллизию).
Криптоанализ, параллельное программирование, ускорители вычислений, хэш-функции.
Короткий адрес: https://sciup.org/14336159
IDR: 14336159 | УДК: 519.682.3
Psta.psiras.ru/
The paper describes a parallel algorithm for searching for MD5 hashfunction collisions and its implementation with run results on a computational cluster. The parallel collision search program is implemented in C ++ language using the MPI library. The source code of the program is based on a consistent version of the program of the search for collisions from the Dutch scientist Mark Stevens. The author is sure that the parallelization algorithm can be used to develop efficient parallel programs for finding collisions of hash functions whose algorithm is based on the difference method of Wan. In the course of this study, using a high-performance cluster, a new pair of single-block messages is opened, MD5-digests of which coincide (they form a collision).
Список литературы Параллельный алгоритм подбора одноблочной 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.
