Все о паролях и практической криптографии

Перебор паролей и CUDA

Недавно вышла новая версия программы по перебору паролей для архивов RAR cRARk v. 3.2 (пока BETA), где я впервые попробовал применить технологию вычислений на видеокартах NVIDIA CUDA. О своих первых впечатлениях об использовании CUDA я бы хотел рассказать.

Первое, и самое главное: в таких задачах, как перебор паролей, которые по своей сути допускают легкое распараллеливание, использование CUDA оказывается чрезвычайно простым. Написание исходного текста программы на CUDA оказалось очень легким: я взял код функции SetCryptKeys() из исходных текстов UnRAR, добавил к ней свободно распространяемые реализации криптографических функций SHA-1 и AES, после чего вставил у всех используемых функций спецификатор __device__, который означает, что эти функции будут выполнятся на устройстве (GPU). По сути, никаких переделок кода с языка C/C++ на CUDA не потребовалось и первая же версия программы, которая смогла скомпилироваться, выдавала осмысленные результаты!

Далее, сложность отладки под GPU оказалась преувеличенной. В опциях компилятору можно указать “-deviceemu”, после чего отлаживать становится возможным в режиме эмуляции, под любимым отладчиком, например, прямо в Visual Studio. Да, в этом режиме эмуляция GPU невозможна на 100%, и некоторые тонкие моменты (например, синхронизацию потоков) там не отладить, но тем не менее режим эмуляции позволяет отладить большинство возникающих проблем. Также я столкнулся с тем, что запись по невыровненному адресу в режиме эмуляции работает, а на реальном устройстве - нет:

long A[N], i;

* (long *) ((char *)A + 3) = i;  // запись по адресу,
                                 // не кратному 4

Компилятор nvcc, несмотря на версию 2.1, все еще является сыроватым. Так, я несколько раз в разных ситуациях получал сообщение о внутренней ошибке компилятора, и совершенно было непонятно, где искать проблему, так номер строки в этом случае не выводится. Опытным путем было выяснено, что он не любит использования функции memcpy(), которая часто встречается в реализации криптопримитивов. По логике, должно быть сообщение об ошибке вызова функции хоста (__host__) на устройстве, вместо этого выдавалось сообщение: “Signal: caught in PU_adjust_addr_flags phase”.

Следующая проблема, которая не описана как следует в документации, заключалась в том, что каждый вызов ядра (kernel) должен выполняться на GPU не более 5 секунд. Поскольку для проверки одного пароля RAR необходимо сделать около 70.000 преобразований SHA-1, то, задавая довольно большие размеры сетки (grid), можно очень скоро упереться в этот барьер, получая сообщение типа “the launch timed out and was terminated”.

Наконец, оптимизация программ на CUDA оказалась довольно трудоемкой и малоэффективной. Так, первая рабочая версия cRARk под CUDA выдавала около 200 паролей в секунду, нынешняя версия показывает 240 (на GeForce 8600GTS). При этом мне кажется, что скорость можно поднять еще как минимум в 2 раза (мое предположение основывается на скорости вычислений MD5 на CUDA, рассмотренной в прошлый раз). На сайте crark.net я выложил исходники реализации перебора паролей RAR на CUDA. Если есть желающие помочь в оптимизации этой бесплатной утилиты, буду рад.

Таким образом, технология CUDA, бесспорно, является очень эффективной и легкой в применении в задачах перебора паролей, но при практической реализации возникает ряд подводных камней, затрудняющих получение наилучших результатов. В частности, для рассмотренной задачи перебора паролей RAR пока скорость на топовых моделях видеокарт и процессоров оказывается примерно одинаковой - около 1000 паролей в секунду.

Tags: cRARk, CUDA, RAR, пароли

GPU, Оптимизация, Скорость | Pavel Semjanov | 27 Апрель 2009 19:16

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

By Mixa, 1 Июнь 2009 @ 2:10

Большое спасибо за такую замечательную программу!
Вы писали: “скорость на топовых моделях видеокарт и процессоров оказывается примерно одинаковой - около 1000 паролей в секунду.”
У меня несколько другие результаты, я что-то делаю не так? (C2D3.6, 8800GTS)
http://www.picatom.com/z/img/Clipboard01-44.jpg
Или дело в том, что архив у меня версии 2.0?
By Pavel Semjanov, 1 Июнь 2009 @ 11:40

Да, я имел в виду архивы 3.x. Архивы 2.х имеют скорость гораздо выше. (Кстати, когда этот формат только появился, на Pentium 166 скорость была опять-таки 1000 п/c). Тем более, что механизм CUDA в cRARk не поддерживает ни RAR 2.0, ни карты 8800.
By Mixa, 1 Июнь 2009 @ 23:00

Вы писали: “Тем более, что механизм CUDA в cRARk не поддерживает ни RAR 2.0, ни карты 8800″.
Сорри, что я такой непонятливый
Это без использования CUDA у меня 20624 паролей/сек.?
А программа пишет CUDA enabled…
http://www.picatom.com/z/img/Clipboard02-9.jpg
By Mixa, 2 Июнь 2009 @ 1:10

