Радужные таблицы в домашних условиях

[AndreyKu]

Автор, спасибо, конечно, за статью. За ваш ник только обидно, хоть и фамилия, но так расставлять акценты…

[arusakov]

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

[DnV]

Если продолжать так везде регистрироваться, то конечно не выкинешь.

[faiwer]

Никто не мешает отписать в администрацию сайта :)

[arusakov]

Злые вы, но уходить мне хочется)

[crizis]

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

[Azy]

Мешает архитектура хабра:

К сожалению, смена имени возможна только
у тех аккаунтов, от имени которых не было
написано постов или комментариев.

Это мне в саппорте ответили.

[ZeroOne_01]

Боже, хватит уже использовать этот «мем», пожалуйста.

[vyacheslav_ka]

Какой мем, вы о чем?

[LIR]

Жириновского. Да, немного надоел. Но пик прошел, очень редко теперь встретишь его.

[vyacheslav_ka]

Ну тогда я скажу «Боже, хватить использовать слова, значение которых вы не понимаете». ru.wikipedia.org/wiki/Мем

[LIR]

Хотя, что-то да, не то. Комикс это.

[ZeroOne_01]

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

К тому же я не просто так написал «мем» в кавычках.

[Regis]

На сленге это называется «макрос».

[horror_x]

Не путайте понятия: ru.wikipedia.org/wiki/Интернет-мем

[ZeroOne_01]

Я думал что тут только один обьект может вызывать схожесть с «мемом». Скажите честно, вы действительно не поняли что я имел ввиду?

[truezemez]

Несколько замечаний:
1. Вашу ф-цию addToDict можно заменить на range.
2. As of PHP 4.2.0, there is no need to seed the random number generator with srand() or mt_srand() as this is now done automatically.

[arusakov]

По первому пункту большое спасибо!
А насчет mt_srand — сама суть в том, что нам нужно инициализировать ГПСЧ предсказуемым образом и делать это многократно.

[truezemez]

Since 5.2.1 The Mersenne Twister implementation in PHP now uses a new seeding algorithm by Richard Wagner. Identical seeds no longer produce the same sequence of values they did in previous versions. This behavior is not expected to change again, but it is considered unsafe to rely upon it nonetheless.

[arusakov]

Я, кажется, понял, о чем речь. В руководстве речь идет о том, что при использовании нового PHP нельзя получить те же числа, что в предыдущих версиях, даже если инициализировать одними и теми же входными значениями.
Для проверки, можно выполнить код — pastebin.

[truezemez]

Вы оказались правы. Вот и комментарий увидел.

[justhack]

5.3.13 результат true

[truezemez]

function getWord($alphabet, $len) {
    shuffle($alphabet);
    return implode('', array_slice($alphabet, 0, $len));
}

[arusakov]

Отлично, а как заставить shuffle базироваться на mt_srand, а не на srand?

[truezemez]

Не знаю. Эта реализация, видимо, здесь не уместна.

[HomoErectus]

Озвучка Жирика бездарна.

[tassadar_ha]

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

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

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

И именно потому имеем в-третьих: те RT, которые можно скачать, создавались путем хеширования популярных паролей, а не рендомного перебора. Среди их есть очень качественные, которые включают в себя русские слова, набранные в английкой раскладке, слова с заменой a на @ и прочими стандартными хитростями.

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

[arusakov]

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

[tassadar_ha]

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

[AndryX]

Хочу добавить, что не имеет смысла генерировать случайные пароли, тогда уже просто лучше заполнить базу итеративным методом (имею ввиду a...a -> z...z). При этом хранить её можно в древе, для ускорения доступа.

P.S.: На PHP такие штуки не особо удобно писать, тк. здесь важна производительность.

[truezemez]

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

[ov7a]

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

[ShadowPrince]

Мда, где-то и мой там будет, хоть и не 6.

[roller]

Я только одного не понял, если пароль захеширован вместе с солью — вы и ее тоже перебираете?

[arusakov]

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

[ivan2kh]

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

[Sicness]

> Чем меньше входной алфавит, тем быстрее будет сгенерирована радужная таблица, но и паролей по заданным хэшам найдется меньше.
Я бы отметил еще и фактор объема полученных данных. А то помню таблицы по 100-200 ГБ и более…

[zim32]

Интересно на сколько быстрее будет реализация на с++ или java

[Yavanosta]

Если нужна скорость то погуглите реализацию на CUDA. Там какое-то бешеное число хэшей в секунду было.

[Riateche]

Вы сами написали, что MySQL не очень подходит для хранения радужных таблиц. Зачем вы тогда его использовали? Не проще ли записать результат в файлы?

[arusakov]

Я выбрал наиболее простые инструменты, чтобы написать быстрее и чтобы материал был наиболее понятен.
Как записывать в файлы — это пожалуй вопрос отдельной статьи. Если грубо записать все цепочки в несколько файлов, то в генерации прирост скорости будет, но поиск будет неадекватно долгим.

[Riateche]

В MySQL-базе без индекса поиск будет еще медленней. С индексом, наверное, будут медленно добавляться данные, да и места он будет занимать много.

[silentnuke]

я конечно дико извиняюсь, но что это за детские ошибки в циклах? приведу один пример, ибо такое не в одном месте.

define('WORD_LENGTH', 6); // длина паролей, для которых строится радужная таблица

for($i = 1; $i < WORD_LENGTH; ++$i) {
$word .= $ALPHABET[mt_rand(0, $LAST_SYMBOL)];
}
на выходе получаем длину 5, никак не 6.

[arusakov]

Посмотрите на строчку перед for, и сразу станет все понятно.

[vitalets]

чтобы единичка в цикле не смущала, я думаю более элегантно было бы так:

$word = '';
for($i = 0; $i < WORD_LENGTH; ++$i) {
     $word .= $ALPHABET[mt_rand(0, $LAST_SYMBOL)];
}

[silentnuke]

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

[varnav]

На дворе 2012 год, bcrypt для надёжного шифрования паролей появился 13 лет назад. Что заставляет хранить пароли в хешах?