Быстрое восстановление пароля по MD5-хешу методом брутфорса

    Наверное каждый из нас хоть раз забывал пароль от какого-нибудь важного сайта, а потом пытался расшифровать его по сохранившимся кукам в браузере. Возможно это были даже не Ваши куки, но это не важно — если Вам интересна тема скоростного брутфорса, то добро пожаловать под кат!

    Сразу скажу, что описанные в статье техники ускорения подходят для любого алгоритма хеширования, но из-за широкой распространённости я выбрал именно 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
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 54

      +16
      Use the rainbow tables, Luke!
        +9
        Они офигенно полезны для расковыривания солёных хэшей, да.
          +9
          Ок, а расскажите в чём офигенная польза вот этого вот способа брута общего случая солёных хешей?
            +4
            Автор показал методы оптимизации полного перебора, не более того.
          0
          Не всегда приносит результат. Плюс, если хочется иметь свои таблицы, их тоже методом перебора нужно генерировать, от этого никуда не деться.
            +1
            Вечность назад использовал софт, генерирующий таблицы хэшей с помощью GPU.
          0
          1. Зашёл на сервис с радужными таблицами.
          2. Ввёл ваш хеш.
          3. ???
          4. Мгновенно получил пароль.
            +5
            Да, безусловно, первым делом это и нужно сделать. Но это не всегда помогает и пост не об этом.
              +1
              Я понимаю о чём пост, но брутфорсить каждый хеш… Зачем? Если вам это часто нужно, то постройте одну большую таблицу и используйте её.

              Кстати, сколько ваша программа генерирует хешей в секунду? Этот показатель намного адекватнее, чем скорость подбора взятого с потолка сверх-простого пароля.
                +5
                Мне не так часто приходится подбирать пароли, поэтому таблица мне не нужна. Я написал программу чисто из собственного интереса по оптимизации и достижении высокой скорости.
                А какой смысл в указании количества паролей в секунду? Железо у всех разное, а значит и скорость перебора у всех будет разная)
                  0
                  Потому вы должны указать железо (чтобы все могли оценивать его производительность) и количество хешей в секунду на нём. Желательно это всё повторить ещё на паре компьютеров.

                  Смысла в указании скорости подбора пароля 12345 намного меньше.
                    +2
                    Железо в посте указано. Чтобы добраться до 12345, нужно перебрать 31779653 возможных вариантов, т.е. скорость 31779653/1.967 = 16156407 паролей/сек.
                      +2
                      Оптимизация не удалась, 16 млн — маловато. Вот софт, который на 9800GX2 порядка одного миллиарда ключей в секунду генерирует.
                        +2
                        Попробовал эту штуку, правда для теста пришлось загрузить винду — нашёл 12345 за 1.2 сек. Впечатляет, но не на много быстрее, чем получилось у меня. Буду дальше оптимизировать, пока мне есть куда стремиться.
                          +3
                          Пароль слабый. Попробуйте на пароле в 8-9 символов. Разрыв должен сильно увеличиться.
                            +6
                            И почему вы берёте такие эталоны, мне не понять…
                              –29
                              Бедненький, пришлось винду загрузить.
                              Через пару лет, надеюсь, до тебя дойдет, что всё это только инструменты.
                                +19
                                Соль в том, что у человека на линуксе под себя настроено окружение, к которому он привык. В итоге при работе на другой системе возникает дискомфорт.
                                  0
                                  Уж как высокомерным тоном пользователям винды любят напоминать, что вообще-то существуют еще другие операционные системы.
                                  А тут вдруг что-то работает в винде и не работает в линуксе и «пришлось» его загружать. Впрочем… не вижу негатива в постах ни того ни другого… хз, зачем jack7277 заминусовали. НЛО? Хомячки?
                                  +12
                                  есть и следующий уровень понимания: когда уже давно дошло, что «все это инструменты», но тошнить от новых версий винды стало еще сильнее.
                                0
                                Может я что-то не понимаю, но на GT240 и Athlon x2 3800+ всего 325млн/с…
                                  –1
                                  Остальное железо не позволяет использовать всю мощь видеокарты.
                                  У меня было 350M/sec на 9600GT Athlon x2 4200+
                                    0
                                    То есть бутылочным горлышком является процессор, а у видеокарты еще запас?
                                    +1
                                    Это значит код кривой. Правильный код для CUDA не требует много процессора, там и на атоме можно гонять. В BarsWF — тоже кривоват, можно намного лучше.
                                    0
                                    Значит вы переплатили за видеокарту и сэкономили на остальном. Традиционно скорость системы определяется самым медленным её элементом.
                                      0
                                      Я не геймер, процессора хватает, видеокарта попала под плановый апгрейд.
                                        0
                                        Я говорил о том, что часть вашей системы не может работать на полную мощность. Например, видеокарту можно было взять значительно дешевле и результат был бы тот же.
                              +3
                              а ваши цифры у всех одинаковые? :)
                        +8
                        Посмотрите на open source (ныне) решение от BarsMonster. Это реально круто и есть чему приятно удивиться.
                          0
                          Спасибо за ссылку, интересное решение. Сейчас попробую замерить, кто быстрее :)
                            +1
                            Ну, что скажете? Только попробуйте не выложить результаты бенчмарка :)
                              +1
                              Проверил. Софт по вашей ссылке оказался шустрее, я сейчас изучаю его сорцы)
                            +1
                            Чёрт, пока искал ссылку в меня опередили :D.
                              +14
                              Черд, я знаменит :-D
                                +1
                                Пост про ядерные реакторы затмил все предыдущие заслуги :D.
                            +1
                            Кто-то ещё хеширует без соли?

                            Итак, используем Password-Based Key Derivation Function (хешируем 1000-XXXX раз пароль) с щипоткой соли и никакие rainbow tables не помогут, да и вообще перебор становится нерентабелен (если таки будут использоваться облака)
                              +1
                              Я хеширую SHA-512 с солью.
                                –2
                                Теоретически, коллизии никто не отменял.
                                  +1
                                  Коллизии это хорошо. Но например нашли мы пароль FJo34nML ввели на сайте. Так оно добавило соль и в md5 — с базой не сходится. Перебор невозможен никак. Вернее найденный ключ будет или коллизией, или с солью. Ни то, ни другое не подойдет, особенно если соль под 10 знаков, то с солью не найдешь.
                                    0
                                    Про коллизию вы правы, но про соль не соглашусь.

                                    Возможно я чего-то не понимаю, но в таком случае у атакующего будет на руках пароль с солью. Никто не сможет помешать ему удалить соль и авторизоваться на целевом сайте (длину можно угадать, вариантов не много). Ещё стоит учитывать, что для получившего доступ к базе злоумышленника достать соль к любому хешу — не проблема, а имея её на руках брутфорс будет проходить уже с заранее известной частью строки.

                                    Хеширование с солью несомненно прибавит сложности, но не сильно. Намного эффективнее против брутфорса хешировать пароль в разумное число раундов и использовать более современную хеш-функцию с длинным ключом.
                                      0
                                      Возможно я чего-то не понимаю, но в таком случае у атакующего будет на руках пароль с солью.

                                      Почему с солью-то? Может быть попалась коллизия и брутфорс нашел не пароль+соль, а просто дающую такой же хэш комбинацию символов? Фишка брутфорса MD5 ведь не в обратном вычислении пароля, а в поиске коллизии по сути.

                                      Потом смотря какая соль еще. Ведь можно просто делать конкатенацию, а можно наложить посимвольно XOR-ом, например.

                                      Вот представьте себе такую хэш-функцию:
                                      function hash($pwd)
                                      {
                                        return md5(xor_strings(md5($pwd), md5(SALT)));
                                      }


                                      допустим пароль 123

                                      вычислим хэш
                                      $pwd = '123'
                                      md5($pwd) = 'abc'
                                      SALT = 'sol'
                                      md5(SALT) = 'cbb'
                                      xor_strings(md5($pwd), md5(SALT)) = '~!#'
                                      md5(xor_strings(md5($pwd), md5(SALT))) = 'bca'


                                      Теперь мы брутфорсим пароль, зная хэш 'bca'.
                                      Допустим, мы вышли на коллизию '2' и md5('2') = 'bca'.

                                      Но, подставив, этот найденный пароль в хэш функцию, мы не получим искомый хэш: hash('2') ≠ 'bca', так как в процессе вычисления хэша еще идет xor-наложение md5-пароля с md5 соли, а затем еще берется md5 поверх xor-наложения.

                                      На примере все упрощено, но подставьте вместо пароля '123', например, пароль 'gH^b_#@1m8Hk!KmdPLgW3$fbf', вместо соли 'sol' — 'DFgs34FDGvhds!2dfgj$56fd', а вместо найденной коллизии '2', к примеру, 'R5%bd' :)
                                        0
                                        Вы не внимательно прочли мой предыдущий ответ, даже первую его строку.

                                        Я признал, что в случае обнаружения коллизии искать придётся дальше, но когда мы получаем явно настоящий пароль, то:
                                        1. Смотрим можно ли с базы достать ещё и соль. (Опять же, укравший базу получит и соль ко всем паролям, а алгоритм хеширования он знает изначально.)
                                        2. Смотрим визуально, можно ли отделить пароль от соли. (Если строки были конкатенированны, то чаще всего это сработает.)
                                        3. Имея на руках два расшифрованных хеша можно восстановить строку с солью. (Работает когда соль одна на всё приложение.)

                                        В вашем случае:
                                        1. Соль статическая и хешировать её не имеет смысла, её хеш всегда будет давать один результат. Его значение будет извлечено тем же XOR'ом на двух восстановленных ключах. (А если она не статическая, то попала бы ему в руки прямо с базы и второй хеш был бы вообще не нужен.)
                                        2. Вы уверены, что злоумышленник найдёт только коллизию, но чаще всего находят именно исходную строку.

                                        В итоге сложность взлом фактически усложнена расшифровкой в два раунда и гемором с изучением алгоритма хеширования в приложении.
                                          0
                                          А, понятно. Вы имеете ввиду, если все-таки перебор дойдет до истинного пароля.

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

                                          1. Про украденную базу по-моему никто не говорил. Говорили про брутфорс, а он осуществим и без воровства базы.
                                          2. Как можно визуально это определить? Ну как? Вот допустим алгоритм такой: md5(md5(salt).md5(pwd)) Как визуально можно определить?
                                          Конкатенация довольно часто применяется и я думаю зря. Лучше использовать более сложный алгоритм соления, вроде XOR или замешивание по принципу расчески.
                                          3. Имея два расшифрованных хэша — да, уже больше возможностей для извлечения соли, но опять-таки в случаях с примитивным наложением соли вроде простой конкатенации.

                                          Ну я привел простой пример, можно не одним XOR'ом, а допустим несколькими циклами переменного хэширования и наложения по XOR. Вообще вы говорите об интеллектуальном взломе, который по идее занимает достаточно долгое время и явно не отвечает теме топика о быстром восстановлении пароля.

                                          Кстати, ниже хорошую ссылку привели www.insidepro.com/eng/egb.shtml как видно переборщики используют самые частые методы соления и XOR-а там нет.

                                            0
                                            Поехали :).

                                            Про украденную базу по-моему никто не говорил. Говорили про брутфорс, а он осуществим и без воровства базы.

                                            Не осуществим, онлайн-брутфорс не будет работать через GPU, в нём скорость перебора слишком мала и средства защиты там другие. Фактически хакер как-то получил хеш, правильно? Логично предположить, что получил он с БД.

                                            Как можно визуально это определить? Ну как? Вот допустим алгоритм такой: md5(md5(salt).md5(pwd)) Как визуально можно определить?

                                            То, что противник всегда знает ваши алгоритмы нужно принимать как дефакто. Это одно с правил IT-безопасности.

                                            Вариантов определить есть куча, вы привели лишь один с них. Хеширование с солью на самом деле происходит по-разному и не в каждом случае реально угадать что именно там было.
                                            Обычно это делается методом тыка, те. я получил строку длинной в 64 символа и знаю, что там точно md5 замешан. Значит я разобью эти строки на две части и пущу в дальнейший брутфорс по-отдельности.

                                            Конкатенация довольно часто применяется и я думаю зря. Лучше использовать более сложный алгоритм соления, вроде XOR или замешивание по принципу расчески.

                                            Это безопасность через отсеивание ленивых. Фактически криптостойкость не увеличится, но некоторые на этом могут обломаться, да.

                                            Кстати, ниже хорошую ссылку привели www.insidepro.com/eng/egb.shtml как видно переборщики используют самые частые методы соления и XOR-а там нет.

                                            Кто-то мешает дописать один метод? :)

                                            Надо делать так:
                                            Md5(password+per_password_salt_100b+static_salt_100kb)
                                            Плюс — это конкатенация, password обрезать до 30 символов, на всякий случай.
                                            Быстрый поиск и все оптимизации сразу в помойку. Не алгоритм, а издевательство над взломщиком. ;)

                                            Так да. Но не проще ли сразу использовать нормальную хеш-функцию и всё? Ну зачем md5, зачем?)
                                              0
                                              Короче этой веткой мы хорошо облегчили кул-хацкерам дело)
                                                0
                                                Если они кул, то знают всё и без нас :D.
                                            0
                                            Надо делать так:
                                            Md5(password+per_password_salt_100b+static_salt_100kb)
                                            Плюс — это конкатенация, password обрезать до 30 символов, на всякий случай.
                                            Быстрый поиск и все оптимизации сразу в помойку. Не алгоритм, а издевательство над взломщиком. ;)
                                  +2
                                  Брук устарел, теперь же AtiSTREAM?
                                  +1
                                    0
                                    Вот ещё парочка брутфорсеров. Интересно, какой всё-таки самый быстрый.
                                    www.cryptohaze.com/multiforcer.php
                                    bvernoux.free.fr/md5/index.php
                                      –1
                                      Советую попробовать в исходнике указать для переменных подсказку register. Может это поможет. А может и нет. Честно не в курсе, насколько хорошо компиляторы умеют оптимизировать код.
                                      Ну и вообще — циклы разворачивать, переходить на ассемблер и т.д. Также есть всякие хаки связанные с предсказанием ветвления на процессорах и прочее. Оптимизацию зачастую можно сделать на пару порядков по отношению к неоптимизированному коду.
                                      Глобально по моему тут две темы:
                                      1. Оптимизация короткой программы (любой). Тема очень обширна.
                                      2. Оптимизация алгоритма. Возможно в этом направлении надо думать, хотя я не уверен.

                                      Only users with full accounts can post comments. Log in, please.