190
прообразы с использованием O(22A/3) хэш-вычислений. Если используется хэш-
функция с 80
битами выходных данных, тогда это реализуемо на практике.
Обрабатывая разные область и диапазон. Естественным явлением на прак-
тике есть попадание в ситуацию, в которой область и диапазон H разные. Один
из примеров лежит в контексте взлома паролей (см. Раздел 5.6.3), когда атаку-
ющий имеет H(pw), но |pw| A. В общем случае, скажем, x выбран из какой-то
области D, которая может быть больше или меньше, чем {0, 1}A. И хотя, конеч-
но же, есть возможность искусственно расширить область/диапазон, чтобы их
размеры совпадали, это не будет полезным для атаки, описанной выше.
Чтобы
понять почему, рассмотрим пример с паролем. Чтобы атака прошла успешно
мы хотим, чтобы pw находился в какой-то таблице значений, сгенерированных
во время предварительной обработки. Если мы сгенерируем каждую строку та-
блицы простым вычислением H(SP ), H(2)(SP ), . . . для SP ∈ D, тогда ни одно из
этих значений (кроме,
возможно, самой SP ) не будет равняться pw.
Мы можем добиться этого, применив функцию Fi, как и ранее, между каждым вы-
числением H, хотя сейчас мы выбираем Fi, преобразовывая {0, 1}A в D. Это
решает
вышеописанную проблемы, так как Fi(H(SP )), (Fi ◦ H)(2)(SP ), . . . теперь все лежат в D.
Применения к атакам на восстановление ключа. Компромиссы времени/
пространства производят атаки и на криптографические примитивы, которые
не являются хэш-функциями. Одно каноническое применение, по сути, приме-
нение изначально рассматриваемое Хеллманом, - это атака на произвольный
блочный шифр F, которая ведет к восстановлению ключа. Определите H(k)
Fk(x), где x - это какой-то произвольный, но фиксированный входной элемент,
который будет использоваться для построения таблицы. Если атакующий смо-
жет получить Fk (x) для неизвестного ключа k, то ли посредством атаки на осно-
ве подобранного открытого текста, то ли посредством подбора x так, чтобы Fk
(x) было получено скорее при помощи атаки на основе открытых текстов, тогда
инвертированием H атакующий узнает (возможное значение для) k. Обратите
внимание, что длина ключа F , возможно, отличается от длины своего блока, но
в этом случае мы можем использовать метод, описанный выше, для обработки
H с разными областью и диапазоном .
Достарыңызбен бөлісу: