181
каждой i мы предположим, что значение yi = H(xi) равномерно аспределено
в {0, 1}A и независимо от любых предыдущих выходных значений {yj }j
(вспомним, как мы предполагали, что все {xi} различны). Таким образом, мы
уменьшили нашу проблему до следующей: если мы выберем значения y1, . . . ,
yq ∈ {0, 1}A единообразно по случайному принципу, какова будет вероятность,
что имеют место различные i, j при yi = yj ?
Данная проблема была внимательно изучена и отнесена к так называемой про-
блеме «дней рождения», подробно описанной в Дополнении A.4. По этой причине
алгоритм нахождения коллизий, который мы описали, часто зовется атакой «дней
рождений». Проблема «дней рождений» заключается в следующем: если в комнате
находится q людей, какова вероятность того, что у двоих из них день рождения в
один и тот же день (Предположим, что дни рождения равномерно распределены по
периоду в 365 дней невисокосного года.) Это аналогично нашей проблеме:
если yi
представляет день рождения человека i, тогда мы имеем y1, . . . , yq ∈ {1, . . . , 365},
выбранные единообразно, и совпадающие дни рождения соответствуют различ-
ным i, j при yi = yj (то есть совпадающие дни рождения соответствуют коллизиям).
В Дополнении A.4 мы показываем, что для y1, . . . , yq, выбранных единоо-
бразно в {1, . . . , N }, вероятность коллизиии приблизительно 1/2, если q = Θ(N
1/2). В случае с дням и рождения, если имеется всего 23 человека, вероятность
того, что у двоих из них день рождение выпадет на одну и ту же дату больше,
чем 1/2. В нашем условии это означает, что если хэш-функция имеет выходную
длину A (и поэтому диапазон будет размером 2A), то принимая q = Θ(2A/2), вы-
даст коллизию с вероятностью примерно 1/2.
С точки зрения конкретной защиты вышеописанное означает, что для хэш-
функции, чтобы противостоять атакам нахождения коллизии, которые действу-
ют в течение времени T (где мы берем время, чтобы определить H в качестве
нашей единицы времени), выходная длина хэш-функции должна быть как ми-
нимум 2 log T бит (так как 2(2 log T )/2 = T). Принимая специфические параме-
тры, это означает, что если мы хотим, что нахождение коллизий было настолько
же трудным, насколько истощающим является поиск по 128-битным ключам,
тогда нам необходимо, чтобы выходная длина хэш-функции была как минимум
256 бит. Мы подчеркиваем, что выходные данные такой длины - это единствен-
ное необходимое условие, но не достаточное. Мы также отмечаем, что атаки
«дней рождения» работают только для нахождения коллизий. Не существует
типичных атак
__________________________________________________________
1Можно увидеть, что это (в значительной степени)
наихудший случай, и коллизии случаются
с более высокой вероятностью, если H отколняется от случайного, и {xi} выбираются единоо-
бразно.
182
для стойкости второго прообраза или стойкости прообраза хэш-функций H, ко-
торые требуют менее чем 2A оценок H (впрочем см. Раздел 5.4.3).
Нахождение значимых коллизий . Атака «дней рождения», описанная выше,
дает коллизию, которая не обязательно очень полезная. Но та же идея может
быть использована, чтобы найти и «значимые» коллизии. Предположим, Али-
са желает найти два сообщения x и xr так, чтобы H(x) = H(xr), и, более того,
x должно быть письмом от ее работодателя, объясняющего, почему она была
уволена с работы, тогда как xr должно быть преувеличенное рекомендательное
письмо. (Это должно позволить Алисе подделать соответствующий тег на реко-
мендательное письмо, если ее работодатель использует подход хэш-и-MAC для
аутентификации сообщений.) Очевидно, что атака «дней рождения» потребует
только, чтобы входные данные хэша x1, . . . , xq были различные; им не обяза-
тельно быть случайными. Алиса может выполнить атаку по типу «дней рожде-
ния» путем генерирования q = Θ(2A/2) сообщение первого типа и q сообщений
второго типа и затем поиска коллизий между сообщениями двух типов. Неболь-
шое изменение анализа из Дополнения A.4 показывает, что это дает коллизию
между сообщениями различных типов с вероятностью приблизительно 1/2. Не-
много размышлений, и очевидно, что легко написать одно и то же сообщение
многими различными способами.
Например, рассмотрите следующее:
Это тяжело/трудно/затруднительно/невозможно представить/вооб-
разить, что мы найдем/пригласим/наймем другого работника/сотруд-
ника, который обладает теми же качествами/навыками/способностя-
ми, что и Алиса. Она сделала прекрасную/превосходную работу.
Любая комбинация слов, выделенных курсивом, возможна и выражает одну
и ту же точку зрения. Таким образом, предложение может быть написано 4 • 2
• 3 • 2 • 3 • 2 = 288 различными способами. Это всего лишь одно предложение,
и поэтому на самом деле легко сгенерировать сообщение, которое может быть
переписано 264 различными способами, все, что нужно - это 64 слова с одим
синонимом для каждого. Алиса может приготовить 2A/2 письма, объясняющие,
почему она была уволена и еще 2A/2 реко мендательных письма; с высокой
вероятностью между двумя типами писем будет найдена коллизия.
Достарыңызбен бөлісу: