_ RU.LINUX (2:5077/15.22) ___________________________________________ RU.LINUX _
From : Solar Designer 2:5020/400 Thu 10 Sep 98 02:09
Subj : Re: паpоли
________________________________________________________________________________
From: Solar Designer <solar@cannabis.dataforce.net>
Alex Korchmar <alx@corbina.net> wrote:
> прав именно BT. John ничего не "дешифрует" - это заняло бы не 30 часов,
Э... полностью никто не прав. ;-) BT сказал, что невозможно узнать именно
этот ли пароль был придуман юзером -- это не так в _примерно_ 255 из 256
случаев -- теоретически можно перебрать весь keyspace, и убедиться, что
мы получаем только одно совпадение хеша. (Числа "255 из 256" верны для
стандартного DES-based crypt(3), а, разумеется, не для чего угодно.)
> а несколько лет. Он просто использует тот факт, что функция шифрования
> выполняется очень быстро (особенно если слегка пересмотреть обычный алгоритм
> на тему оптимизации именно под повторяющиеся шифрования с одним и
> тем же salt) и просто шифрует произвольные (и не очень произвольные :)
> строки до тех пор, пока одна из них не совпадет. Именно по этой причине
Ключевое слово: "не очень произвольные". Вернее, в определенном порядке.
> полезно использовать пароли длинее восьми символов, даже несмотря на то,
> что md5 вычисляется еще быстрее, чем des.
Hу, насчет "MD5 быстрее DES" вопрос весьма спорный (смотря что именно ты
имел ввиду), но то, что количество реальной информации в пароле важнее,
чем способ хеширования, это верно. Hапример, мы можем замедлить хеш где-то
в миллион раз. Hо это равносильно добавлению только 20 бит информации
к паролю (разумеется, при отсутствии какой-либо закономерности среди этих
битов, иначе их надо будет больше 20). Впрочем, запомнить даже 48 бит уже
бывает довольно сложно для многих юзеров (это _не_ равно слову из 7 букв;
это может быть, например, фраза из 4 слов _случайно_ выбранных из списка
в 4096, причем "случайно" в криптографическом смысле). Поэтому и всякие
замедления (а миллион раз -- реально) очень даже полезны, как дополнительный
уровень защиты. Кстати, и не только для login паролей, но и, например, в
программах шифрования файлов -- да хоть в том же PGP.
> P.S. а вот алгоритм IDEA, похоже, такой оптимизации не поддается. openbsd'шные
Еще раз: быстродействие реализаций crypt(3) имеет очень мало общего с
быстродействием block ciphers, etc. положенных в основу.
> пароли john пока подбирать не умеет. (а зря)
1. Уже пол года как умеет.
2. IDEA там даже и не пахнет, там Blowfish. Да и то не столько (по времени)
шифрование, сколько key setup, загнанный в цикл.
По сути дела (оптимизации) -- какой "такой" он не поддается? Если говорить
вообще об соотношении быстродействия между оптимально оптимизированными
реализациями password validation и password cracking -- то поддается, это
отношение не равно единице. Если говорить про вынос установки salt'а за
цикл, то, хоть это у меня и сделано уже по аналогии, оно для хороших
реализаций crypt(3) почти ничего не дает, т.к. установка salt'а требует
мало времени по сравнению с собственно хешированием пароля (время на
которое искусственно приравнивается, например, к 0.1 секунды через
variable iteration count -- что есть в OpenBSD и BSDI... ну и у некоторых
из нас на Linux'ах;-).
А так, в случае password cracking, но _не_ password validation, возможны
следующие оптимизации:
1. Всякие выносы за цикл. Что-то дает только для стандартного DES-based.
2. Bitslice.
3. Другие варианты SIMD, вроде использования MMX для MD5.
4. Перемешивание команд от разных "вызовов" crypt(3) для улучшения
instruction-level parallelism'а и покрывания latencies. Конкретно,
должно дать ускорение (иногда в разы) для MD5 и Blowfish на Alpha
(где сейчас все, кроме DES, сравнительно медленно).
Пока у меня сделано только #1 и #2. Hу и просто оптимизация кода и
алгоритма для каждого конкретного случая.
P.S. Извини, что я все в таком несогласном тоне -- просто когда на этом
деле собаку съел ;-) -- уже каждая мелочь кажется важной. ;-) Хотя для
дискуссии в ru.linux было бы все равно.
Вот блин вы даете. По такому случаю такие дебаты!
Есть такой интересный man как
man crypt
---------
и почитайте на досуге кто не знает, чтобы не вводить в заблуждение других.
Там сказано и про salt и про key и про то, как кодируется и что вашим
паролем и по какому алгоритму, хотя это и не соответствует на 100% всем
системам, но это те основы, которые надо знать для представления себе.
И кодируется ключем не строка пробелов, а строка нулей.
А для лучшего представления как на самом деле - лезьте в исходники и
смотрите. Hапример в исходниках adduser-а можно увидеть как назначается
salt, надо сказать, что эти 2 байта зависят от времени (если я правильно
помню). И Эти salt-ы остаются неизменными атрибутами зашифрованной строки
в /etc/passwd или /etc/shadow....
to BT: Удивительно не услышать от тебя любимый тобой ответ man (в данном
случае crypt) :) Сразу меньше вопросов было бы. Чего разжевывать,
когда уже давно разжевано.
ps: только не придирайтесь к написанному мной выше, мол этот man не
соответствует тем или иным системам или алгоритм шифрования не DES 56битный,
в этом мане кратко изложен принцип.
--
--------------------* UNIX is Live Forever *-----------------
Michael I. Morozov MickeyICE powered by Linux
Moscow, Russia Fido: Michael Morozov 2:5020/954.20
--- ifmail v.2.9.os
* Origin: UNIX DarkWorld (2:5020/954.20)
Vova
