ТЕОРЕМА 6.5 Если F моделируется в качестве идеального шифра, то кон-
струкция Мейера-Дэвиса дает устойчивую к коллизиям функцию сжатия. Точ-
нее, любой взломщик, делая q < 2A/2 запросов к прогнозам идеального шифра
обнаруживает коллизию с вероятностью, чаще всего, q2/2A.
ДОКАЗАТЕЛЬСТВО Чтобы было ясно, мы рассмотрим здесь вероятностный
эксперимент, в котором F отбирается случайным образом (точнее, для каждого k
∈
{0, 1}n функция F (k, •) : {0, 1}A → {0, 1}A выбирается равномерно из множе-
ства PermA перестановок A-битных строк) а затем взломщик получает доступ к
прогнозу F и F −1. Взломщик пытается затем найти пару с коллизией (k, x), (kr, xr),
т.е. для которой F (k, x)⊕ x = F (kr , xr)⊕ xr. Никакие вычислительные ограничения
не действуют на взломщика кроме ограничения количества запросов прогноза,
которые он делает. Скажем, предполагаем, что если взломщик выводит пары с
коллизией (k, x), (kr , xr), то он предварительно сделал запросы прогноза, необхо-
димые для вычисления значений F (k, x) и F (kr, xr). Мы также предполагаем, что
взломщик никогда не делает один и тот же запрос более, чем один раз и никогда
не запрашивает F −1(k, y), если уже узнал, что y = F (k, x) (и наоборот). Все эти
предположения сделаны без ограничения общности.
Рассмотрим i-й запрос взломщика, сделанный по его прогнозам. Запрос (ki,
xi)к F показывает только значение хэш-функции hi h(ki, xi) = F (ki, xi) ⊕
xi; аналогично, запрос к F −1 , дающий результат xi = F −1(ki, yi), дает только
значение хэш-функции hi h(ki, xi) = yi ⊕ F −1(ki, yi). Взломщик не получит
коллизии кроме hi = hj для некоторых i ƒ= j.
Зафиксируем i, j при i > j и рассмотрим вероятность того, что hi = hj . Во время
i-го запроса значение hj зафиксировано. Коллизия между hi и hj получается на
i-м запросе, только если взломщик обращается с запросом (ki, xi) к F и получает
результат F (ki, xi) = hj ⊕ xi, или обращается с запросом (ki, yi) к F −1 и получает
257
результат F −1(ki, yi) = hj ⊕ yi. Либо событие происходит с вероятностью, чаще всего,
1/(2A − (i − 1)) поскольку, например, F (ki, xi) равномерна по {0, 1}A, за исключени-
ем того, что она не может быть равна любому значению F (ki, x) уже определенному
взломщиком (чаще всего) i − 1 предыдущими запросами прогноза с использованием
ключа ki. Поскольку i ≤ q < 2A/2, вероятность того, что hi = hj чаще всего равна 2/2A.
Принимая границу объединения по всем .q/2. < q2/2 различным парам i, j дает
результат, указанный в теореме.
Достарыңызбен бөлісу: |