Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| РИС. 6.9: Дифференциалы в нашем S-блоке.
Этот же процесс можно выполнить для всех 24 входных разностей ∆x , чтобы вычислить вероятность каждого дифференциала. А именно, для каждой пары (∆x, ∆y ) мы заносим в таблицу количество 4-битных входов x, для которых S(x) ⊕ S(x ⊕ ∆x) = ∆y . Мы сделали это для S-блока нашего примера на рис. 6.9. (Для краткости мы представим (∆x, ∆y ), используя шестнадцатеричную запись). Та- блицу нужно читать следующим образом: запись (i, j) подсчитывает, сколько входных данных с разностью i отображается в выходных данных с разностью j. Заметим, например, что имеется 8 входов с разностью 0xF = 1111, которая отображается на выходе 0xA = 1010, как мы показали выше. Это наиболее ве- роятный дифференциал (за исключением тривиального дифференциала (0, 0)). Но существуют другие интересные дифференциалы: входная разность 0x4 = 0100 отображается на выходной разности 0x6 = 0110 с вероятностью 6/16 = 3/8, и есть несколько дифференциалов с вероятностью 4/16 = 1/4. РИС. 6.10: Дифференциалы трассировки через четыре раунда SPN, в которой используется S-блок и смешивающая перестановка, приведенная в тексте. 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 достаточно боль- шим, мы можем (с высокой вероятностью) определить правильное значение. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|