LINUX.ORG.RU

Параллелизация John the Ripper с помощью OpenMP - поддержка bcrypt, SHA-crypt, SunMD5

 , , , ,


1

1

Вышла новая версия John the Ripper, программы для подбора/аудита Unix-паролей (и не только Unix) по их хешам, впервые с официальной поддержкой параллелизации, реализованной с помощью директив OpenMP (требуется GCC 4.2+, Sun Studio или другой компилятор с поддержкой OpenMP). На данном этапе, OpenMP поддерживается и эффективно работает для «медленных» типов хешей: OpenBSD-подобных на основе Blowfish (алгоритм bcrypt), glibc 2.7+ SHA-crypt, Solaris SunMD5. Для bcrypt используется оптимизированный код (на x86-64 вычисляет по два хеша параллельно на каждый поток). Для SHA-crypt и SunMD5 пока что используется системная функция crypt_r(3) на glibc или поддерживающая многопоточность crypt(3C) на Solaris (причем SHA-crypt там поддерживается тоже).

Эффективность этого подхода была проверена еще до релиза на 4- и 8-ядерных x86-64 и на UltraSPARC T2 (4 ядра, 32 потока). Для bcrypt, на 4-ядерных Core i7 и UltraSPARC T2 ускорение (по сравнению с одним процессом, не поддерживающим параллелизм) составило от 5.3 до 5.5 раз (оно превышает 4 раза благодаря SMT). На 8-ядерной системе (без SMT), ускорение составило 7.9 раза. Для SHA-crypt на Linux и Solaris и для SunMD5 на Solaris результаты чуть хуже - ускорение около 3.7 раз на 4-ядерных системах. Для обсуждаемых типов хешей и их типичных настроек (количество итераций, которое регулируется системным администратором) речь может идти об ускорении примерно с 200 до 700-1600 проверяемых комбинаций {пользователь, пароль} в секунду. Дальнейший параллелизм на несколько машин пока что может осуществляться по-старинке (вручную или с MPI).

Одно из основных преимуществ OpenMP-подхода: простота в сборке, установке и использовании программы. Причем использование ничем не отличается от традиционного, JtR работает как обычно (включая возможность прервать и продолжить работу с прежнего места), только быстрее. Один из основных недостатков - необходимость реализации поддержки для каждого типа хешей или интерфейса отдельно.

В будущих версиях JtR ожидается расширение поддержки параллелизма и на другие типы хешей - с использованием имеющегося в JtR оптимизированного кода.

>>> Анонс от Openwall

Давно пора на CUDA переписать

devl547 ★★★★★ ()
Ответ на: комментарий от devl547

(я не в теме) и что, оно станет работать ещё быстрее?

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

>оно станет работать ещё быстрее?

Если смогут его распаралелить на такое количество потоков

devl547 ★★★★★ ()
Ответ на: комментарий от devl547

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

Ramen ★★★★ ()
Ответ на: комментарий от yoghurt

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

По сравнению з многоядерным интелом можно ожидать x60-x1000 ускорения.

vertexua ★★★☆☆ ()
Ответ на: комментарий от Ramen

Если загрузишь видюху, то проц пускай просто покурит в сторонке.

vertexua ★★★☆☆ ()

>Параллелизация John the Ripper с помощью OpenMP

я понял для чего нужны облачные вычисления :) :) :)

tommy ★★★★ ()

Щасте читайтелей порножурнала «ксакеп»?

su ()
Ответ на: комментарий от devl547

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

drakmail ★★★★ ()
Ответ на: комментарий от drakmail

Чтобы было «в несколько раз быстрее» код должены быть адски непаралелельным.

vertexua ★★★☆☆ ()
Ответ на: комментарий от devl547

> Давно пора на CUDA переписать

Я ожидал, что один из первых комментариев будет о поддержке GPU. :-) Да, есть такие планы, но все еще лишь в теории. Сначала - лучшая поддержка многоядерных и многопроцессорных систем, что уже начато. Как бы GPU ни были быстрее, они все же есть и легко поддерживаются далеко не в каждой системе, на которой будет работать JtR в ближайшее время. Также, почему именно CUDA? Тут же попросят поддержать карточки ATI, которые нынче еще и быстрее, но требуют более специфичный код. С точки зрения рационального расхода времени на разработку (которого у меня, увы, очень мало), может быть смысл еще немного выждать (занимаясь другими направлениями и проектами), а затем реализовать поддержку OpenCL.

