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

Радужные таблицы (англ. rainbow tables) — это специализированные структуры данных, используемые для ускорения обратного восстановления паролей по их хеш-значениям. Они представляют собой предварительно вычисленные цепочки хеш-функций и функций редукции, организованные в таблицу, которая позволяет находить пароль за время, значительно меньшее, чем при полном переборе (brute force), при умеренных затратах памяти. Метод является разновидностью атаки «время-память» (time-memory trade-off), предложенной Мартином Хеллманом в 1980 году и усовершенствованной Филиппом Окслином в 2003 году.

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

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

Цепочки хеширования и редукции

Цепочка строится следующим образом:

1. Выбирается случайный пароль \( P_1 \) (начальная точка).
2. К нему применяется хеш-функция \( H \), получается хеш \( H(P_1) \).
3. К полученному хешу применяется функция редукции \( R \), которая преобразует хеш (обычно длинную строку) обратно в пароль (более короткую строку, соответствующую алфавиту паролей). Получается \( P_2 = R(H(P_1)) \).
4. Процесс повторяется: \( H(P_2) \), затем \( R(H(P_2)) = P_3 \), и так далее \( k \) раз.
5. Конечная точка цепочки — последний полученный пароль \( P_k \).

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

Поиск пароля

Для восстановления пароля по данному хешу \( h \) выполняется следующий алгоритм:

1. К хешу \( h \) применяется функция редукции \( R \), получается пароль \( P' \). Проверяется, является ли \( P' \) конечной точкой какой-либо цепочки в таблице.
2. Если нет, то к \( P' \) снова применяется хеш-функция, затем редукция, и так далее до \( k \) раз. На каждом шаге проверяется, не стал ли очередной пароль конечной точкой.
3. Если на каком-то шаге пароль совпал с конечной точкой, то из таблицы извлекается соответствующая начальная точка, и цепочка пересчитывается с неё до тех пор, пока не будет получен хеш, равный исходному \( h \). Предыдущий пароль в этой цепочке и будет искомым.
4. Если за \( k \) шагов совпадение не найдено, пароль не содержится в таблице.

Ключевое отличие радужных таблиц от метода Хеллмана заключается в использовании разных функций редукции для каждого шага цепочки. В классическом методе Хеллмана использовалась одна и та же функция редукции, что приводило к коллизиям и слиянию цепочек. В радужных таблицах для каждого шага \( i \) применяется своя функция \( R_i \), что значительно снижает вероятность коллизий и делает таблицы более эффективными.

История

Концепция атаки «время-память» была впервые предложена Мартином Хеллманом в 1980 году. Его метод позволял восстанавливать ключи шифрования, но имел серьёзный недостаток — высокую вероятность коллизий (слияния цепочек), что снижало эффективность.

В 2003 году Филипп Окслин (Philippe Oechslin) опубликовал работу «Making a Faster Cryptanalytic Time-Memory Trade-Off», в которой представил усовершенствованную версию метода, названную радужными таблицами. Окслин предложил использовать для каждого шага цепочки свою функцию редукции, что позволило практически полностью устранить проблему слияния цепочек и повысить скорость поиска.

С тех пор радужные таблицы стали стандартным инструментом для взлома паролей, особенно тех, которые хранятся в виде хешей без соли (salt). Инструменты, такие как Ophcrack (для LM-хешей Windows) и RainbowCrack, реализуют этот метод и предоставляют готовые таблицы для различных хеш-функций.

Классификация и характеристики

Радужные таблицы классифицируются по нескольким параметрам.

По типу хеш-функции

• Для LM-хешей: используются для взлома старых паролей Windows (Lan Manager), которые имеют слабую криптостойкость.
• Для NTLM-хешей: для современных систем Windows.
• Для MD5, SHA-1, SHA-256: для широко распространённых криптографических хеш-функций.
• Для специализированных алгоритмов: например, для хешей, используемых в базах данных (MySQL, PostgreSQL) или в архиваторах (RAR, ZIP).

По длине и сложности пароля

• По длине: таблицы могут быть рассчитаны на пароли определённой длины (например, от 1 до 7 символов, от 8 до 14 символов).
• По алфавиту: таблицы могут включать только цифры, только буквы нижнего регистра, буквы верхнего и нижнего регистра, а также специальные символы. Чем шире алфавит, тем больше возможных паролей и тем больше таблица.

По размеру и эффективности

• Размер таблицы: варьируется от нескольких гигабайт до нескольких терабайт. Чем больше таблица, тем выше вероятность нахождения пароля, но тем больше времени требуется на её создание и хранение.
• Вероятность успеха: зависит от размера таблицы и длины цепочек. Для типовых таблиц вероятность может достигать 99% для паролей определённой длины и сложности.

Применение

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

Легитимное использование

• Восстановление паролей: пользователи могут восстановить забытый пароль к своей учётной записи, если администратор системы предоставит хеш.
• Аудит безопасности: специалисты по информационной безопасности используют радужные таблицы для проверки стойкости парольных политик в организациях. Если пароль легко находится по таблице, это сигнал о необходимости его смены.
• Криминалистика: в судебной экспертизе для извлечения данных из зашифрованных устройств или файлов.

Злонамеренное использование

• Несанкционированный доступ: злоумышленники могут использовать радужные таблицы для взлома учётных записей пользователей, получив доступ к базе данных хешей.
• Распространение вредоносного ПО: некоторые программы-вымогатели используют радужные таблицы для взлома паролей к зашифрованным файлам.

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

Существует несколько эффективных методов защиты от атак с использованием радужных таблиц.

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

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

Использование стойких хеш-функций

Современные алгоритмы хеширования паролей, такие как bcrypt, scrypt, PBKDF2 и Argon2, являются медленными по своей природе. Они намеренно требуют больших вычислительных затрат (многократное хеширование, использование большого объёма памяти). Это делает вычисление радужных таблиц для них крайне затратным по времени и ресурсам, а также замедляет сам процесс поиска.

Увеличение длины и сложности пароля

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

Ограничение числа попыток входа

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

Критика и ограничения

Несмотря на эффективность, радужные таблицы имеют ряд ограничений и критикуются за:

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

Интересные факты

• Самая известная реализация радужных таблиц — проект RainbowCrack, который предоставлял готовые таблицы для различных хеш-функций. Проект был закрыт в 2010-х годах.
• В 2004 году Филипп Окслин получил премию за лучшую статью на конференции USENIX Security Symposium за свою работу о радужных таблицах.
• Некоторые современные системы, такие как Windows 10 и 11, по умолчанию используют хеширование с солью и медленные алгоритмы (NTLMv2), что делает их устойчивыми к атакам с помощью радужных таблиц.

Источники

• Oechslin, P. (2003). «Making a Faster Cryptanalytic Time-Memory Trade-Off». Advances in Cryptology — CRYPTO 2003.
• Hellman, M. (1980). «A cryptanalytic time-memory trade-off». IEEE Transactions on Information Theory.
• «Rainbow Tables» — статья в англоязычной Википедии.
• «Ophcrack» — документация проекта.
• «RainbowCrack» — документация проекта.