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



Прошедшая неделя с точки зрения информационной безопасности выдалась исключительно «удачной»: то база хэшей LinkedIn утекла в сеть, то хэши last.fm. И во всех обсуждениях, так или иначе, упоминают о радужных таблицах.
Слышали о них почти все, но делали их своими руками очень немногие.

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

Интеллектуального прорыва в области радужных таблиц сегодня не планируется, а есть желание рассказать, что радужные таблицы – это не сложно, поэтому и писать будем на чем-то простом, а именно: PHP. Хранить таблицу в MySQL.

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

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

$ALPHABET = array_merge(range(0, 9), range('A', 'Z'), range('a', 'z'));
$LAST_SYMBOL = count($ALPHABET) - 1; // индекс последнего доступного символа


Для создания радужной таблицы используются цепочки, начало которых – это некоторый случайный пароль фиксированной длины. Очевидно, необходима функция генерация случайных паролей из символов входного алфавита:

define('WORD_LENGTH', 6);  // длина паролей, для которых строится радужная таблица
function getWord($newRandom = false) {
    global $ALPHABET, $LAST_SYMBOL;
    
    if($newRandom) {
        mt_srand();
    }
    
    $word = $ALPHABET[mt_rand(0, $LAST_SYMBOL)];
    for($i = 1; $i < WORD_LENGTH; ++$i) {
        $word .= $ALPHABET[mt_rand(0, $LAST_SYMBOL)];
    }
    return $word;
}


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

Конечно, можно было бы написать две-три функции редукции самостоятельно, но не в случае, когда длина цепочки равна 100 или 1000. Тем более, хотелось бы, чтобы длина цепочки хранилось в константе, которую можно заменить легким движением руки.

В голову приходить достаточно очевидное решение: нужно использовать Генератор псевдослучайных чисел (ГПСЧ). Для каждой конкретно взятой функции редукции инициализировать ГПСЧ определенным набором бит из хэша, поступающего на вход, а затем получать пароль с помощью вызова getWord().

В принципе действовать на уровне отдельных бит и не требуется. Инициализировать ГПСЧ нужно числом типа int, для моей платформы – это 32 бита или 4 байта. MD5 состоит из 16 байт (посмотрите на второй параметры у функции md5 в PHP), тогда количество возможных размещений равно 16! / (16 — 4)! = 43680 – даже для длины цепочки в 1000 хватит с запасом.

Сказано – сделано:

define('CHAIN_LENGTH', 1000);  // длина цепочки из хэшей и редукций
define('HASH_LAST_BYTE', 15); // номер последнего байта хэша, начиная с 0 (для MD5 – 15)

$reductions = array(); // массив, определяющий какие байты хэша для конкретной редукции нужны
mt_srand(CHAIN_LENGTH); // инициализируем генератор фиксированной величиной, чтобы от запуска к запуску при одной и той же длине цепочки функции редукции не менялись

$i = 0;
while($i < CHAIN_LENGTH) {
    $positions = array(); 
    $positions[] = mt_rand(0, HASH_LAST_BYTE);
    for($j = 1; $j < 4; ++$j) {
        do {
            $ind = mt_rand(0, HASH_LAST_BYTE);
            if(!in_array($ind, $positions)) {
                $positions[] = $ind;
                break;
            }
        }
        while(true);
    }
    if(!in_array($positions, $reductions)) {  // все редукции различны
        $reductions[] = $positions;
        ++$i;
    }
}


Тогда собственно функция редукции, принимающая на вход хэш и номер текущего шага в цепочке, будет иметь вид:

function reduction($hash, $step) {
    global $reductions;
    $pos = $reductions[$step % CHAIN_LENGTH];
    
    mt_srand(ord($hash[$pos[0]]) | ord($hash[$pos[1]]) << 8 | ord($hash[$pos[2]]) << 16 | ord($hash[$pos[3]]) << 24);   
    return getWord();
}


С учетом всего вышеописанного функция расчета конца цепочки по ее началу тривиальна:

function getEndOfChain($word, $startStep = 0, $length = CHAIN_LENGTH) {
    for($i = $startStep; $i < $length; ++$i) {
        $hash = md5($word, true);
        $word = reduction($hash, $i);
    }
    return $word;    
}


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

В классическом варианте берется последняя n-ая функция редукции от хэша и получившийся пароль ищется в радужной таблице, если ничего не нашлось, берется n-1 редукция, потом вычисляется хэш, потом n-ая редукция и ищется в таблице и так далее, пока не найдется пароль. При использовании MySQL это могло бы вылиться в n однотипных SELECT-ов (в худшем случае) – даже начинающий веб-программист знает, что за это можно и по рукам получить! Конечно же, достаточно одного SELECT-а для поиска одного пароля, но для этого необходимо генерировать все пароли для поиска разом:

