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