Как работает функция сокращения, используемая с радужными таблицами?
Я внимательно прочитал о радужных столах и не могу ничего понять. Для построения цепочки хеширования используется функция сокращения. Это функция, которая каким-то образом отображает хэши на пароли. В этой статье говорится, что функция сокращения - это не инверсия хеша, а просто отображение.
Я не понимаю - какая польза от отображения, которое даже не является инверсией хэш-функции? Как такое сопоставление должно работать на практике и помочь в получении пароля?
3 ответа
Радужный стол - это "просто" умный метод сжатия для большой таблицы предварительно вычисленных хэшей. Идея состоит в том, что таблица может "инвертировать" выходные данные хеш-функции, если и только если соответствующий вход был рассмотрен во время построения таблицы.
Каждая строка таблицы ("цепочка") представляет собой последовательность вызовов хеш-функций. Хитрость в том, что каждый вход вычисляется детерминистически из предыдущего вывода в цепочке, так что:
- сохраняя начальную и конечную точки цепочки, вы "морально" сохраняете всю цепочку, которую вы можете восстановить по желанию (именно здесь радужный стол можно рассматривать как метод сжатия);
- Вы можете начать перестройку цепочки с вывода хеш-функции.
Функция сокращения - это клей, который превращает вывод хеш-функции в соответствующий ввод (например, строка символов, которая выглядит как подлинный пароль, состоящий только из печатных символов). Его роль в основном заключается в возможности генерировать возможные входные данные хеш-функции с более или менее равномерной вероятностью, учитывая случайные данные для работы (и выходные данные хэш-функции будут приемлемо случайными). Функция сокращения не должна иметь какой-либо конкретной структуры, в частности, в отношении того, как работает сама хэш-функция; функция сокращения должна просто позволять продолжать строить цепочку, не создавая слишком много ложных столкновений.
Причина, по которой функция сокращения не является инверсией хэша, состоит в том, что истинная инверсия хэша не была бы функцией (помните, что для фактического определения "функции" требуется один выход для одного входа).
Хеш-функции создают строки, которые короче, чем их соответствующие входные данные. По принципу квадратного отверстия это означает, что два входа могут иметь одинаковый выход. Если можно хэшировать произвольно длинные строки, на самом деле бесконечное число строк может иметь одинаковый результат. Тем не менее, радужный стол обычно содержит только один вывод для каждого хеша, поэтому он не может быть истинным обратным.
Функция сокращения, используемая большинством радужных таблиц: "сохранить самую короткую строку, имеющую этот хэш".
Неважно, будет ли он выдавать пароль: то, что вы получите, будет работать как пароль, и вы сможете войти с ним так же, как и с оригинальным паролем.