Наконец, когда речь зайдет не только о «медленных», но и о «быстрых» хешах, встанет вопрос выбора между эффективным порядком перебора по убыванию оценки вероятности (что лучше реализуется на CPU) и высокой скоростью проверки отдельных вариантов (что лучше реализуется на GPU). Реализовать и то и другое сложно - возможно, потребуется «гибридный» алгоритм (частично порядок перебора будет определяться вероятностями, а частично возможностями по быстрой проверке «похожих» вариантов). В итоге, с точки зрения успешного подбора паролей за единицу времени скорость возрастет не так сильно, как может показаться глядя лишь на количество проверок в секунду.

solardiz ()
Ответ на: комментарий от solardiz

Не надо выжидать - OpenCL работает уже сейчас прекрасно.

vertexua ★★★☆☆ ()

А я вот думаю, разве нельзя раз и навсегда сгенерить Rainbow-таблицы для хэшей и не насиловать процы да видюхи?

Sadler ★★★ ()

Глупый, может быть, вопрос, но сколько это в часах, днях, годах?

anonymous ()

Тыксц... Походу, в скором будущем, особенно после подключения видеокарт к подобным системам, мы все начнем переходить на какие-нибудь eToken и тому подбные аппаратные поделия с ключами в десятки килобит...

su ()
Ответ на: комментарий от Sadler

>А я вот думаю, разве нельзя раз и навсегда сгенерить Rainbow-таблицы для хэшей и не насиловать процы да видюхи?

Можно. А теперь подсчитай их обьем.

roller ★★★ ()

А когда риппера допилят что бы он юзал видеокарты для расчетов ?

anonizmus ()
Ответ на: комментарий от vertexua

> По сравнению з многоядерным интелом можно ожидать x60-x1000 ускорения.

Думаю, это преувеличение. На данный момент, если сравнивать с оптимальным кодом на CPU, ускорение будет порядка 10x-20x - это то, что мы видим в заслуживающих доверие тестах (от людей, кто оптимизировал один и тот же код и для CPU и для GPU, в том числе используя CPU+GPU одновременно), да и то в ряде случаев за это придется платить худшим порядком перебора. Допускаю, что со временем разрыв увеличится в пользу GPU, которые еще и окажутся интегрированы с CPU.

Некоторые публикуемые тесты, показывающие ускорение в 100 раз и т.п., используют сравнение с неоптимальными реализациями на CPU. «Честных» тестов с таким результатом я пока не видел.

Не надо выжидать - OpenCL работает уже сейчас прекрасно.

Может быть, я пока не пробовал. С радостью приму такой патч в contrib. Сам же пока планирую заниматься другими направлениями, как связанными с JtR так и нет. Кстати, нынешние/ближайшие шаги по параллелизации на CPU имеют отношение и к возможной будущей реализации для GPU - некоторые желательные переделки кода, который останется на CPU в обоих случаях, для этих задач общие.

solardiz ()

Даешь John the Ripper на MapReduce :)

AEP ★★★★★ ()

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

anonymous ()
Ответ на: комментарий от anonymous

> Вот на Хабре как раз была статья про OpenMP.

Ссылочка?

annoynimous ★★★★★ ()
Ответ на: комментарий от roller

> Можно. А теперь подсчитай их обьем.

Терабайтами уже никого не напугаешь. Один нормальный сервер с таблицами на пару десятков ТБ, в онлайне осуществляющий поиск по таблицам, и дело в шляпе. Тут даже salt не поможет.

Sadler ★★★ ()
Ответ на: комментарий от Sadler

> А я вот думаю, разве нельзя раз и навсегда сгенерить Rainbow-таблицы для хэшей и не насиловать процы да видюхи?

При грамотном использовании salt'ов на сервере, хеши паролей с которого проверяем - нельзя. А если с salt'ами там плохо - то это и надо в первую очередь исправлять (админу), а не заниматься выявлением слабых паролей.

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

solardiz ()
Ответ на: комментарий от anonymous

> Глупый, может быть, вопрос, но сколько это в часах, днях, годах?

Когда остановить проверку и решить, что оставшиеся пароли - достаточно хорошие - решать админу. Среди критериев - предполагаемые ресурсы при возможной атаке (сколько CPU-часов потратит «взломщик») и убывание количества успешных подборов за единицу времени. Например, за первый час может подобраться 10% от всех паролей, к концу первого дня 20%, к концу первой недели 25%, к концу первого месяца 27%. Сравнив 25% и 27% - довольно близкие числа - можно решить, что дальнейший подбор нерационален (еще один месяц, вероятно, приведет к успешному подбору не более 2% паролей). Подобные числа - реалистичны для хешей не-быстрого типа при отсутствии на сервере «серьезной» password policy во время установки паролей, выбираемых пользователями. При особо быстрых или особо медленных хешах, проблемах с генерацией salt'ов, другими ограничениями на выбор паролей числа могут быть совсем другими - встречается и 0%-1% (системы с bcrypt и passwdqc) и выше 90% (raw MD5 хеши с веб-сайтов).

