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

Определение

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

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

Как это работает

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

Это обмен времени на память. Полезные таблицы строить дорого, зато после построения ими можно быстро проверять много подходящих несолёных хешей.

Защита

Уникальная случайная соль для каждого пароля делает одну предвычисленную таблицу бесполезной для множества учётных записей, потому что соль меняет хешируемое значение. Медленные функции хеширования паролей, такие как Argon2id, bcrypt и PBKDF2, дополнительно повышают стоимость каждой догадки.

Соли не делают слабые пароли сильными, а быстрые сырые хеши вроде MD5 или SHA-1 всё равно плохо подходят для хранения паролей даже с солью. Храните пароли с помощью специализированной функции хеширования и актуальных параметров стоимости.