Таки похоже что действительно, это на одном ядре такая скорость… А что было-бы на GPU? Не планируете ли вы добавить поддержку RAR архивов версии 2.х ?
By Pavel Semjanov, 2 Июнь 2009 @ 11:03

Нет, это, во-первых, бессмысленно для устаревшего формата и, во-вторых, шифрование RAR 2.0 не подходит для реализации под CUDA.
By Alexander, 29 Июнь 2009 @ 19:39

Павел, спасибо за программу!

Я хотел тоже уточнить пару моментов:
1. Вики (и профильная ветка на IXBT) утверждают, что AES применяется в RAR, начиная с 2.9 - так ли это? и считаются ли эти архивы программой как фактически 3.х?
2. В доке по CUDA заявляется, что compute compatibility 1.0 только у старых 8800, новые же - 8800 GT/GS, 8800 GTS 512 - поддерживают 1.1. Это я к тому - не пугайте новичков, пожалуйста :), а то я и сам поначалу расстроился, что ускорения не будет…

Ну и собственно вопрос: учитывая вышесказанное, должно ли заработать ускорение на моем C2Q 2.4/8800 GT, если версия для извлечения 2.9?
И является ли скорость подбора 65 тыс.п/c (через 50 часов снижается до 30 тыс.п/c, непонятно почему) для пароля [$a]* из 7 знаков нормальной?
И еще небольшая просьба - если не сложно, выводите на экран, работает ли программа с ускорением или без такового.
By Pavel Semjanov, 3 Июль 2009 @ 10:49

1. AES применяется с версии 3.0, многое из которой включалось в версию 2.9. Все существующие архивы на сегодняшний день имеют номер версии не старше чем 2.9
2. Возможно.
3. Не надо запускать 2 копии программы на одном GPU
4. Если программа выводит размер блока, то она работает на GPU
By nemorr, 22 Сентябрь 2009 @ 9:36

здравствуйте.
Огромное спасибо за программу!
У меня есть пара вопросов:
Я правильно понял, что на 64-битных версиях windows CUDA не запустить? (при запуске отваливается видео драйвер, без режима cuda -с работает)
И многоядерность (q6600) процессора для ускорения тоже нельзя использовать?
By Pavel Semjanov, 22 Сентябрь 2009 @ 9:54

Если вылетает видеодрайвер (обычно в Vista, Windows 7) - читайте
http://www.microsoft.com/whdc/device/display/wddm_timeout.mspx

Что касается многоядерности, то ее нет и не будет. Потому что многоядерность поддерживает Parallel RAR Password Recovery
http://www.parallelrecovery.com/rar-password.html, которая использует те же алгоритмы, что и cRARk.
By userCRARK, 20 Ноябрь 2009 @ 23:32

Win XP (работаю по инструкции крарк - кстати написано емко и хорошо как коменты исходника - нет никакоких блабла)
CPU C2D-T5800-2GHz [CPU rate = 1.90]
GPU http://www.nvidia.ru/object/geforce_9300m_gs_ru.html
при ломании не подключает КУДА:
cudaGetDeviceCount() failed: CUDA version is insufficient for CUDART version
и процес ломания идет примерно на rate = 140 p/s

спасибо за прогу спасибо и за ответ
By Pavel Semjanov, 30 Ноябрь 2009 @ 16:48

Поставить последнюю версию CUDA - 2.3.
By FeodorMD, 5 Декабрь 2009 @ 1:29

Большое спасибо за прогу, Павелю
У меня такая проблема:
AMD Athlon 64×2 Dual Core Processor 4400+ 2.31ГГц, 2ГБ ОЗУ
Видеокарта NVIDIA GeForce 8500 GT
ОС: Windows XP SP 3
всё обновлено, но скорость перебора без GPU 50 p/s, а с GPU 147 p/s
Подскажите, пожалуйста: можно ли как-то увеличить скорость перебора???
Спасибо
By Pavel Semjanov, 11 Декабрь 2009 @ 11:06

Естественно, поставить более мощную видеокарту.
By Napalm, 17 Январь 2010 @ 16:50

Прога просто супер. Автору огромное спасибо. Но есть проблема. Ранее использовал crark в Win XP. Сейчас установил Win 7х64. После запуска программы вылетает драйвер видеокарты. Вопрос можно ли устранить эту проблему.
By Zenitur, 28 Январь 2010 @ 3:26

Похоже, во всём виновата 64-битность дистрибутива…
By Zenitur, 29 Январь 2010 @ 2:45

Возникла проблема. Раньше сутками перебирало, теперь не хочет.
zenitur@linux-athlonxp:~/crark-3.2> ./crark-hp -l7 -g15 07111.rar
cRARk-HP (Encrypted Headers) CUDA enabled v. 3.2b Freeware
Copyright 1995-2001, 2006-09 by P. Semjanov,
http://www.crark.net
portions (c) 1993-2005 Eugene Roshal
(c) PSW-soft Password Cracking Library PCL v. 2.0d by P. Semjanov

CUDA device GeForce 9800 GT found, multiprocessors = 14, GPU rate = 0,47
Choosing best crypto functions…………………………………………….
Chosen: ASM (Prescott/AMD), SSE2 (P4/Core 2) (/f1444)
Ticks per password expected = 18725377, theoretical = 27000000, CPU rate = 1,44

Processing line 66 of password definition file…
Testing 7-chars passwords …
Block size is: 112 x 64 (-m112)
! cudaThreadSynchronize() failed: the launch timed out and was terminated
Try to use -m56 option
Testing 8-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 9-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 10-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 11-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 12-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 13-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 14-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated
Testing 15-chars passwords …
! cudaMalloc() failed: the launch timed out and was terminated

Passwords tested = 78848 (time = 01:30,23, rate = 874 p/s)
Total tested = 78848, slow tests = 0
Password not found

Total passwords tested = 78848, slow tests = 0
zenitur@linux-athlonxp:~/crark-3.2>
Может, всё дело в том, что я делал Ctrl-C дял выхода из приложения несколько раз? В разных дистрибутивах картина одинаковая и проявляется меньше чем через полчаса. Температура в норме. А ещё я делал разгон для ускорения, потом убрал но проблема осталась. Игры работают без проблем. И вообще до 800 упало когда ошибка, перезагружаюсь и выдаёт 1500.
By Pavel Semjanov, 30 Январь 2010 @ 14:23

Если раньше работало, то это не ко мне.
Попробуйте на чистой системе со свежеустановленными драйверами.
By DrVooDoo, 30 Январь 2010 @ 16:50

Upd. Прочитал что нужно сделать.
сделал такой батничек

echo off
cmd /K crark-hp 1NetScan.rar

при запуске мне пишет

archive header is not encrypted. Use crack.exe program.

Использую crack.exe в батнике - вроде как все нормально, но только у меня такое чувство что он перебирает процессором, а не видюхой. Как это можно проверить?
By lamko, 30 Январь 2010 @ 18:13

Добрый день, Pavel Semjanov,вопрос к вам -
у меня система с2д 2.66 8500gt ,поставил cuda драйвер с сайта нвидии, в программе карта определилась и gpu rate 0.07,cpu rate 1.93
block size 8×64 - больше не получается,вылетает и просит попробовать с -m8 /110 пассов в секунду при завершении показывает.
-
у меня очень слабая система или я что-то делаю не так?помогите пожалуйста.Заранее спасибо.
By Pavel Semjanov, 31 Январь 2010 @ 0:06

Перебор идет на видеокарте, если программа пишет “Block size: xxx x 64″
By Pavel Semjanov, 31 Январь 2010 @ 0:07

Очень слабая система. Нужна видеокарта как минимум с 8 мультипроцессорами, лучше 16 и больше.
By Zenitur, 11 Февраль 2010 @ 23:53

Нашёл решение проблемы на главной странице программы: воспользуйтесь опцией -m(число) - смотри подсказку в ошибке. Зато столкнулся с другой проблемой. crark-hp часто говорит CRC OK и пробует пароль. Не подходит. Дальше перебирает. После второго раза Ошибка Сегментирования. Поэтому перебираю пока процессором ((
By Zenitur, 12 Февраль 2010 @ 0:10

Да что же это такое… Через пару минут после написания:
baaaauucuh - Header CRC Ok
Ошибка сегментирования
zenitur@linux-athlonxp:~/crark-3.2>
By Aleks Versus, 28 Март 2010 @ 18:19

Можно по-подробнее рассказать о создании словарей? В файлe russian.def приведены только примеры расположения, как самому составить словарь и использовать его? Возникла необходимость протестировать слово, написанное в разных регистрах, то есть например: crack, Crack, CrAcK, CRACK, можно ли задать как-то перебор регистра букв? И до кучи, хотелось бы брать слова из словаря и перебирать в них символы меняя их регистр. Это осуществимо? Если это описано в коментариях файла russian.def, ткните носом, а то сам я походу не увижу.
By Aleks Versus, 28 Март 2010 @ 23:33

Так, словарь я сделал. Остается вопрос о переборе регистра для символов. Очень лень писать двадцать слов по пятнадцать раз.
By Pavel Semjanov, 29 Март 2010 @ 17:19

Для перевода в регистр используются модификаторы .u, .l
By Oleg1980, 18 Июль 2010 @ 10:59

Павел спасибо за програму! Тестировал ее с другими переборщиками - cRARk оказался на высоте, вот только еще не совсем разобрался с параметрами перебора.
1.Как например задать параметр, что бы перебирались весь регистр английских букв, цифры и спецзнаки? Вот так подойдет:
##
[$A $a $1 $!] - если да почему тогда у меня в консоли русские буквы перебираются?
2.Как выставить по умолчанию -l1 -g10?
И вообще какой -значный пароль реально подобрать cRARk, -g10 достаточно, или можно больше?
3.Время от времени появляется надпись:
Header CRC Ok - что это означает?
By Pavel Semjanov, 18 Июль 2010 @ 11:07

1. Все верно. По поводу русских букв - в почту со скриншотом.
2. По умолчанию - никак. На мой взгляд, больше 6-7 символов подобрать нельзя, если нет никакой дополнительной информации о пароле.
3. Просто пароль проходит первую (быструю) проверку.