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

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

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

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

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

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

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

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

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

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

Вот бы еще OpenCL....

Ммм, прикольно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://project-rainbowcrack.com/table.htm

кстати вот и таблицы

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

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

Ссылочка?

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

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

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

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

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

К.О.

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

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

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

> Ссылочка?

Я бы сказал, что это скорее философская статья и, в основном, не про OpenMP - http://habrahabr.ru/company/intel/blog/95992/#habracut

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

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

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

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

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

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

PoC для CUDA на расшифровку MD5:

http://www.openwall.com/lists/john-users/2008/06/02/3

Там же сорцы. Так что все реально.

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

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

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

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

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

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

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

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

> солёный 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.

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

> $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).

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

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

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

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

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

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

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

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

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

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

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.

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

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

Теперь и для 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-подходом (реакция на другую загрузку) гораздо менее выражена.