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

Схема упрощенной радужной таблицы с длиной цепочек равной трем. R1 R2 R3 - функции редукции, H - функция хеширования.

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

Предпосылки к появлению

Компьютерные системы, которые используют пароли для аутентификации, должны каким-то образом определять правильность введенного пароля. Самым простым способом решения данной проблемы является хранение списка всех допустимых паролей для каждого пользователя. Минусом данного метода является то, что в случае несанкционированного доступа к списку злоумышленник узнает все пользовательские пароли. Более распространенный подход заключается в хранении значений криптографической хеш-функции от парольной фразы. Однако большинство хешей быстро вычисляются, поэтому злоумышленник, получивший доступ к хешам, может быстро проверить список возможных паролей на валидность. Чтобы избежать этого, нужно использовать более длинные пароли, тем самым увеличивая список паролей, которые должен проверить злоумышленник. Для простых паролей, не содержащих соль, взломщик может заранее подсчитать значения хешей для всех распространенных и коротких паролей и сохранить их в таблице. Теперь можно быстро найти совпадение в заранее полученной таблице. Но чем длиннее пароль, тем больше таблица, и необходимо больше памяти для её хранения. Альтернативным вариантом является хранение только первых элементов цепочек хэшей. Это потребует больше вычислений для поиска пароля, но значительно уменьшит количество требуемой памяти. А радужные таблицы являются улучшенным вариантом данного метода, которые позволяют избежать коллизий.

Теория

Радужная таблица создается построением цепочек возможных паролей. Каждая цепочка начинается со случайного возможного пароля, затем подвергается действию хеш-функции и функции редукции. Данная функция преобразует результат хеш-функции в некоторый возможный пароль (например, если мы предполагаем, что пароль имеет длину 64 бита, то функцией редукции может быть взятие первых 64 бит хеша, побитовое сложение всех 64-битных блоков хеша и т. п.). Промежуточные пароли в цепочке отбрасываются и в таблицу записываются только первый и последний элементы цепочек. Создание таких таблиц требует больше времени, чем нужно для создания обычных таблиц поиска, но значительно меньше памяти (вплоть до сотен гигабайт, при объёме для обычных таблиц в N слов для радужных нужно всего порядка N^2/3). При этом они требуют хоть и больше времени (по сравнению с обычными методами) на восстановление исходного пароля, но на практике более реализуемы (для построения обычной таблицы для 6-символьного пароля с байтовыми символами потребуется 256⁶ = 281 474 976 710 656 блоков памяти, в то время как для радужной — всего 256^6·⅔ = 4 294 967 296 блоков).

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

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

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

Таблицы могут взламывать только ту хеш-функцию, для которой они создавались, то есть таблицы для MD5 могут взломать только хеш MD5. Теория данной технологии была разработана Philippe Oechslin^[1] как быстрый вариант time-memory tradeoff ^[2]. Впервые технология использована в программе Ophcrack для взлома хешей LanMan (LM-хеш), используемых в Microsoft Windows. Позже была разработана более совершенная программа RainbowCrack, которая может работать с большим количеством хешей, например LanMan, 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( пароль + соль ),
или
хеш = MD5( MD5(пароль) + соль ).

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

По сути, затравка увеличивает длину и, возможно, сложность пароля. Если таблица рассчитана на некоторую длину или на некоторый ограниченный набор символов, то затравка может предотвратить восстановление пароля.Например, в старых Unix паролях использовалась затравка, размер которой составлял всего лишь 12 бит. Для взлома таких паролей злоумышленнику нужно было посчитать 4096 таблиц, что можно свободно хранить на терабайтных жестких дисках. Такие же алгоритмы хеширования, как MD5 и bcrypt используют затравку размером 48 и 128 бит соответственно.^[3] Такие большие длины затравки делают предварительные вычисления просто бессмысленными. Другим возможным способом борьбы против атак, использующие предварительные вычисления, является растяжение ключа(англ. key stretching).Например:

ключ = хеш(пароль + соль)
for 1 to 65536 do
ключ = хеш(ключ + пароль + соль)

Этот способ снижает эффективность применения предварительных вычислений, так как использование промежуточных значений увеличивает время, которое необходимо для вычисления одного пароля, и тем самым уменьшает количество вычислений, которые злоумышленник может произвести в установленные временные рамки.^[4] Данный метод применяется в следующих алгоритмах хеширования: MD5, в котором используется 1000 повторений, и bcrypt.^[5] Альтернативным вариантом является использование усиление ключа(англ. key strengthening), который часто принимают за растяжение ключа. Применяя данный метод, мы увеличиваем размер ключа за счет добавки случайной затравки, которая затем спокойно удаляется, в отличие от растяжения ключа, когда затравка сохраняется и используется в следующих итерациях.^[6] Также рассмотрим LM-хеш – это старый алгоритм хеширования, который используется в Microsoft. Он чрезвычайно уязвим, так пароль, состоящий больше, чем из 7 символов, но меньше, чем из 15 символов, разбивается на две части, которые хешируютя независимо друг от друга. Поэтому, чтобы избежать создания LM-хеша, необходимо использовать пароли из 15 символов и более.^[7]

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

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

Примечания

1. ↑ Philippe Oechslin
2. ↑ Доклад Philippe Oechslin на конференции CRYPTO’03 (PDF)
3. ↑ Alexander, Steven (June 2004). «Password Protection for Modern Operating Systems». ;login: (USENIX Association) 29 (3).
4. ↑ Ferguson Neils Practical Cryptography. — Indianapolis: John Wiley & Sons. — ISBN 0-471-22357-3
5. ↑ (June 6, 1999) «A Future-Adaptable Password Scheme». Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference (USENIX Association).
6. ↑ U. Manber, "A Simple Scheme to Make Passwords Based on One-Way Functions Much Harder to Crack," Computers & Security, v.15, n.2, 1996, pp.171-176.
7. ↑ How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases, Microsoft

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

• Страница Ophcrack Оригинальная исследовательская работа с демонстрацией
• Проект RainbowCrack
• oxid.it Содержит winrtgen — графическую оболочку для rtgen (утилиты создания таблиц)
• Взлом MD5 с помощью радужных таблиц
• Создание радужных таблиц для A5/1 (используется в GSM сетях, пока только для видеокарт с CUDA)
• Большие радужные таблицы от группы Shmoo Group, создателей AirSnort