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

Радужная таблица — это структура данных, используемая в криптографии для ускорения процесса восстановления открытого текста по его хеш-значению (криптографической хеш-функции). Основное применение радужных таблиц — взлом паролей, хранящихся в виде хешей, путём поиска по таблице предварительно вычисленных цепочек хешей. Радужные таблицы представляют собой компромисс между временем вычислений и объёмом памяти, позволяя значительно сократить время подбора пароля по сравнению с полным перебором, при этом занимая меньше места, чем полная таблица соответствий «хеш — пароль».

Принцип работы

Радужные таблицы основаны на идее, впервые предложенной Мартином Хеллманом в 1980 году, и были усовершенствованы Филиппом Охслином в 2003 году. В отличие от простых таблиц Хеллмана, радужные таблицы используют несколько различных редукционных функций (R1, R2, ..., Rk) для построения цепочек, что устраняет проблему коллизий и слияния цепочек, характерную для исходного метода.

Основные элементы

1. Хеш-функция (H) — криптографическая функция, преобразующая произвольный пароль в хеш-значение фиксированной длины (например, MD5, SHA-1, SHA-256). В контексте взлома паролей хеш-функция известна атакующему.
2. Редукционная функция (R) — функция, преобразующая хеш-значение (обычно длинную строку битов) обратно в строку, соответствующую возможному паролю (например, в строку длиной от 1 до 8 символов, состоящую из букв и цифр). Редукционная функция не является обратной к хеш-функции; она лишь отображает хеш в пространство паролей. В радужной таблице используется несколько различных редукционных функций (R1, R2, ..., Rk), по одной для каждого шага цепочки.
3. Цепочка — последовательность, начинающаяся с пароля P1, к которому применяется хеш-функция, затем редукционная функция, затем снова хеш-функция и так далее. Цепочка имеет фиксированную длину k (количество шагов). Она записывается в таблицу только первой (начальный пароль) и последней точкой (конечный хеш после применения последней редукционной функции).
4. Радужная таблица — набор таких цепочек, построенных для всех возможных паролей из заданного пространства (например, все пароли длиной от 1 до 8 символов из латинских букв нижнего регистра). Каждая цепочка представлена парой (начальный пароль, конечный хеш).

Процесс построения таблицы

1. Выбирается множество начальных паролей (P1, P2, ..., Pn), покрывающее всё пространство возможных паролей.
2. Для каждого начального пароля строится цепочка длиной k:

• H(P1) → h1
• R1(h1) → P2
• H(P2) → h2
• R2(h2) → P3
• ...
• H(Pk) → hk
• Rk(hk) → Pk+1 (конечный пароль, который не хранится, но используется для вычисления конечного хеша)
• H(Pk+1) → hk+1 (конечный хеш)

1. В таблицу сохраняется только пара (P1, hk+1). Все промежуточные пароли и хеши отбрасываются.

Процесс поиска по таблице

Для заданного хеша h (например, хеша пароля, который нужно взломать) выполняется поиск в радужной таблице:

1. На первом шаге предполагается, что h находится на последнем шаге цепочки. Применяется редукционная функция Rk к h, получается пароль P'. Затем вычисляется хеш H(P') = h'. Если h' совпадает с каким-либо конечным хешем в таблице, то восстанавливается соответствующая цепочка, начиная с её начального пароля, и в ней находится пароль, дающий исходный хеш h.
2. Если совпадения нет, предполагается, что h находится на предпоследнем шаге. Применяется Rk-1 к h, затем H, затем Rk, и снова сравнивается с конечными хешами.
3. Процесс повторяется, последовательно «продвигая» хеш вперёд по цепочке, пока не будет найдено совпадение или не будет проверено k шагов.

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

Преимущества и недостатки

Преимущества

• Экономия памяти: Радужные таблицы занимают значительно меньше места, чем полные таблицы «хеш-пароль» (например, таблица для всех 8-символьных паролей из букв и цифр заняла бы терабайты). В радужной таблице хранится только начальный и конечный хеш каждой цепочки, а не все промежуточные значения.
• Ускорение поиска: Поиск по радужной таблице происходит значительно быстрее, чем полный перебор всех возможных паролей. Время поиска пропорционально квадрату длины цепочки (k²), что всё равно намного быстрее, чем O(2^n) для полного перебора.
• Устранение коллизий: Использование нескольких редукционных функций (R1, R2, ..., Rk) в радужных таблицах практически полностью устраняет проблему слияния цепочек, которая была характерна для таблиц Хеллмана. Это делает радужные таблицы более эффективными и предсказуемыми.

Недостатки

• Вероятностный характер: Радужная таблица не гарантирует нахождение пароля для любого хеша. Она покрывает лишь определённую часть пространства паролей. Для увеличения вероятности успеха необходимо строить несколько таблиц или увеличивать их размер.
• Затраты на построение: Построение радужных таблиц требует значительных вычислительных ресурсов и времени. Для больших пространств паролей (например, до 10 символов) построение таблицы может занять недели или месяцы даже на мощных компьютерах.
• Зависимость от хеш-функции: Радужные таблицы эффективны только для конкретной хеш-функции. Для другой хеш-функции (например, SHA-256 вместо MD5) необходимо строить новую таблицу. Современные системы часто используют «соль» (salt) — случайное значение, добавляемое к паролю перед хешированием. Радужные таблицы, построенные без учёта соли, бесполезны для взлома таких систем.
• Ограниченность пространства: Радужная таблица может быть построена только для ограниченного пространства паролей (например, длина до 8 символов, определённый набор символов). Для паролей, выходящих за эти рамки (например, длиннее 12 символов или содержащих специальные символы), построение таблицы становится практически невозможным.

Применение

Взлом паролей

Основное и наиболее известное применение радужных таблиц — это восстановление паролей по их хешам, полученным из скомпрометированных баз данных. Атакующий, получив базу данных с хешами паролей, может использовать радужные таблицы для быстрого подбора паролей, если они не были защищены солью. В прошлом радужные таблицы активно использовались для взлома хешей MD5 и SHA-1, которые ранее широко применялись в системах аутентификации.

Криптоанализ

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

Обратная разработка

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

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

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

Другие методы защиты включают:

• Использование стойких хеш-функций: Современные криптографические хеш-функции, такие как SHA-256, SHA-3, bcrypt, scrypt, Argon2, являются более устойчивыми к атакам по радужным таблицам, чем устаревшие MD5 и SHA-1.
• Увеличение длины пароля: Радужные таблицы, как правило, ограничены по длине пароля. Пароли длиннее 10-12 символов значительно усложняют построение таблиц.
• Использование «перца» (pepper): Секретное значение, добавляемое к паролю перед хешированием, которое хранится отдельно от базы данных хешей. Это делает атаку ещё более сложной.

Примеры реализации

Существует несколько известных программных реализаций радужных таблиц, наиболее известной из которых является RainbowCrack (автор — Чжу Шулян). Эта программа позволяет создавать радужные таблицы для различных хеш-функций (MD5, SHA-1, SHA-256, NTLM) и выполнять по ним поиск. Также существуют готовые наборы радужных таблиц, доступные в интернете, которые можно использовать с RainbowCrack.

Другие реализации включают Ophcrack (специализируется на взломе LM-хешей Windows) и Cain & Abel (многофункциональный инструмент, включающий поддержку радужных таблиц).

Критика

Основная критика радужных таблиц связана с их использованием в незаконных целях, таких как взлом учётных записей пользователей. Однако сами по себе радужные таблицы являются нейтральным инструментом; их применение зависит от намерений пользователя. В академической среде радужные таблицы рассматриваются как важный инструмент для изучения стойкости хеш-функций и методов защиты паролей. Кроме того, они могут использоваться для восстановления утерянных паролей к личным данным при условии, что владелец данных имеет к ним законный доступ.

Источники

• Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
• Oechslin, P. (2003). Making a Faster Cryptanalytic Time-Memory Trade-Off. Advances in Cryptology — CRYPTO 2003, 617-630.
• RainbowCrack Project. (n.d.). RainbowCrack — Crack Hashes with Rainbow Tables. Retrieved from rainbowcrack.com.
• Шнайер, Б. (1996). Прикладная криптография. 2-е изд.