Как работает функция сокращения, используемая с радужными таблицами?

Question

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

Я не понимаю - в чем смысл отображенияэто даже не инверсия хэш-функции?Как такое сопоставление должно практически работать и помогать в выводе пароля?

Answer 1

Радужный стол - это «просто» умный метод сжатия для большой таблицы предварительно вычисленных хэшей. Идея состоит в том, что таблица может «инвертировать» выходные данные хэша, если и только если соответствующий вход был рассмотрен во время построения таблицы.

Каждая строка таблицы («цепочка») представляет собой последовательность вызовов хеш-функций. Хитрость в том, что каждый вход вычисляется детерминистически из предыдущего выхода в цепочке, так что:

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

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

Answer 2

Причина, по которой функция сокращения не является инверсией хэша, заключается в том, что истинная инверсия хэша не была бы функцией (помните, что для фактического определения «функции» требуется один выход для одного входа).

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

Функция сокращения, используемая большинством радужных таблиц, заключается в «хранении самой короткой строки, имеющей этот хэш».

Answer 3

Неважно, если он выдаст пароль : то, что вы получите, будет также работать как пароль, и вы сможете войти с ним так же, как и с оригинальным паролем.