solardiz ()
Ответ на: комментарий от vertexua

>если алгоритм распараллелить так, чтобы не было разного ветвления, а чистая математика
Ключевое слово здесь - если.

Ramen ★★★★ ()

>SunMD5
А чем оно от обычного MD5 отличается, кстати?

Ramen ★★★★ ()
Ответ на: комментарий от constRS

Спасибо, хотя сама статья ничего конкретного не предлагает. Мне лично OpenMP импонирует своей высокоуровневостью. Да, MPI — гибче, имеет более широкую область применения, но... это такой параллельный ассемблер, где нужно постоянно помнить об особенностях реализации, иметь дело с низкоуровневыми и железо-специфичными вещами. Это трудно, поскольку абстракция — мощное средство решения проблем. Впрочем, ладно, во-первых это тоже философия, во-вторых, оффтопик.

annoynimous ★★★★★ ()
Ответ на: комментарий от Ramen

SunMD5 - поделка Alec Muffett'а (автора Crack и сотрудника Sun). Включена в Solaris как пример использования нового framework'а. По сути SunMD5 ничем не лучше уже имевшегося на то время bcrypt, поддержка которого была включена в Solaris одновременно. Советую использовать bcrypt, а не SunMD5.

«Обычный» MD5 вообще не предназначен для хеширования паролей. Его непосредственное использование в таком качестве приводит к плачевным результатам. В то же время, на основе MD5 вполне можно построить отвечающий почти-современным требованиям метод хеширования паролей - добавив поддержку salt'ов и переменного количества итераций - что и сделано в SunMD5 (и еще кое-что лишнее). Получилось неплохо, но при наличии bcrypt было не нужно.

solardiz ()
Ответ на: комментарий от vertexua

> Ну как тебе сказать, если алгоритм распараллелить так, чтобы не было разного ветвления, а чистая математика, то хорошая видеокарта может выполнить до 32000 потоков абсолютно параллельно.

Давай считать, допустим, tesla имеет 30MP, каждый выполняет один warp = 32 треда, получается всего 30*32 = 960. Причем примерно 4такта на инструкцию, потому что каждый MP содержит всего 8 CUDA cores, а тредов 32.

frey ★★ ()
Ответ на: комментарий от solardiz

Ясно, спасибо.
А под «обычным» я имел в виду как раз солёный MD5. Не солёный MD5 для хранения паролей используется разве что только всякими унылыми форумными движками, CMS и иже с ним.

Ramen ★★★★ ()

Оно уже научилось с md5 искаропки работать? Или как обычно, нужно с патчами пересобирать?

xintrea ()

Зачем вообще нужны все эти OpenMP, MPI, если есть pthreads и обёртки над ними?

Legioner ★★★★★ ()
Ответ на: комментарий от xintrea

> Оно уже научилось с md5 искаропки работать? Или как обычно, нужно с патчами пересобирать?

Пока «как обычно» - четыре десятка дополнительных типов хешей и шифров, включая raw MD5, поддерживаются через jumbo patch. Этот патч уже длительное время я обновляю лично почти синхронно с выпуском новых релизов (сейчас есть версия 1.7.6-jumbo-2). Кому эта функциональность нужна - могут без проблем скачать два файла (.tar.gz и .diff.gz) и выполнить одну лишнюю команду (patch). У нас на wiki даже сказано как именно (для dummies).

Разумеется, это тоже одно из направлений для улучшений.

solardiz ()
Ответ на: комментарий от Legioner

> Зачем вообще нужны все эти OpenMP, MPI, если есть pthreads и обёртки над ними?

Точно так же можно спросить зачем нужны pthreads если есть OpenMP и MPI. Это три разные вещи, со своими особенностями. Правда, OpenMP зачастую реализуется как раз «поверх» pthreads, но программе этого «не видно». Получается та самая «обертка над pthreads».

solardiz ()
Ответ на: комментарий от Ramen

> солёный MD5

