"Кто-нибудь другой наверняка уже высказал все твои мысли лучше тебя, так что если не можешь сказать еще лучше воруй у великих!" (с)

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

Оглавление
1. Вступление
2. Теория

2.1 Таблицы
2.2 Структура и поиск в rainbow table
2.3 Создание таблиц с помощью winrtgen, наглядные характеристики таблиц
2.4 Статистические данные из "MakingaFasterCryptanalyticTime-Memory Trade-Off" от Philippe Oechslin

3. Практика

3.1 Непосредственное создание и использование таблиц
3.2 Использование таблиц в других программах

4. FAQ
5. Links

1. Вступление

Для понимания данного материала, надо знать элементарные вещи про то что такое пароли, хеши, алгоритмы и тд и тп, но мне не трудно, и я напомню что такое хеш

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

Примеры хешей
MD5 - 5f4dcc3b5aa765d61d8327deb882cf99
MySQL - 5d2e19393cc5ef6
SHA-1 - 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8

Где MD5, MySQL, SHA-1 типы хешей. Однозначного соответствия между паролем и хешем быть не может в общем случае, и разные пароли имеют разные хеши - это криптографические особенности хеш функции.

2.1 Таблицы

Существует такое понятие как таблицы поиска (lookup table) - это такие таблицы, которые представляют собой массив данных, созданы они для того чтоб заменить ресурсоемкие вычисления на обычных поиск, и используются в тех случаях, когла гораздо легче извлекать эти данные из памяти, чем их создавать.

В 1980 году Мартин Хеллман предложил использовать предварительно вычисленные таблицы, размещенные в памяти, и это было зарождением rainbow tables.

Теперь перейдем к определению Rainbow table:
Для ускорения генерации и поиска используются различные оптимизации и ухищрения, такие как time-memory tradeoff (компромис памяти и времени) в различных вариантах.

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

2.2 Структура и поиск в rainbow table

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

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

Если не ясно, постараюсь объяснить чуть более подоробно:

1. Фиксируется рабочий алфавит, то есть задается множество Q всех возможных ключей.
2. Фиксируется элемент q из множества Q и вычисляется значение h хэш-функции на нем.
3. При помощи некоторой «срезающей» функции R из хэша генерируется ключ, принадлежащий множеству Q: q=R(h). Если число элементов в цепочке меньше заданного, осуществляется переход к пункту 2.

Эти операции будут повторяться пока не будет получена цепочка длиной t ключей. Эта последовательность не размещается целиком в памяти, записывается лишь первый и последний ее элементы. Это и есть time-memory tradeoff - допустим генерим цепочку из 2000 ключей, а записывается только первый и последний элементы, получаем огромнейшую экономию, но с другой стороны время криптоанализа увеличивается.
Далее генерируем определенное количество цепочек, которые удобно представить в виде таблицы с двумя колонками (двумерный массив), в первой из которых находится начальный ключ цепочки, а во второй - конечный. После того, как цепочки сгенерированны, можно уже осуществлять в них поиск ключа.

Задается значение хэш-функции, для которого необходимо получить коллизию (нахождение соответствия). При помощи срезающей функции R строится значение ключа K0, из которого выводится по описанному алгоритму цепочка поиска длиной не более чем t элементов. Если в таблице есть искомый ключ, то один из сгенерированных элементов новой цепочки будет являться терминальным элементом нашей таблицы. Далее не составляет труда по известному начальному элементу вывести всю соответствующую терминалу цепочку, включая элемент, непосредственно предшествующий начальному значению K0, то есть ключ, который мы ищем. Но если же в сгенерированных таблицах нет коллизия, то нельзя дать точного ответа сколько нужно сгенерировать цепочек, чтобы они покрывали все множество возможных ключей.

Еще не ясно? Ок, попробуем иначе

