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 точек, и поэтому коллизии становятся более вероятным явлением.
Достарыңызбен бөлісу: