Радужная таблица

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

Содержание

Теория

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

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

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

Таблицы могут взламывать только ту хеш-функцию, для которой они создавались, т.е. таблицы для MD5 могут взломать только хеш MD5. Теория данной технологии была разработана Philippe Oechslin [1] как быстрый вариант time-memory tradeoff [2]. Впервые технология использована в программе Ophcrack для взлома хешей LanMan, используемых в Windows. Позже была разработана более совершенная программа RainbowCrack которая может работать с большим количеством хешей, например LanMan, MD5, SHA1 и др.

Применение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. Philippe Oechslin
  2. [1] (PDF)

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home