Что такое радужные таблицы

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

Прошедшая неделя с точки зрения информационной безопасности выдалась исключительно «удачной»: то база хэшей 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)

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

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 всё-таки удалось решить.

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

• Информационная безопасность
• PHP

Password Recovery Software

04.10.2023
Reset Windows Password v13.2
A new feature for removing junk files and cleaning up registry files.

20.09.2023
Windows Password Recovery v15.3.0
Windows Credentials Explorer
05.06.2023
Reset Windows Password v13.1
Forensic tools to analyze Remote Desktop activity in Windows

Articles and video

You may find it helpful to read our articles on Windows security and password recovery examples. Video section contains a number of movies about our programs in action

Windows Password Recovery — создание простых радужных таблиц

Радужные таблицы — это специальные таблицы поиска, используемые для вскрытия паролей, преобразованных при помощи необратимых хэш функций. Примером таких паролей могут служить хэши пользователя (LM или NTLM) в операционной системе Windows.

В программе Windows Password Recovery реализован поиск паролей по радужным таблицам. Для его работы необходимо наличие таблиц, которые можно либо скачать из Интернета, либо создать самостоятельно при помощи инструмента для генерации RT таблиц.

Перед тем, как начать создание таблиц(ы), важно настроить соответствующие взаимосвязанные опции и найти их наилучшее соотношение. Для этого выберите один из двух алгоритмов (LM или NTLM) и допустимый набор символов. Естественно, чем шире диапазон символов, тем больше паролей будет найдено в атаке по таблицам, но тем больше времени понадобится на их создание и, возможно, тем большего размера они будут.

В поле ‘Min length‘ и ‘Max length‘ задается минимальная и максимальная длина пароля в таблицах поиска. LM пароль в Windows состоит из двух 7 символьных половинок, поэтому максимальная длина пароля при генерации LM таблиц не должна превышать 7 символов.

‘Chain Length‘ (длина цепочки) влияет на следующие параметры таблицы: вероятность нахождения пароля, время генерации таблицы и время подбора одного пароля во время атаки.

От количества цепочек (Chain count) зависит вероятность нахождения пароля, время генерации таблицы и ее размер.

В настоящее время инструмент генерации таблиц не поддерживает таблицы размером более 2 Гб, однако при создании больших таблиц можно увеличивать их количество (параметр ‘Table count‘).

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

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

Радужная атака

Радужная атака — это реализация метода Faster Cryptanalytic Time-Memory Trade-Off, разработанного доктором Филиппом Охслином. Идея состоит в том, чтобы заранее (только один раз) сгенерировать хеш-таблицы паролей, а в процессе аудита/восстановления искать хеш-значения в этих предварительно вычисленных таблицах. Этот процесс значительно сокращает необходимое время, особенно для сложных паролей. Из-за характера этой атаки некоторые пароли не могут быть восстановлены; однако вы можете использовать радужные таблицы с большой вероятностью успешного нахождения пароля.

Чтобы получить доступ к настройкам радужной атаки, переключите тип атаки на радужную (Rainbow) и щелкните вкладку радужной атаки (Rainbow attack). Нажмите кнопку «Список радужных таблиц» (Rainbow tables list) и найдите таблицы для дальнейшей атаки (вы можете добавить сразу несколько таблиц), вы можете удалять таблицы из списка и перемещать их вверх и вниз; по завершении нажмите «Закрыть» (Close) и приступайте к самой атаке.

Программа также поддерживает индексированные радужные таблицы, доступные по адресу http://www.freerainbowtables.com.

Чтобы создать свои собственные таблицы, нажмите кнопку «Сгенерировать таблицы» (Generate tables).

Тип хеша (Hash type)

Могут быть созданы хэш-таблицы LM и NTLM; см. О Windows паролях

Длина пароля (Password length)

Минимум и максимум; обычно от 1 до 7 (чтобы покрыть все пространство паролей для хэшей LM). Однако, если вы хотите проверять только 6-символьные пароли (и вторую половину паролей длиной от 8 до 15 символов), вы можете создать более эффективные и все же относительно небольшие таблицы для длины от 1 до 6.

Кодировка (Charset)

• буквенный (alpha): только заглавные буквы (26)

• буквенный-пробел (alpha-space): заглавные буквы плюс пробел (27)

• буквенно-цифровой (alpha-numeric): заглавные буквы плюс цифры (36)

• буквенно-числовой-пробел (alpha-numeric-space): заглавные буквы плюс цифры и пробел (37)

• буквенно-числовой-символьный14 (alpha-numeric-symbol14): заглавные буквы, цифры и 14 наиболее распространенных символов:! @ # $% ^ & * () -_ + = (50)

• буквенно-числовой-символьный14-пробел (alpha-numeric-symbol14-space): заглавные буквы, цифры, пробел и 14 наиболее распространенных символов:! @ # $% ^ & * () -_ + = (51)

• все (all): заглавные буквы, цифры и 32 печатных символа, включая пробел (69)

Длина цепи (Chain length)

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

Счетчик цепи (Chain count)

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

Количество таблиц и индексов (Number of tables and Indexes)