Min Len - минимальное число букв в пароле.
Max Len - максимальное число букв в пароле.
K = Сумма(по i, от L1, до L2, C^i) - Число букв в чарсете и MaxLen с MinLen влияют на общее число паролей которые подлежат анализу
Где K – кейспейс,
L1 – минимальная длина пароля,
L2 – максимальная длина пароля,
C – число букв в чарсете. Чарсетом называют набор букв, к примеру ABCDEFGHIJKLMNOPQRSTUVWXYZ.

Строка таблицы состоит из двух записей. Запись по 8 байт, то есть строка 16 байт
При расчете записи таблицы выполняется такая последовательность действий:

1. Скидывается случайное число от нуля до кейспейса.
2. Находится плейнтекст пароля, соответствующий этому случайному числу.
3. Вычисляется хэш пароля.
4. Вычисляется R от хэша.
5. Находится плейнтекст соотвтствующий индексу в кейспейсе полученому на предыдущем шаге.
Дальше пункты 3-5 выполняются столько раз сколько "длина цепочки".

Последняя запись таблицы - это R от последнего хэша, т.е. запись таблицы состоит из двух групп по 8 байт, в каждой группе из 8 байт хранится число от 0 до кейспеса. Конечно кейспейс всегда меньше чем 256^8 , именно это (и еще сортированность таблицы) дает возможность так хорошо ее паковать.

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

При росте размеров таблицы вероятность P* практически перестает увеличиваться. По этой причине для эффективного использования метода необходимо создавать несколько таблиц, сгенерированных независимым образом.

Вероятность успеха, объем занимаемой памяти и время поиска зависят от длины цепочек t, их количества m и числа используемых таблиц l.
Поэтому общий объем таблицы из m цепочек составляет 16*m. Соответственно, если таблица всего одна, то они занимают 16*m*l байт.
Что касается времени поиска хэша, то оно выражается так: t*t/(2*speed), где speed - это скорость вычисления хэшей.

2.3 Создание таблиц с помощью winrtgen, наглядные характеристики таблиц

Генерировать таблицы можно с помощью визуальной утилиты или стандартной rtgen, но сейчас мы запустим winrtgen для того что разобраться с параметрами таблиц. Итак, winrtgen и далее кнопка "add table"

Еще раз повторю, что значат параметры
Hash название хэш алгоритма. Хэшалгоритм должен поддерживаться данным билдом генератора таблиц. В winrtgen вшит ограниченный набор алгоритмов. В коммандлайный rtgen можно вкомпилировать любой свой алгоритм или любую свою собственную имплементацию, которая будет быстрее работать на вашей системе.
Min Len минимальное число букв в пароле.
Max Len максимальное число букв в пароле.
K = Сумма(по i, от L1, до L2, C^i)
Где K – кейспейс,
L1 – минимальная длина пароля,
L2 – максимальная длина пароля,
C – число букв в чарсете.

Допустим будут такие соотношениея (в случае, если C=30, L1=1, L2=8, для примера):
- Увеличение L2 (длины пароля) на 1 увеличивает кейспейс примерно в 30 (длина чарсета) раз.
- Увеличение чарсета на одну букву увеличивает кейспейс примерно на 30%. Примерная формула L2/C
- Отказ от просчета паролей меньшей длины, т.е. изменение L1 так чтобы L1=L2 приводит к уменьшению кейспейса примерно на 3% т.е. на (1/C).

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

Чарсет – название чарсета из файла charset.txt для характеристики таблиц имеет значение только число букв в чарсете. Однако для правильной работы программы необходимо поставлять файл чарсета вместе с таблицами, ибо кракер, выполняющий криптоанализ должен иметь тот же самый charset.txt что и генератор таблиц. При этом имеет значение порядок букв в чарсете.

