Тестирование скорости взломщиков MD5

В связи с появлением на сайте www.password-crackers.ru тестов скорости под графическую карту (GPU) NVIDIA с использованием технологии параллельных вычислений CUDA я провел ряд тестов взломщиков MD5-хэшей, потому что взлом MD-подобных алгоритмов хэширования идеально подходит для распараллеливания как на центральных, так и на графических процессорах.

Действительно, семейство хэшей MD (куда относятся алгоритмы MD4, MD5, SHA) отличает простота и компактность. Они не используют никакую дополнительную память, кроме непосредственно сообщения и выходного значения, а все операции представляют собой простые арифметические и логические действия над 32-битными данными, а именно: AND, OR, XOR, NOT, сложение и циклический сдвиг, для которых в ассемблере обычно есть соответствующие команды.

Оптимизация перебора хэшей MD5 и аналогичных состоит в следующем:

1. Использование параллельных вычислений, т.к алгоритм перебора паролей прекрасно распараллеливается - для процессоров на 2, 4 и более потоков (по количеству ядер), для GPU - на 64/128/256 и более.
2. Вычисление нескольких хэшей одновременно в одном потоке. Для этого подходят MMX- и SSE-инструкции, позволяющие одновременно вычислять 2 и 4 хэша соответственно. Перевести ассемблерный код на использование MMX или SSE довольно просто - надо заменить обычные ассемблерные инструкции и регистры на соотвествующие MMX/SSE. Код ниже показывает соответствие обычного и SSE-кода одного из шагов на первом раунде MD5:
   

   xor edi, edx	pxor xmm4, xmm3
   and edi, ebx	pand xmm4, xmm1
   xor edi, edx	pxor xmm4, xmm3
   lea eax, DWORD PTR 3614090360[edi+eax]	paddd xmm0, XMMWORD PTR _DATA_R0[0] paddd xmm0, xmm4
   mov edi, ebx	movdqa xmm4, xmm1
   add eax, DWORD PTR [esi]	paddd xmm0, XMMWORD PTR [esi]
   rol eax, 7	movdqa xmm5, xmm0 pslld xmm0, 7 psrld xmm5, 25 por xmm0, xmm5
   add eax, ebx	paddd xmm0, xmm1

   Как видно, коды очень похожи, за исключением реализации циклического сдвига - вместо одной операции на SSE приходится делать 4: два обычных сдвига в разные стороны и потом объединение результатов. (Странно, что даже в самой последней версии SSE 4.2 команд для циклических сдвигов так и не появилось).

3. Исключение сложений с нулевыми данными. При коротких паролях данные в конце 64-байтового блока являются нулевыми, поэтому операции сложения с ними можно исключить.
4. Инверсия последнего раунда. Из-за нулевых данных удается также  исключить вычисления на последнем раунде, инверсировав его и проверяя пароль на правильность раньше.

Для тестирования скорости подбора MD5-хэшей использовались следующие программы:

1. Тестовый, неоптимизированный код под CUDA MD5-PoC от Андрея Беленко (в исходниках под Visual C)
2. Бесплатная утилита от Elcomsoft Lighting Hash Cracker (LHC) v. 0.52
3. Бесплатная утилита BarsWF v. 0.8 от Сваричевского Михаила
4. Коммерческая программа Extreme GPU Bruteforcer (EGP) v. 1.4.2 от InsidePro.
5. Коммерческий профессиональный продукт Elcomsoft Distributed Password Recovery (EDPR) v. 2.71
6. Бесплатная утилита UDC v. 3.2.1.0, бывшая чемпионом по скорости до внедрения технологии CUDA

Тесты проводились на Intel Core 2 Duo 6300, 1.86 GHz + NVIDIA GeForce 8600 GTS, 675 MHz. Результаты представлены в таблице:

Таблица. Скорость перебора MD5-хэшей на CPU и GPU, миллионов хэшей/сек

Примечание *. В одном случае утилита LHC искомый пароль не нашла.

Выводы:

1. Технология CUDA кардинально меняет представления о скорости перебора хэшей и стойкости паролей. Даже самая первая, неоптимизированная версия переборщика показывает скорость выше, чем самая быстрая, оптимизированная под SSE версия для CPU. При этом тактовая частота GPU была в 3 раза меньше. Современные графические карты способны вычислять более полумиллиарда хэшей в секунду, что означает, что они способны перебрать все буквенно-цифровые пароли до 8 символов включительно за пару дней!
2. Программа BarsWF оправдывает звание самого быстрого взломщика MD5, показывая фантастические результаты как на CPU, так и на GPU. По утверждению автора, она тратит 58 тактов CPU на один хэш, что, бесспорно, является впечатляющим. (У меня есть код MD5, который требует 130 тактов для полного MD5, т.е. с исключенным последним раундом он бы исполнялся около 100 тактов. Куда деваются еще 40, непонятно). В любом случае, поздравляем автора с наградой в категории MD5-хэши.
3. Использование технологий обычных вычислений на графических видеокартах (GPGPU) пока еще может вызвать затруднения как у разработчиков, так и у пользователей. Для разработчиков отмечу непривычную архитектуру высокопараллельных вычислений и трудность отладки (что приводит к ошибкам, как в утилите LHC). Для пользователей - это сложность в запуске таких программ, требующих совместимых видеокарт, последних версий драйверов и некоторых дополнительных dll-библиотек, плюс, для достижения масчимальной скорости,  желательны дополнительные настройки под конкретную видеокарту.

Дополнительные ссылки:

1. NVIDIA CUDA — неграфические вычисления на графических процессорах
2. Тестирование скорости работы MD5-взломщиков от автора BarsWF

Нет комментариев

Еще нет комментариев.

RSS лента комментариев к этой записи. TrackBack URI

Оставить комментарий