Это не конкретно. «Соленых MD5» есть «бесчисленное» количество разных. Из коробки, JtR поддерживает FreeBSD-подобный MD5-based crypt(3), который на данный момент также используется на многих/большинстве Linux-систем. В сравнении с ним, основное отличие SunMD5 - переменное количество итераций (в FreeBSD'шном их всегда 1000), по аналогии с bcrypt и позже реализованное также в SHA-crypt. (Есть и другие отличия. Поэтому «в лоб» сравнивать количества итераций там и там неправильно.) Это делает все три - bcrypt, SHA-crypt, SunMD5 - «медленными». (Насколько я знаю, впервые переменное количество итераций, кодируемое вместе с хешем, было реализовано в BSDI в районе 1993 года. Эти хеши JtR тоже поддерживает «из коробки».)

Многие другие варианты хешей на основе MD5 (и не только) поддерживаются в jumbo patch.

solardiz ()
Ответ на: комментарий от solardiz

А вот это тогда как называется?
$1$salt$md5sum(salt+password)
Где salt — 8 случайных цифробукв

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

> $1$salt$md5sum(salt+password)

Хеши, закодированные в строки такого вида, вычисляются иначе - после $1$salt$ находится не просто md5sum(salt+password), а результат вычисления некоторой более сложной функции на основе 1000 итераций MD5 от salt и password. С учетом этой поправки, это может называться «FreeBSD-подобным MD5-based crypt(3)» (см. мой комментарий выше), т.к. они впервые появились в FreeBSD (а затем в Linux и Cisco IOS). JtR их поддерживает «из коробки» с 1997 года, в выдаче их называет «FreeBSD MD5» (тем более что на момент реализации поддержки в JtR их можно было встретить только на FreeBSD).

solardiz ()
Ответ на: комментарий от Xenius

> А чем 1000 итераций md5sum лучше одной?

Тем, что медленнее - для проверки пароля системой (при «входе» в нее) - несущественно (и то и другое достаточно быстро), а для попытки подбора по хешу - существенно (перебор идет медленнее примерно в ту самую 1000 раз). Но 1000 уже стало маловато (при этом конкретном методе хеширования), поэтому хеши этого типа использовать не следует, а следует переходить на поддерживающие переменное количество итераций, которое можно будет постепенно увеличивать (для вновь устанавливаемых и изменяемых паролей). Три примера таких типов хешей - в заголовке новости. Советую bcrypt (из Linux'ов, он используется по умолчанию на Owl, ALT Linux, поддерживается SUSE Linux). Еще рекомендую почитать:

http://www.openwall.com/articles/PHP-Users-Passwords#password-hashing

(в контексте приложений на PHP, но почти то же самое относится и к системным паролям).

solardiz ()
Ответ на: комментарий от solardiz

А может просто лучше не давать взломщикам даже хешей?

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

> А может просто лучше не давать взломщикам даже хешей?

Лучше - и не давать и подстраховаться на случай утечки.

А возможностей для утечки много разных - это уязвимости в системе (приложения, OS), уязвимости других систем (бекапы, NAS, сервер аутентификации, сетевое оборудование и его настройка), утилизация или небезопасное хранение вышедших из строя, устаревших или ставших ненужными носителей информации, ошибочные действия сотрудников, намеренные действия бывших сотрудников, действия других посетителей ЦОД (злоупотребление физическим доступом), конфискация оборудования (и утечка из органов) и т.п.

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

solardiz ()
Ответ на: комментарий от solardiz

Heya!

Yeah, you've got it about right - aside from variable numbers of iterations, the other thing about SunMD5 was the arbitrary size of the salt, which could include the username and other material in order to guarantee uniqueness, and render rainbow tables a lot less effecctive :-)

- alec :-)

ps: i'm glad you're still doing this - it gives me hope for the future.

anonymous ()
Ответ на: комментарий от solardiz

Xenius> ....? solardiz> ...... Xenius> ....? solardiz> ...... Xenius> ....? solardiz> ......

И услышав это, Xenius достиг просветления.

anonymous ()

Теперь и для DES-based crypt(3)

Вот патч и тесты производительности при параллелизации bitslice DES в JtR, тоже с OpenMP-директивами:

http://www.openwall.com/lists/john-users/2010/06/27/1

Лучший результат - пока 17M c/s для традиционного crypt(3).

Под серверной загрузкой (даже всего лишь 10%), к сожалению, эффективность OpenMP-подхода для не-медленных хешей оказывается низка (о причинах см. по той же ссылке, выше). Так что этот новый патч - для использования на личных компьютерах или на простаивающих серверах.

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

solardiz ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.