252
Теперь продолжим это, чтобы найти хороший
дифференциал для первых
трех раундов SPN. Рассмотрим оценку SPN на двух входах, которые имеют
дифференциал 0000 1100 0000 0000, и проследим дифференциал между про-
межуточными значениями на каждом этапе этой оценки. (См. рис. 6.10, на кото-
ром показаны четыре полных раунда SPN плюс этап заключительного ключе-
вого смешивания.
Для ясности, на рис. опущена смешивающая перестановка
в 4-ом раунде; эта смешивающая перестановка влияет только на перетасовку
битов дифференциала, и поэтому может быть легко учтена при атаке). Этап
ключевого смешивания в первом раунде не влияет на дифференциал и поэтому
входы для второго S-блока в первом раунде имеют дифференциал 1100. Из рис.
6.9. видно, что разность 0xC = 1100 во входных данных для S-блока дает раз-
ность 0x8 = 1000 в выходных данных S-блока с вероятностью 1/4. Таким обра-
зом, с вероятностью 1/4 дифференциал в выходных данных 2-го S-блока после
раунда 1 является одиночным битом, который при смешивающей перестановке
перемещается с 5-ой позиции в 12-ю позицию. (Входные данные для других
S-блоков равны, поэтому их выходные данные равны и дифференциалы на вы-
ходах равны 0000). Если предположить, что это так, то входная разность для
третьего S-блока во втором раунде равна 0x1 = 0001 (опять же, этап ключевого
смешивания во втором раунде не влияет на дифференциал); используя рис. 6.9,
имеем, что с вероятностью 1/4 выходная разность от этого S-блока равна 0x4 =
0100.
Таким образом, опять же имеется только единственный выходной бит,
который отличается, и он перемещается из 10-й позиции в первую позицию при
смешивающей перестановке. И наконец, сверившись еще раз с рис. 6.9, видим,
что входная разность 0x8 = 1000 для S-блока дает в результате выходную раз-
ность 0xF = 1111 с вероятностью 1/4. Биты в позициях 1, 2, 3 и 4 затем переме-
щаются при смешивающей перестановке в позиции 7, 2, 3 и 8.
В целом, мы далее видим, что входная разность ∆x = 0000 1100 0000 0000 дает
выходную разность ∆y = 0110 0011 0000 0000 после трех раундов с вероятностью
минимум 1/4•1/4 •1/4= 1/64•7 (Мы перемножаем вероятности, поскольку эври-
стически предполагаем независимость каждого раунда). Для случайной функци-
ивероятность того, что появляется любой данный дифференциал равна только
2−16=1/65536. Таким образом, дифференциал, который мы нашли, появляется
с вероятностью существенно выше, чем можно было бы ожидать для случайной
функции.
Заметим также, что мы нашли дифференциал с низким весом.
Мы можем использовать этот дифференциал, чтобы найти первые 8 битов
итогового вспомогательного ключа k5.
Как обсуждалось ранее, начнем, пред
___________________________________________________________
7 Это нижняя граница вероятности дифференциала, поскольку могут существовать другие
разности в промежуточных значениях, которые приведут к той же разности в выходных данных.
253
ставляя, что {(xi , xi )}L является множеством L пар
случайных входных данных с
дифференицалом ∆x. Используя атаку подобранного открытого текста, мы затем по-
лучим значения yi = Fk (xi ) и yi = Fk (xi ) для всех i. Теперь, для всех возможных значе-
ний для начальных 8 битов k5 мы вычислим начальные 8 битов y˜i , y˜i промежуточ-
ные значения после этапа ключевого смешивания 4-го раунда. (Мы можем делать это
потому, что нам нужно только инвертировать два крайних левых S-блока 4-го раунда,
чтобы получить эти 8 битов). Если мы угадаем правильное значение для начальных 8
битов k5, то мы можем ожидать, что 8-битный дифференциал 0110 0011 появляется с
вероятностью минимум 1/64. Эвристически неправильный прогноз дает ожидаемый
дифференциал только с вероятностью 2−8 = 1/256. При задании L достаточно боль-
шим, мы можем (с высокой вероятностью) определить правильное значение.
Достарыңызбен бөлісу: