Наверное каждый из нас хоть раз забывал пароль от какого-нибудь важного сайта, а потом пытался расшифровать его по сохранившимся кукам в браузере. Возможно это были даже не Ваши куки, но это не важно — если Вам интересна тема скоростного брутфорса, то добро пожаловать под кат!
Сразу скажу, что описанные в статье техники ускорения подходят для любого алгоритма хеширования, но из-за широкой распространённости я выбрал именно md5.
Возможно брутфорс не всегда целесообразно использовать для решения конкретной задачи, но, тем не менее, это самый универсальный метод, который гарантированно даёт результат, пусть и самый долгий.
Существует два пути повышения производительности: хардверный и софтверный. Первый заключается в покупке железок помощнее и пускании на них скриптов для брутфорса, но это не наш метод, поэтому выберем второй — тщательная оптимизация и максимальное использование того, что имеем. А имеем мы довольно слабый по текущим меркам системный блок с процессором Dual Core 1.8 Ghz, 2 GB Ram и видеоплатой Nvidia 9800 GT. Итак, попробуем выжать из него все соки!
В данном случае наверное очевидным выбором является ассемблер, но мне хотелось бы сохранить переносимость кода, поэтому я выбрал Си как наиболее быстрый вариант после ассемблера.
Алгоритм md5 устроен таким образом, что он оперирует не сразу всеми данными целиком, а разбивает данные на блоки по 64 байта и обрабатывает каждый блок отдельно. Учитывая, что перебор до 64 символов (а если быть точным, то до 59, ибо остальную часть блока занимает служебная информация) физически невозможен даже на суперкомпьютерах, т.к. занимает десятки лет, то это разбиение можно вообще исключить и заранее выделить некий массив длиной в 64 байта, куда и записывать возможные варианты пароля. Также, дабы не сравнивать между собой все 16 байтов полученного хеша, целесообразно сразу перевести исходный хеш в 32-битные числа A, B, C и D и уже их сравнивать с полученными в процессе перебора, т.к. сравнение четырёх 32-битных чисел на современном процессоре будет производиться гораздо быстрее, чем шестнадцати 8-битных.
Для начала попробуем поиграться с компилятором. Я использовал GCC версии 4.4.5. Компилируем брутфорсер без дополнительных флагов и запускаем тест:
В качестве тестового пароля используется 12345. Алфавит, используемый в переборе, состоит из цифр, заглавных и строчных английских букв — для теста этого вполне достаточно.
Далее, попробуем добавить флаги -O3 (максимальный уровень оптимизации) и -static (статическая линковка, все библиотеки включаются непосредственно в исполняемый файл) и снова запускаем тест:
В итоге получаем ускорение аж в ~3.5 раза!
Поскольку процессор у нас имеет два ядра, попробуем запустить тот же тест в два потока:
Получаем ускорение ещё в ~2 раза, что, в общем то, вполне логично.
Также, можно попробовать скомпилировать брутфорсер с использованием пробной версии Intel C++ Compiler, который лучше всех оптимизирует код (при условии, что код компилируется под процессор Intel, конечно), но мне это не дало ощутимого прироста в производительности, поэтому я не буду приводить здесь замеры.
Действительно, если у нас есть ещё один процессор (а точнее, аж 112 маленьких процессоров), который скучает без дела, так почему бы его не использовать? Для организации рассчётов на GPU существуют два решения: CUDA и BrookGPU, для видеокарт NVIDIA и AMD соответственно. Поскольку у нас есть только видеокарта от NVIDIA, будем использовать CUDA для вычисления md5-хешей на GPU.
Главная проблема здесь заключается в том, что под GPU используется совершенно другой принцип программирования и просто так организовать цикл, перебирающий все возможные пароли не получится, ибо у каждого потока есть свой таймаут, по истечении которого поток автоматически завершается.
Обойти это можно, если основной цикл вынести на CPU и там же заранее просчитывать возможные варианты пароля для каждого из потоков GPU, а на самом GPU уже считать по одному хешу на поток и сравнивать с исходным значением.
Попробуем это в действии:
Результатами совместных усилий CPU+GPU удалось достичь ускорения ещё в ~2 раза! Это уже вполне неплохие цифры, и, если набраться терпения, вполне реально находить пароли длиной 9 и больше символов, даже если алфавит включает в себя символы знаков препинания и другие языки.
P.S. Исходники, использованные в тестах, можно получить с помощью git:
Сразу скажу, что описанные в статье техники ускорения подходят для любого алгоритма хеширования, но из-за широкой распространённости я выбрал именно md5.
Возможно брутфорс не всегда целесообразно использовать для решения конкретной задачи, но, тем не менее, это самый универсальный метод, который гарантированно даёт результат, пусть и самый долгий.
Существует два пути повышения производительности: хардверный и софтверный. Первый заключается в покупке железок помощнее и пускании на них скриптов для брутфорса, но это не наш метод, поэтому выберем второй — тщательная оптимизация и максимальное использование того, что имеем. А имеем мы довольно слабый по текущим меркам системный блок с процессором Dual Core 1.8 Ghz, 2 GB Ram и видеоплатой Nvidia 9800 GT. Итак, попробуем выжать из него все соки!
0. Выбор языка программирования
В данном случае наверное очевидным выбором является ассемблер, но мне хотелось бы сохранить переносимость кода, поэтому я выбрал Си как наиболее быстрый вариант после ассемблера.
1. Ускорение обсчёта md5
Алгоритм md5 устроен таким образом, что он оперирует не сразу всеми данными целиком, а разбивает данные на блоки по 64 байта и обрабатывает каждый блок отдельно. Учитывая, что перебор до 64 символов (а если быть точным, то до 59, ибо остальную часть блока занимает служебная информация) физически невозможен даже на суперкомпьютерах, т.к. занимает десятки лет, то это разбиение можно вообще исключить и заранее выделить некий массив длиной в 64 байта, куда и записывать возможные варианты пароля. Также, дабы не сравнивать между собой все 16 байтов полученного хеша, целесообразно сразу перевести исходный хеш в 32-битные числа A, B, C и D и уже их сравнивать с полученными в процессе перебора, т.к. сравнение четырёх 32-битных чисел на современном процессоре будет производиться гораздо быстрее, чем шестнадцати 8-битных.
2. Оптимальное использование CPU
Для начала попробуем поиграться с компилятором. Я использовал GCC версии 4.4.5. Компилируем брутфорсер без дополнительных флагов и запускаем тест:
~$ make PARAMS=""
~$ time ./brute 827ccb0eea8a706c4c34a16891f84e7b
...
real 0m22.164s
user 0m22.080s
sys 0m0.020s
В качестве тестового пароля используется 12345. Алфавит, используемый в переборе, состоит из цифр, заглавных и строчных английских букв — для теста этого вполне достаточно.
Далее, попробуем добавить флаги -O3 (максимальный уровень оптимизации) и -static (статическая линковка, все библиотеки включаются непосредственно в исполняемый файл) и снова запускаем тест:
~$ make PARAMS="-O3 -static"
~$ time ./brute 827ccb0eea8a706c4c34a16891f84e7b
...
real 0m6.422s
user 0m6.370s
sys 0m0.020s
В итоге получаем ускорение аж в ~3.5 раза!
Поскольку процессор у нас имеет два ядра, попробуем запустить тот же тест в два потока:
~$ make PARAMS="-O3 -static -DTHREADS=2"
~$ time ./brute 827ccb0eea8a706c4c34a16891f84e7b
...
real 0m3.763s
user 0m6.530s
sys 0m0.020s
Получаем ускорение ещё в ~2 раза, что, в общем то, вполне логично.
Также, можно попробовать скомпилировать брутфорсер с использованием пробной версии Intel C++ Compiler, который лучше всех оптимизирует код (при условии, что код компилируется под процессор Intel, конечно), но мне это не дало ощутимого прироста в производительности, поэтому я не буду приводить здесь замеры.
3. Задействуем GPU
Действительно, если у нас есть ещё один процессор (а точнее, аж 112 маленьких процессоров), который скучает без дела, так почему бы его не использовать? Для организации рассчётов на GPU существуют два решения: CUDA и BrookGPU, для видеокарт NVIDIA и AMD соответственно. Поскольку у нас есть только видеокарта от NVIDIA, будем использовать CUDA для вычисления md5-хешей на GPU.
Главная проблема здесь заключается в том, что под GPU используется совершенно другой принцип программирования и просто так организовать цикл, перебирающий все возможные пароли не получится, ибо у каждого потока есть свой таймаут, по истечении которого поток автоматически завершается.
Обойти это можно, если основной цикл вынести на CPU и там же заранее просчитывать возможные варианты пароля для каждого из потоков GPU, а на самом GPU уже считать по одному хешу на поток и сравнивать с исходным значением.
Попробуем это в действии:
~$ make PARAMS="-O3 -static -DTHREADS=2 -DUSEGPU"
~$ time ./brute 827ccb0eea8a706c4c34a16891f84e7b
...
real 0m1.967s
user 0m3.933s
sys 0m0.120s
Результатами совместных усилий CPU+GPU удалось достичь ускорения ещё в ~2 раза! Это уже вполне неплохие цифры, и, если набраться терпения, вполне реально находить пароли длиной 9 и больше символов, даже если алфавит включает в себя символы знаков препинания и другие языки.
P.S. Исходники, использованные в тестах, можно получить с помощью git:
git clone git://github.com/VladX/md5-bruteforcer.git
