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

186
любой точки отсчета x (обратите внимание, что большинство функций не опреде-
ляют цикл, но мы предположим такое, чтобы продемонстрировать идею на очень 
простом случае). Для ясности, пусть N = 2A обозначает размер области.
В фазе предварительной обработки атакующий просто завершит внутренний цикл, 
начиная с произвольной точки отсчета x0 и вычисляя x1 := H(x0), x2 := H(H(x0)) вплоть 
до xN = H(N )(x0), где H(i) ссылается i-кратное определение H. Пусть xi H(i)(x0). 
Представим разделение цикла на √N сегментов длиной √N каждый, and having the
attacker store the points at the beginning и конец каждого такого сегмента. То есть атаку-
ющий хранит в таблице пары формы (xi•√N , x(i+1)•√N ) для i = 0 до √N-1, отсортиро-
ванные по второму компоненту каждой пары. Итоговая таблица содержит O(√N) точек.
Когда атакующий получает точку y , чтобы инвертировать в онлайн фазу, он про-
веряет, какая из y, H(y), H(2)(y), . . . соответствует конечной точке сегмента. (Каждая 
проверка всего лишь задействует поиск по таблице второго компонента хранящей-
ся пары.) Так как y лежит в каком-то сегменте, конечная точка будет гарантировано 
найдена за √N шагов. После того, как конечная точка xr = x i√Nидентифицирована, 
атакующий берет начальную точку xr = xi•√N соотвествующего сегмента 
РИСУНОК 5.3: Генерирование таблицы. Хранятся только пары (SPi, EPi).
и вычисляет H(xr), H(2)(xr), . . ., пока не достигается y; что мгновенно дает ис-
комый прообраз. Заметьте, что на это уходит максимум √N определений H. В 
итоге, такая атака хранит O (√N) точек и находит прообраз с вероятность 1, ис-
пользуя O(√N) хэш-вычислений.
Компромисс времени/пространства Хеллмана. Мартин Хеллман предста-
вил более общий компромисс времени/пространства, применимый к произвольной 
функции H(хотя анализ считает H соучайной функцией). Атака Хеллмана все еще 
хранит начальную точку и конечную точку нескольких сегментов, но в данном случае 
сегменты скорее «независимы», чем часть одного большого цикла. Более подробно: 
пусть s, t будут параметрами, которые мы зададим позже. Атака для начала подбирает 
s одинаковых начальных точек SP1, . . . , SPs ∈{0, 1}A. Для каждой такой точки SPi она 
вычисляетсоответсвующую конечную точку EPi := H(t)(SPi) при помощи t-кратного 
примененияH. (См. Рисунок 5.3.) Затем атакующий хранит значения {(SPi, EPi)}s в 

187
таблице, отсортированной по второй записи каждой пары.
По получении y для инвертирования, атака продолжается так, как в простом 
случае, описанном ранее. В частности, она проверяет, является ли какое-либо 
из значений y, H(y), . . . , H(t−1)(y) равной конечной точке одного из сегментов 
(останавливаясь как только первое из таких совпадений будет найдено). Воз-
можно такое, что ни одно из этих значений не будет равно конечной точке (что 
мы обсудим ниже). Однако, если H(j)(y) = EPi = H(t)(SPi) для некоторых i, j, 
тогда атакующий вычисляет H(t−j−1)(SPi) и проверяет, является ли это прооб-
разом y. Весь процесс требует максимум t определений H.
Вроде бы, это работает, но есть ряд тонкостей, которые мы игнорируем. Во-
первых, может случится, что ни одно из значений y, H(y), . . . , H(t−1)(y) не явля-
ется конечной точкой сегмента. Такое может случиться, если y не находится в 
коллекции значений s • t (не считая начальную точку), полученных во время на-
чального процесса генерирования таблицы. Мы можем установить s • t ≥ N в по-
пытке включить каждую A-битную строку в таблицу, но это не решает проблему, 
так как могут случаться коллизии в самой таблице, фактически, из-за s • t ≥ N 1/2 
наш предыдущий анализ проблемы «дней рождений» подсказывает нам, что ве-
роятны коллизии, которые уменьшат количество разных точек в коллекции значе-
ний. Во-вторых, проблема, которая возникает, даже еслиy присутствует в таблице, 
заключается в том, что даже если мы найдем совпадающюю конечную точку, и 
таким образом H(j)(y) = EPi = H(t)(SPi) для некоторых i, j, это не гарантирует, 
что H(t−j−1)(SPi) - это прообраз y. Проблема в том, что сегмент y, H(y), . . . , H(t−1)
(y) мог бы столкнуться с сегментом i, даже если y сам по себе не находится в этом 
сегменте; см. Рисунок 5.4. (Даже если y лежит в каком-то сегменте, первая совпа-
дающая конечная точка может находится не в этом сегменте.) Мы называем это 
ложное срабатывание. Можно подумать, что это маловероятно, если H является 
стойкой к коллизиям; и нова, однако, мы имеем дело с ситуацией, когда задейство-
вано более √N точек, и поэтому коллизии становятся более вероятным явлением.

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

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