Атака методом перебора MD5 — эффективная многопоточная реализация

Подход, который я считаю достаточно гибким, заключается в создании потоков, выполняющих следующий код:

void thread_fn() {
    PASSWORD_BLOCK block;
    while (get_next_password_block(&block) {
        for (PASSWORD password in block) {
            if (verify_password(password)) set_password_found(password);
        }
    }
}

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

get_next_password_block() — это место, где выполняются все блокировки и синхронизация. Эта функция отвечает за отслеживание списка/диапазона паролей, увеличение пароля и т. д.

Зачем использовать PASSWORD_BLOCK, а не один пароль? Что ж, MD5 — очень быстрый алгоритм, поэтому, если мы будем вызывать get_next_password_block() для каждого пароля, то накладные расходы на блокировку/увеличение будут экстремальными. Кроме того, SIMD-инструкции позволяют нам выполнять массовые вычисления MD5 (4 пароля одновременно), поэтому нам нужен быстрый и эффективный способ получить значительную часть паролей, чтобы уменьшить накладные расходы.

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

«Правильный» способ сделать это - иметь пул рабочих (равный количеству ядер ЦП, либо не считая ядер гиперпотока, либо считая их все как «одно») и незаблокированную очередь FIFO, в которую вы отправляете группы из ста тысяч или около того задач. Это дает приемлемый баланс между накладными расходами на синхронизацию и балансировкой нагрузки.
Хитрость заключается в том, чтобы разделить работу на относительно небольшие группы, чтобы время, когда только один поток выполняет последнюю группу, было не слишком долгим (никакого параллелизма!), но в то же время не делайте группы слишком маленькими, чтобы вы были связаны синхронизацией/конкуренцией за шину. MD5 довольно быстр, поэтому от нескольких десятков до сотен тысяч рабочих элементов должно хватить.

Однако, учитывая конкретную проблему, это на самом деле излишество. Слишком сложно.

5-буквенных паролей в 26 раз больше, чем 4-буквенных, 6-буквенных паролей в 26 раз больше, чем 5-буквенных, и так далее. Другими словами, самый длинный пароль имеет значительно наибольшую долю в общем количестве комбинаций. Все 4,5,6-значные комбинации вместе составляют только около 3,9% комбинаций всех 7-значных комбинаций. Другими словами, они совершенно ничтожны. 96% всего времени выполнения находится в пределах 7-значных комбинаций, независимо от того, что вы делаете с остальными. Это еще более экстремально, если вы рассматриваете буквы и цифры или заглавные буквы.

Таким образом, вы можете просто запустить столько потоков, сколько у вас ядер процессора, и запускать все 4-значные комбинации в одном потоке, все 5-значные комбинации в другом и так далее. Это не очень хорошо, но этого достаточно, поскольку никто все равно не заметит разницы.
Затем просто разбейте возможные 7-значные комбинации на num_thread диапазонов одинакового размера, и пусть каждый поток, закончивший свой начальный диапазон, продолжит работу с этим. один.
Работа не всегда будет идеально сбалансирована, но так будет в течение 96% времени выполнения. И он работает с абсолютным минимумом управления задачами (нет) и синхронизации (нужно просто установить глобальный флаг для выхода при обнаружении совпадения).

Поскольку вы не можете ожидать идеальной балансировки нагрузки, даже если вы выполняете идеальное и правильное планирование задач (поскольку планирование потоков находится в руках операционной системы, а не ваших), это должно быть очень близко к «идеальному» подходу.

В качестве альтернативы вы можете рассмотреть возможность запуска одного дополнительного потока, который выполняет весь диапазон комбинаций, кроме самого длинного («незначительные 3%), и разделяет остальные поровну. Это вызовет несколько дополнительных переключений контекста во время запуска, но, с другой стороны, сделает логику программы еще проще.

Ручное разделение задачи на рабочие потоки неэффективно с обеих точек зрения: с точки зрения затраченных усилий и полученного баланса нагрузки. Современные процессоры и операционные системы усугубляют дисбаланс даже в том, что на первый взгляд кажется очень сбалансированной рабочей нагрузкой из-за:

• промахи кеша: один поток может попасть в кеш, другой может пострадать от промаха кеша, тратя до тысяч циклов на операцию загрузки памяти, где одна и та же загрузка может быть выполнена за несколько циклов.
• Турбо-ускорение, управление питанием, основные функции парковки. Как сам процессор, так и ОС могут управлять частотой и доступностью вычислительных блоков, способствующих дисбалансу.
• Вытеснение потока: в современных многозадачных операционных системах запущены другие процессы, которые могут временно прерывать выполнение потока.

Современные алгоритмы планирования перехвата работы весьма эффективны в сопоставлении и распределении нагрузки даже несбалансированной работы с рабочими потоками: вы просто описываете, где у вас есть потенциальный параллелизм, и планировщик задач назначает его доступным ресурсам. Кража работы — это распределенный подход, который не включает одно общее состояние (например, итератор) и, следовательно, не имеет узких мест.

Проверьте cilk, tbb или ppl для получения дополнительной информации о реализации таких алгоритмов планирования. Более того, они дружелюбны к вложенным и рекурсивным параллельным конструкциям, таким как:

void check_from(std::string pass) {
    check_password(pass);
    if(pass.size() < MAX_SIZE)
        cilk_for(int i = 0; i < syms; i++)
            check_from(pass+sym[i]);
}