function getWordsInChain($hash) {
    $words = array(); // массив последних слов в цепочке для длины 100, 99, 98 и тд
    for($i = 0, $n = CHAIN_LENGTH; $i < $n; ++$i) {
        $wordStart = reduction($hash, $i);
        $wordEnd = getEndOfChain($wordStart, $i + 1);
        $words[] = $wordEnd;
    }
    return $words;   
}


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

И напоследок ложка дегтя. PHP и MySQL прекрасно справляются с созданием прототипов на скорую руку, но PHP действительно не самый быстрый язык и хранение радужной таблицы в реляционной СУБД общего назначения не самое эффективное решение. Радужную таблицу для MD5 для 6-символьных паролей с длиной цепочки 1000 из 2 миллионов записей ноутбук на базе i3-330UM генерировал более 8 часов. В идеале полученная таблица может обратить 2*10^9 хэшей, но это число не соизмеримо с общим количеством 6-символьных паролей, которых 56,8*10^9 на выбранном входном алфавите.

Это в очередной раз показывает, насколько важен выбор подходящего инструмента для решения конкретной задачи.
Думаю, что задачу наглядно продемонстрировать принцип реализации радужных таблиц мне на пару с PHP всё-таки удалось решить.

Спасибо за внимание.
Share post

Comments 47

    +5
    Автор, спасибо, конечно, за статью. За ваш ник только обидно, хоть и фамилия, но так расставлять акценты…
      +5
      Придумал мне его друг в школе — давно это было, а тогда переводили мы его в более приятном свете. Теперь английским владею лучше, а уже «из песни слов не выкинешь».
        +30
        Если продолжать так везде регистрироваться, то конечно не выкинешь.
          0
          Никто не мешает отписать в администрацию сайта :)
            +5
            Злые вы, но уходить мне хочется)
              0
              Написать-то можно, только вот помочь они не смогут. Я тоже хотел как–то сменить ник здесь, но служба поддержки прислала отказ, сославшись на техническую невозможность данной операции.
                0
                Мешает архитектура хабра:
                К сожалению, смена имени возможна только
                у тех аккаунтов, от имени которых не было
                написано постов или комментариев.

                Это мне в саппорте ответили.
            –1
            Боже, хватит уже использовать этот «мем», пожалуйста.
              0
              Какой мем, вы о чем?
                0
                Жириновского. Да, немного надоел. Но пик прошел, очень редко теперь встретишь его.
                  +4
                  Ну тогда я скажу «Боже, хватить использовать слова, значение которых вы не понимаете». ru.wikipedia.org/wiki/Мем
                    +2
                    Хотя, что-то да, не то. Комикс это.
                      +4
                      Извините конечно, но то, что это комикс, не мешает ему быть «единицей передачи культурной информации, распространяемая от одного человека к другому посредством имитации, научения и др».

                      К тому же я не просто так написал «мем» в кавычках.
                        0
                        На сленге это называется «макрос».
                        +5
                        Не путайте понятия: ru.wikipedia.org/wiki/Интернет-мем
                      –1
                      Я думал что тут только один обьект может вызывать схожесть с «мемом». Скажите честно, вы действительно не поняли что я имел ввиду?
                    +1
                    Несколько замечаний:
                    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.
                      +1
                      По первому пункту большое спасибо!
                      А насчет mt_srand — сама суть в том, что нам нужно инициализировать ГПСЧ предсказуемым образом и делать это многократно.
                        0
                        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.
                          +1
                          Я, кажется, понял, о чем речь. В руководстве речь идет о том, что при использовании нового PHP нельзя получить те же числа, что в предыдущих версиях, даже если инициализировать одними и теми же входными значениями.
                          Для проверки, можно выполнить код — pastebin.
                    0
                    function getWord($alphabet, $len) {
                        shuffle($alphabet);
                        return implode('', array_slice($alphabet, 0, $len));
                    }
                    
                      0
                      Отлично, а как заставить shuffle базироваться на mt_srand, а не на srand?
                        0
                        Не знаю. Эта реализация, видимо, здесь не уместна.
                      –1
                      Озвучка Жирика бездарна.
                        +8
                        Какой-то странный подход. Я бы сказал первым делом вроде как в случае с библиотеками для шифрования: не создавайте радужные таблицы (далее — RT) самостоятельно, разве что вы точно знаете, зачем вы это делаете.

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

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

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

                        Шанс на успех с такими, уже заготовленным таблицами, намного выше, чем с рендомным перебором.
                          0
                          Все хорошо говорите.
                          Да, подбор по словарю с точки зрения этих критериев (как можно больше, как можно быстрее) более эффективен.
                          Но никто не отменял исключительно учебные цели.
                          Мое лично убеждение заключается в том, что на голых книжных знаниях далеко не пойдешь. Нужно постоянно пробовать новое, изобретать, стараться что-то реализовывать самому. В процессе создания появляются трудности, и только в момент их преодоления ты действительно растешь как личность, растут твои профессиональные качества.
                            0
                            Не спорю, но только обращаю внимание читателей, что создание собственной таблицы на основании перебора не имеет ровно никакой практический ценности, и может служить разве что в учебных целях.
                            +1
                            Хочу добавить, что не имеет смысла генерировать случайные пароли, тогда уже просто лучше заполнить базу итеративным методом (имею ввиду a...a -> z...z). При этом хранить её можно в древе, для ускорения доступа.

                            P.S.: На PHP такие штуки не особо удобно писать, тк. здесь важна производительность.
                            +3
                            Запутано все как-то с этими радужными таблицами. Если бы я ради фана подбирал пароли, то я бы качнул словарь побольше, записал бы хеш каждого слова и само слово в таблицу бд и сделал бы джоин с «угнаной» таблицей.
                              0
                              Проблема в памяти будет. Радужная таблица позволяет существенно сэкономить место. Кроме того, помимо словарных паролей, с помощью различных функций редукции можно получить и несловарные пароли «в подарок».
                              0
                              Мда, где-то и мой там будет, хоть и не 6.
                                0
                                Я только одного не понял, если пароль захеширован вместе с солью — вы и ее тоже перебираете?
                                  0
                                  Уникальная для каждого пароля соль — очень простой и эффективный метод борьбы против подбора с помощью радужных таблиц. Она увеличивает длину входных пароля, и создание радужной таблицы под пароли такой длины становиться практически нереально задачей (в наше время по крайней мере).
                                    0
                                    Не так. Сложность создания радужной таблицы та же.
                                    Не имеет смысла использовать радужную таблицу когда нужно подобрать только один пароль (в данном случае).
                                  0
                                  > Чем меньше входной алфавит, тем быстрее будет сгенерирована радужная таблица, но и паролей по заданным хэшам найдется меньше.
                                  Я бы отметил еще и фактор объема полученных данных. А то помню таблицы по 100-200 ГБ и более…
                                    +1
                                    Интересно на сколько быстрее будет реализация на с++ или java
                                      +3
                                      Если нужна скорость то погуглите реализацию на CUDA. Там какое-то бешеное число хэшей в секунду было.
                                      +2
                                      Вы сами написали, что MySQL не очень подходит для хранения радужных таблиц. Зачем вы тогда его использовали? Не проще ли записать результат в файлы?
                                        –2
                                        Я выбрал наиболее простые инструменты, чтобы написать быстрее и чтобы материал был наиболее понятен.
                                        Как записывать в файлы — это пожалуй вопрос отдельной статьи. Если грубо записать все цепочки в несколько файлов, то в генерации прирост скорости будет, но поиск будет неадекватно долгим.
                                          0
                                          В MySQL-базе без индекса поиск будет еще медленней. С индексом, наверное, будут медленно добавляться данные, да и места он будет занимать много.
                                          –2
                                          я конечно дико извиняюсь, но что это за детские ошибки в циклах? приведу один пример, ибо такое не в одном месте.

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

                                          for($i = 1; $i < WORD_LENGTH; ++$i) {
                                          $word .= $ALPHABET[mt_rand(0, $LAST_SYMBOL)];
                                          }
                                          на выходе получаем длину 5, никак не 6.
                                            0
                                            Посмотрите на строчку перед for, и сразу станет все понятно.
                                              0
                                              чтобы единичка в цикле не смущала, я думаю более элегантно было бы так:
                                              $word = '';
                                              for($i = 0; $i < WORD_LENGTH; ++$i) {
                                                   $word .= $ALPHABET[mt_rand(0, $LAST_SYMBOL)];
                                              }
                                              
                                                0
                                                ох ты ж ежик и в правду, надо больше спать. извиняюсь.)
                                              0
                                              На дворе 2012 год, bcrypt для надёжного шифрования паролей появился 13 лет назад. Что заставляет хранить пароли в хешах?

                                              Only users with full accounts can post comments. Log in, please.