Количество таблиц для создания или индексы таблиц, если вы распределяете процесс создания таблиц по нескольким компьютерам. Чем больше у вас таблиц, тем выше вероятность успеха. Например, если одна таблица дает вероятность 60% (0,6), две таблицы дают 1 — (1 — 0,6) * (1 — 0,6) = 0,84 (84%). С тремя такими таблицами вероятность уже равна 1 — (1 — 0,6) ^ 3 = 0,936 (93,6%). Но, конечно, резко увеличивается в объеме и занятое таблицами пространство.

Папка вывода (Output folder)

Нажмите кнопку «Обзор» (Browse), чтобы выбрать папку для сохранения сгенерированных таблиц (перед запуском процесса создания убедитесь, что в ней достаточно свободного места).

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

Есть несколько стандартных конфигураций (для LM-хэша, длина от 1 до 7; время рассчитывается для процессора Pentium 4 3.0ГГц), которые вы можете использовать, например:

Радужные таблицы

Радужная таблица (англ. rainbow table ) — специальный вариант таблиц поиска (lookup table), использующий механизм уменьшения времени поиска за счет увеличения занимаемой памяти или time-memory tradeoff. Радужные таблицы используется для вскрытия паролей, преобразованных при помощи необратимой хеш-функции.

Теория

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

Для восстановления пароля данное значение хеш-функции подвергается функции редукции и ищется в таблице. Если не было найдено совпадения, то снова применяется хеш-функция и функция редукции. Данная операция продолжается, пока не будет найдено совпадение. После нахождения совпадения, цепочка содержащая его, восстанавливается для нахождения отброшенного значения, которое и будет искомым паролем.

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

Таблицы могут взламывать только ту хеш-функцию, для которой они создавались, то есть таблицы для [1] как быстрый вариант time-memory tradeoff [2] . Впервые технология использована в программе Ophcrack для взлома хешей LanMan, используемых в Microsoft Windows. Позже была разработана более совершенная программа MD5, SHA1 и др. Следующим шагом было создание программы The UDC, которая позволяет строить Hybrid Rainbow таблицы не по набору символов, а по набору словарей, что позволяет восстанавливать более длинные пароли (фактически неограниченной длины).

Применение

При генерации таблиц важно найти наилучшее соотношения взаимосвязанных параметров:

• вероятность нахождения пароля по полученным таблицам
• времени генерации таблиц
• время подбора пароля по таблицам
• занимаемое место

Вышеназванные параметры зависят от настроек заданных при генерации таблиц:

• допустимый набор символов
• длина пароля
• длина цепочки
• количество таблиц

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

Хотя применение радужных таблиц облегчает использование метода грубой силы (bruteforce) для подбора паролей, в некоторых случаях необходимые для их генерации/использования вычислительные мощности не позволяют одиночному пользователю достичь желаемых результатов за приемлемое время. К примеру для паролей длиной не более 8 символов, состоящих из букв, цифр и специальных символов !@#$%^&*()-_+= захешированных алгоритмом MD5 могут быть сгенерированы таблицы со следующими параметрами:

• длина цепочки 1400
• количество цепочек 50 000 000
• количество таблиц 800

При этом вероятность нахождения пароля с помощью данных таблиц составит 0.7542 (75.42 %), сами таблицы займут 596 Гб, генерация их на компьютере уровня Пентиум-3 1ГГц займёт 3 года а поиск 1 пароля по готовым таблицам не более 22 минут.

Однако процесс генерации таблиц возможно распараллелить, например расчёт одной таблицы с вышеприведёнными параметрами занимает примерно 33 часа. В таком случае если в нашем распоряжении есть 100 компьютеров, все таблицы можно сгенерировать через 11 суток.

Защита от радужных таблиц

Данные таблицы невозможно использовать против необратимых хеш-функций, которые включают salt («соль», или «затравка»). Например, рассмотрим следующую функцию для создания хеша от пароля:

хеш = MD5( пароль + соль ),

где + обозначает конкатенацию.

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

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

Использование

Практически все дистрибутивы ОС Unix, GNU/Linux и PHP используют простой хеш (обычно Microsoft Windows и Windows NT используют хеши LAN Manager и NT LAN Manager, которые также не используют соль, что делает их одними из самых популярных для создания радужных таблиц.

Примечания

1. ↑Philippe Oechslin
2. ↑Доклад Philippe Oechslin на конференции CRYPTO’03 (PDF)

Внешние ссылки

• Страница Ophcrack Оригинальная исследовательская работа с демонстрацией
• Проект RainbowCrack
• oxid.it Содержит winrtgen — графическую оболочку для rtgen (утилиты создания таблиц)
• взлом MD5 с помощью радужных таблиц
• rainbowcrack.com Распределенное создание таблиц
• Большие радужные таблицы от группы Shmoo Group, создателей AirSnort
• download Rainbow Tables
• Ultimate Distributed Cracker Взлом паролей с использование Гибридных Радужных Таблиц

Wikimedia Foundation . 2010 .

• Радуев С. Б.
• Радужный (ХМАО)