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

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

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

[липкая дрянь]

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

А я пока продолжу отвечать на вопрос о количестве цепочек. Вообще говоря, чтобы обеспечить полное покрытие множества Q, необходимо сгенерировать бесконечно большую таблицу с цепочками. Дело в том, что частота слипания цепей быстро увеличивается вместе с ростом таблицы. Поэтому число требуемых последовательностей характеризуется требуемой вероятностью (обозначу ее как P*) того, что произвольный ключ q из Q окажется в нашей системе подмножеств, в нашей таблице. Именно требуемая вероятность P* определяет необходимый размер таблицы с цепочками. Обрати внимание, что под «размером» таблицы я понимаю как число цепочек, так и их длину, оба эти параметра влияют на частоту слипания и эффективность покрытия.

В работе Хеллмана строго выводится формула, по которой можно вычислить P* как функцию от числа цепочек, их длины и числа элементов во множестве Q. Это довольно здоровое выражение, и само по себе нас мало интересует, нас больше заботит, что оно показывает. Собственно, ничего кардинально нового: при росте размеров таблицы вероятность P* практически перестает увеличиваться. По этой причине для эффективного использования метода необходимо создавать несколько таблиц, сгенерированных независимым образом. В этом случае общая вероятность успеха (P) выражается так: P=1-(1-P*)^l, l - число таблиц. Эту формулу очень легко получить из простейших соображений: (1-P*) - это вероятность того, что мы не найдем ключ в одной из таблиц; (1-P*)^l - вероятность, что вообще не найдем ключ ни в одной из l таблиц. Соответственно, вероятность обратного события - это P=1-(1-P*)^l.

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

[конкретные вещи]

Думаю, то, что я рассказал тебе, будет достаточно для понимания более практических вещей. Давай познакомимся с конкретным софтом, научимся с ним работать и, вообще, понюхаем эти радуги в таблицах. На самом деле, в Сети не так уж и много информации о rainbow tables: если ты поищешь инфу в гугле, то, по существу, увидишь только одну содержательную ссылку - www.antsight.com/zsl/rainbowcrack. Однако смею тебя заверить, ее нам будет предостаточно! Это сайт проекта с говорящим названием RainbowCrack, главная ценность которого находится в разделе Downloads. Там предлагается скачать софтину, с помощью которой можно генерировать цепочки ключей, и взламывать при помощи уже созданных таблиц конкретные хэши. Софтина поставляется в том числе и в исходных кодах, так что при наличии у тебя желания и необходимого опыта, можно будет ознакомиться с конкретной реализацией всего того, о чем мы говорили выше. Мы же в этой статье просто научимся пользоваться этой программой для генерации rainbow-таблиц и взлома хэшей. Под FreeBSD собрать эту программу у меня не получилось, и поэтому я решил все эксперименты проводить на виндовой машине - благо на сайте лежит уже готовый бинарник, и париться с компиляцией не нужно. Последняя версия системы - 1.2, она поддерживает работу с хэшами LanManager, md5, sha1, а также позволяет пользователю легко прикручивать к программе свои собственные алгоритмы, которых нет в базовом списке.