Wikipedia Радужные таблицы

Question

Страница Википедии для радужных столов говорит:

«это использование нескольких функций сокращения примерно вдвое увеличивает скорость поиска».

Предполагая "среднюю" позицию в цепочке, мы берем хеш и пропускаем его по 9-итерационной цепочке ...

Исходная таблица проходит через 4 сокращения и 4 хэша и находит конец цепочки, затем ищет еще 5 хешей 5 сокращений ... всего 9 хешей 9 сокращений

Радужная таблица проводит ее через вычисления Rk-1, Rk-2, Rk-3 и Rk-4, чтобы найти конец цепочки, затем еще 5 хешей 5 сокращений, чтобы получить открытый текст: всего 15 хешей 15 сокращений ...

Что мне здесь не хватает? По моей математике, единственный случай, когда поиск по радуге равен той же скорости, что и обычная таблица, это когда хэш просто оказывается в самом конце цепочки ... На самом деле RT должен постепенно увеличиваться по мере продвижения к началу хэш лежит ...

Цепочка 5k с хешем в начале должна быть примерно в 2500 раз медленнее с радужными таблицами, чем с обычными хеш-таблицами ...

Я что-то упустил или Википедия допустила ошибку? (Документ , упомянутый на этой странице (стр. 13), также был бы неправильным, поэтому я склоняюсь к первому)

Answer 1

Цель радужных столов не обязательно быть быстрее, а уменьшить пространство. Радужные столы обменивают скорость на размер.

Хранение хешей для всех возможных 10-значных паролей, например, будет чрезмерно дорогим с точки зрения дискового пространства. Также необходимо учитывать, что, поскольку пространство словаря настолько велико, это потребует значительного разбиения по страницам (очень медленная операция).

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

Вот лучший иллюстрированный пример: http://kestas.kuliukas.com/RainbowTables/

Конечно, все это академично. Радужные столы не имеют никакой ценности против хорошо спроектированных систем безопасности. 1) Использовать криптографически безопасный алгоритм (не «бросай свой») 2) Используйте функцию выведения ключей (с тысячами итераций), чтобы снизить скорость хэширования злоумышленниками. 3) Используйте большую (от 32 до 64 бит) случайную соль. Радужные таблицы больше не могут быть предварительно вычислены, и эти вычисления не могут быть использованы для любой другой системы (если только они не используют одну и ту же соль). 4) Если возможно, используйте разные соли для каждой записи, таким образом, делая радужную таблицу полностью недействительной.

Answer 2

Все ответы в оригинальной статье.Прежде всего, вы должны увидеть, что вы должны сравнить одну радужную таблицу с t классическими таблицами, где t - количество элементов в цепочке.Действительно, каждый столбец в радужной таблице действует как одна классическая таблица (например, если у вас есть идентичные элементы в столбце радужной таблицы, у вас будет слияние, если у вас есть два идентичных элемента в классической таблице, у вас такжеслияния).Затем вы увидите, что для поиска в t классических таблицах вам понадобится t ^ 2 операций, если вам нужно просмотреть все таблицы (t таблиц с цепочками длины t).Если вы ищете в единственной радужной таблице, вам понадобится 1 + 2 + 3 + ... + t операций, что равно t ^ 2/2.Так что в худшем случае, когда вы не найдете пароль, вы будете в два раза быстрее.Теперь, если пароль отображается в среднем после того, как вы прошли половину таблиц или столбцов, он будет в 4 раза быстрее.Если вам нужна высокая вероятность успеха (например, 99%), то в среднем пароль уже будет отображаться после 10% таблицы, что сделает радужные таблицы в 20 раз быстрее.