Радуга в таблицах

Никита Кислицин

Хакер, номер #082, стр. 082-050-1

(nikitoz@real.xakep.ru)

Использование rainbow tables для сверхбыстрого взлома хэшей

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

[начало]

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

К сожалению, сейчас многие проекты страдают довольно странной, на мой взгляд, вещью: они сами предоставляют интерфейс для аутентификации через хэш-пароля, обращая в маразм всю эту затею с шифрованием. За примерами далеко ходить не надо: куча web-форумов, которые хранят в пользовательских cookies зашифрованные пароли и осуществляют аутентификацию по этим значениям.

Если же аутентификация по хэш-паролю невозможна, перед взломщиком встает серьезная проблема: нужно каким-то способом получить исходную строку по известному хэшу. Строго говоря, решение этой задачи не единственное: нельзя исключать ситуацию, при которой двум различным строкам будет соответствовать одно и тоже значение хэш-функции. Именно по этой причине правильно говорить, что взлом хэша - это поиск коллизии, а не исходной строки. Ведь если одному значению хэша соответствуют строки «jkfdskhjvk» и «Qkfdjkvfdhlbdfhbf», невозможно знать наверняка, какую из них загадал пользователь Петя.

Каким же образом возможно найти коллизию? Самый простой вариант, который приходит в голову - тупой перебор всех возможных значений. Генерируется множество всех допустимых значений строк-оригиналов, берется первый элемент, для него генерируется хэш, сравнивается с известным. Если значения совпадают, процесс закончен и коллизия найдена. Если не совпадают, берется следующий элемент. И так до тех пор, пока не обнаружится коллизия, либо не закончится множество претендентов.

К сожалению, такой подход не может обеспечить хорошей производительности. Дело в том, что процесс перебора занимает разумное время только в том случае, если множество вариантов не слишком велико. Перебор всех возможных строк длиной в 10 символов - это уже неземная задача для PC-хакера. Именно по этой причине люди стали искать пути к тому, чтобы оптимизировать процесс поиска коллизий. И что ты думаешь, нашли.