Введение в современную криптографию

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 с разными областью и диапазоном .

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: