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

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

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

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

function addToDict(&$alph, $beginSymbol, $endSymbol) {
    for($i = ord($beginSymbol), $n = ord($endSymbol); $i <= $n; ++$i) {
        $alph[] = chr($i);
    }
}

Тогда сам алфавит заполним следующим образом:

$ALPHABET = array();
addToDict($ALPHABET, 0, 9);
addToDict($ALPHABET, 'A', 'Z');
addToDict($ALPHABET, '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('CHINE_LENGTH', 1000);  // длина цепочки из хэшей и редукций
define('HASH_LAST_BITE', 15); // номер последнего байта хэша, начиная с 0 (для MD5 – 15)

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

$i = 0;
while($i < CHINE_LENGTH) {
    $positions = array(); 
    $positions[] = mt_rand(0, HASH_LAST_BITE);
    for($j = 1; $j < 4; ++$j) {
        do {
            $ind = mt_rand(0, HASH_LAST_BITE);
            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 % CHINE_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 getEndOfChine($word, $startStep = 0, $length = CHINE_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 getWordsInChine($hash) {
    $words = array(); // массив последних слов в цепочке для длины 100, 99, 98 и тд
    for($i = 0, $n = CHINE_LENGTH; $i < $n; ++$i) {
        $wordStart = reduction($hash, $i);
        $wordEnd = getEndOfChine($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 всё-таки удалось решить.

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

Автор: RusSuckOFF