Index – Строго говоря, этот параметр задает некий оффесет, используемый функцией редукции. Можно называть его номером таблицы. Следует сказать, что если вы сгенерируете две таблицы с одинаковым индексом, это будут все равно две РАЗНЫЕ таблицы. Фактически это будет эквивалентно тому, что вы сгенерировали таблицу вдвое большей длины. Разница между двумя таблицами с одинаковым индексом и двумя таблицами с разным индексом состоит в том, что во втором случае КПД несколько выше, разница тем больше, чем больше длина строки таблицы (chain len). В данном случае под КПД таблицы понимается отношение числа паролей, которые могут быть вскрыты таблицей, к числу хэшей, которое было рассчитано в ходе генерации таблиц
Еще можно добавить что индексы и суффиксы используются для того, чтобы отличать таблицы друг от друга. Вообще же, пароли в таблицы собираются не по-порядку, а случайным образом. Поэтому метод никогда не даёт 100% гарантии подбора любого пароля, но в то же время:
1. Чем больше посчитано таблиц, тем выше вероятность нахождения пароля по данному алгоритму и ключевому пространству.
2. Любые таблицы могут использоваться для поиска паролей из любой части ключевого пространства.
RainbowCrack доводит каждый набор таблиц до расчётной вероятности 99,9%. Используются индексы от 0 до 7 и суффиксы от 0 до 24. Для разных ключевых пространств эти диапазоны отличаются.
Общие правила:
1. Кол-во индексов * Кол-во суффиксов = Кол-во таблиц для расчёта.
2. Длина цепочки * Кол-во цепочек = Кол-во паролей в таблице.
3. Кол-во цепочек * 16 = Размер таблицы (в байтах).

Chain Len – Длина строки таблицы. Увеличение длины таблицы, к примеру вдвое, приводит (при прочих равных условиях) к увеличению времени расчетов ровно в два раза, увеличению вероятности вскрытия почти ровно в два раза, не приводит к изменению объема таблицы, приводит к увеличению времени криптоанализа по таблицам примерно в 4 раза.

Чтобы было понятнее, сравним таблицы:
А) chain len = 2400 chain count = 40 000 000

Б) chain len = 4800 chain count = 20 000 000



По идее эти две таблицы должны иметь примерно одинаковые свойства. Разница между ними состоит в:
1. Время генерации одинаковое.
2. Таблица Б имеет вдвое меньший размер.
3. Вероятность вскрытия почти одинаковая, может колебаться в обе стороны, не более 0.1%.
4. Время криптоанализа по таблице Б больше примерно в 4 раза.

Ниже приблизительная связь вероятности успеха - КПД, рассчитанная для одного частного случая.
0.1 - 91.4%
0.5 - 59.7%
0.7- 42%
0.8 - 32.1%
0.85 - 26.7%
0.9 - 20.7%
0.95 - 13.7%
0.98 - 8.3%

Разобравшись с тем на что влияет каждый параметр, вы уже должны выбрать для себя, чем жертвовать, свободным место или временем для криптоанализа.
Для начала, задать желаемую вероятность успеха. Выбрав вероятность успеха, следует выбрать длину строки такую, чтобы достичь компромисса между вашим дисковым пространством и временем, необходимым на криптоанализ по получившимся таблицам. Разумной представляется величина на уровне 80% - 90%. Меньше особого смысла нет, т.к. повышать вероятность до 80% можно без особого вреда для КПД. А повышать ли выше 80% думать вам, в зависимости от объема ваших счетных ресурсов. Повышение до 90% повысит время счета и требуемое дисковое пространство в полтора раза, это еще ничего, а вот дальше уже это вряд ли оправдано.

Вот смотрите сами, зависимость количества таблиц и success probability %:

2.4 Статистические данные из "Making a Faster Cryptanalytic Time-Memory Trade-Off" от Philippe Oechslin

В работе Philippe Oechslin есть сравнения поиска по обычным и rainbow таблицам, приведу лишь часть таблицы, чтоб не нагружать вас цифрами и формулами:

Из этой таблицы видно, что rainbow выигрывают по скорости в 7 раз.