Радужная таблица (rainbow table) — заранее вычисленная структура данных, позволяющая восстанавливать пароли по хешам без соли гораздо быстрее, чем при вычислении каждого хеша во время атаки.
Как работают радужные таблицы
Взлом хеша обычно означает хеширование вариантов пароля до совпадения. Готовая таблица «пароль — хеш» для всех паролей работала бы мгновенно, но потребовала бы колоссального объёма памяти. Радужные таблицы, предложенные Филиппом Ошлином (Philippe Oechslin) в 2003 году на основе компромисса «время — память» Мартина Хеллмана 1980 года, находят золотую середину:
- Таблица состоит из цепочек: пароль хешируется, хеш с помощью «функции редукции» превращается в новый вариант пароля, который снова хешируется, — и так тысячи раз.
- Хранятся только первое и последнее значения каждой цепочки, что экономит огромный объём места.
- Чтобы взломать хеш, атакующий строит от него цепочку, ищет совпадающую конечную точку, а затем восстанавливает цепочку целиком и находит пароль.
Каждая таблица подходит только для одного алгоритма хеширования и заданного набора символов и длины. Метод популяризировали RainbowCrack и Ophcrack — особенно против LM- и NTLM-хешей Windows, которые не используют соль.
Почему это важно
Для быстрых хешей без соли — MD5, SHA-1 или NTLM — радужные таблицы сокращают время взлома коротких паролей с нескольких дней до минут. Именно такие хеши утекали при многих старых взломах сайтов. Сегодня атаки по словарю на видеокартах с помощью Hashcat часто быстрее и гибче, но радужные таблицы остаются хрестоматийным примером того, почему так важен правильный способ хранения хешей.
Как защититься
- Добавлять к каждому паролю перед хешированием уникальную случайную соль — она делает заранее вычисленные таблицы бесполезными.
- Использовать специальные алгоритмы хеширования паролей: Argon2, bcrypt, scrypt или PBKDF2.
- Отключить устаревшие LM-хеши и сократить зависимость от NTLM.
- Требовать длинные пароли или парольные фразы.
