Атаки «дней рождения « малого пространства

183
Более того, всегда можно позволить вычислению работать автономно, в то же 
время требования алгоритма к памяти должны быть удовлетворены сразу же, 
как эта память потребуется.
Мы покажем здесь более продвинутую атаку «дней рождения» с существенно 
уменьшенными требованиями к памяти. В действительности, она имеет такую 
же временную сложность и вероятность успеха, как и прежняя, однако исполь-
зует только постоянный объем памяти. Атака начинается с подбора случайного 
значения x0 и вычисления xi := H(xi−1) и x2i := H(H(x2(i−1))) для i = 1, 2, . . .. 
(Обратите внимание, что xi = H(i)(x0) для всех i, где H(i) ссылается на i-кратную 
итерацию H.) На каждом шаге значения xi и x2i сравниваются; если они идентич-
ны, значит коллизия происходит где-то в последовательности x0, x1, . . . , x2i−1. 
Затем алгоритм находит наименьшее значение j , для которого xj = xj+i (обратите 
внимание, что j ≤ i, так как j = i работатет) и выводит xj−1, xj+i−1 в качестве колли-
зии. Данная атака, описанная формально как Алгоритм 5.9 и проанализированная 
ниже, требует только хранилища для двух хэш-значений при каждой итерации.
АЛГОРИТМ 5.9
Атака "дней рождения" малого пространства
Вход: Хэш-функция H : {0, 1 }* → {0, 1 }A 
Выход: Различные x, xr при H(x) = H(xr)
Сколько итераций первого круга мы прогнозировали ранее xr = x? РАссмотрите по-
следовательность значений x1, x2, . . ., где xi = H(i)(x0), как было определено ранее. Есл 
и мы смоделируем H в качестве случайной функции, каждое из этих значений будет 
равномерно и независимо распределяться в {0, 1}A, пока не случится первый повтор.
Таким образом, мы ожидаем, что повтор случится с вероятностью 1/2 в первых q = 
Θ(2A/2) членах последовательности. Мы покажем, что повтор случится в первых q 
элементах, алгоритм найдет повтор в максимум q итерациях первого круга:

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

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