Использование нескольких потоков для взлома паролей

Question

Я сейчас работаю над научным выставочным проектом 10-го класса, и я как бы врезался в стену. Мой проект проверяет влияние параллелизма на эффективность перебора паролей md5. Я буду подсчитывать количество паролей / секунду, которое он тестирует, чтобы увидеть, насколько оно эффективно, используя 1, 4, 16, 32, 64, 128, 512 и 1024 потоков. Я не уверен, буду ли я использовать словарь для перебора или чисто перебор. Я полагаю, что словарь будет легче распараллелить; просто разделите список на равные части для каждого потока. Я еще не написал много кода; Я просто пытаюсь спланировать это прежде, чем я начну кодировать.

Мои вопросы:

• Является ли вычисление проверенных комбинаций паролей в секунду лучшим способом определения производительности на основе числа потоков?

• Словарь или чисто грубая сила? Если бы вы использовали чисто грубую силу, как бы вы разбили задачу на переменное количество потоков?

• Есть еще предложения?

Answer 1

Я не пытаюсь ослабить ваш энтузиазм, но это уже вполне понятная проблема. Я постараюсь объяснить, чего ожидать ниже. Но, возможно, было бы лучше сделать ваш проект в другой области. Как насчет «Максимизации пропускной способности хеширования MD5», тогда вы не ограничитесь только просмотром потоков.

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

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

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

Существует 2 класса вычислений: IO-привязанный и вычисляемый. Вычисления, связанные с вводом-выводом, могут потратить большое количество циклов ЦП в ожидании ответа от некоторого оборудования, такого как сетевая карта или жесткий диск. Из-за этих издержек вы можете увеличить количество потоков до точки, где ЦП снова будет максимально увеличен, и это может отменить стоимость переключения контекста. Однако существует ограничение на количество потоков, после которого переключение контекста займет больше времени, чем потоки блокируют для ввода-вывода.

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

C # ThreadPool уже позаботился обо всем этом за вас - вы просто добавляете задачи и ставите их в очередь, пока не станет доступен поток. Новые потоки создаются только тогда, когда поток заблокирован. Таким образом, переключение контекста сводится к минимуму.

У меня есть четырехъядерный компьютер - разбить проблему на 4 потока, каждый из которых выполняется на собственном ядре, будет более или менее быстро, так как моя машина может перебирать пароли.

Чтобы серьезно распараллелить эту проблему, вам понадобится много процессоров. Я читал о , использующем графический процессор для решения этой проблемы.

Есть анализ векторов атак, которые я записал здесь , если он вам нужен. Радужные таблицы и компромиссы между процессором и памятью были бы еще одной интересной областью для реализации проекта.

Answer 2

Чтобы ответить на ваш вопрос: 1) Нет лучшего способа проверить производительность потоков. Различные задачи по-разному масштабируются с потоками, в зависимости от того, насколько независима каждая операция в целевой задаче. Таким образом, вы можете попробовать словаре вещь. Но когда вы анализируете результаты, полученные результаты могут быть применимы не ко всем проблемам. Однако один очень популярный пример состоит в том, что люди пробуют общий счетчик, где счетчик увеличивается фиксированным числом раз для каждого потока.

2) Грубая сила охватит большое количество случаев. Фактически, грубой силой может быть бесконечное количество возможностей. Таким образом, вам может потребоваться ограничить ваш пароль некоторыми ограничениями, такими как максимальная длина пароля и так далее. Один из способов распределения грубой силы состоит в том, чтобы назначить каждому потоку разные начальные символы для пароля. Затем поток проверяет все возможные пароли для этого начального символа. Как только поток завершает свою работу, он получает еще один начальный символ, пока вы не используете все возможные начальные символы.

3) Одно из предложений, которое я хотел бы вам дать, - это протестировать немного меньшее количество потоков. Вы идете в 1024 темы. Это не очень хорошая идея. Количество ядер на машине обычно составляет от 4 до 10. Поэтому постарайтесь не превышать количество потоков на огромное количество, чем количество ядер. Потому что процессор не может запускать несколько потоков одновременно. Это один поток на процессор в любой момент времени. Вместо этого попытайтесь измерить производительность для разных схем назначения проблемы различным потокам.

Дайте мне знать, если это поможет!

Answer 3

Одним из решений, которое будет работать как для словаря, так и для грубой силы всех возможных паролей, является использование подхода, основанного на разделении работы на рабочие блоки.Иметь общий объект, отвечающий за разделение проблемного пространства на единицы работы - в идеале, около 100–5 секунд работы каждый - и указывать ссылку на этот объект для каждого потока, который вы запускаете.Затем каждый поток работает в цикле, подобном следующему:

for work_block in work_block_generator.get():
  for item in work_block:
    # Do work

Преимущество этого перед простым разделением всего рабочего пространства на один блок на поток заранее состоит в том, что если один поток работает быстрее, чем другие, он выигрываетне заканчивайте работу и просто бездействуйте - он будет собирать больше кусков.

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

Answer 4

Как в словарном, так и в грубом методах проблема заключается в смущающе параллельной . Чтобы разделить задачу о грубой силе с n нитями, просто скажем, первые две (или три) буквы («префикс») на n частей. Затем каждому потоку присваивается набор назначенных префиксов, например «aa - fz», где он отвечает только за тестирование всего, что следует за его префиксами.

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