Введение в современную криптографию

248
может быть использовано, чтобы обеспечить атаку с полным восстановлением 
ключа, как мы сейчас наблюдаем для сетей с защитой от несанкционированного 
доступа (SPN - subscriber-protected network).
Мы опишем основную идею, а затем проработаем ее на конкретном при-
мере. Пусть F будет блочным шифром с A-битной длиной блока, который 
является r-раундовой сетью SPN и допустим, что k (x) означает промежу-
точный результат в расчете Fk (x) после применения этапа ключевого сме-
шивания раунда r. (Т.е., F r исключает подстановку S-блока и перемешива-
ющей перестановки последнего раунда, а также этап итогового ключевого 
смешивания). Допустим, имеется дифференциал (∆x, ∆y ) in F r , который 
появляется с вероятностью p 2−A. Можно использовать этот дифферен-
циал с высокой вероятностью, чтобы узнать биты вспомогательного ключа 
итогового смешивания kr+1. Идея высокого уровня следующая: пусть {(xi 
, xi )}L будет набором L пар случайных входных данных с дифференциалом 
∆x, т.е., с xi ⊕ xi = ∆x для всех i. Используя атаку подобранного открытого 
текста, получим значения yi= Fk (xi ) и yi= Fk (xi ) для всех i. Теперь, для 
всех возможных строк битов k∈ {0, 1}A, вычислим y˜i = F r (xi ) и y˜i = F r 
(xi ), предполагая, что итогового вспомогательного ключа kr+1 равно k*. Это 
делается инвертированием итогового ключа смешивания с использованием 
k*, а затем инвертирования смешивающей перестановки и S-блоков раунда 
r, которые не зависят от мастер-ключа. Когда k* = kr+1, мы предполагаем, 
что доля p пар будет удовлетворять y˜i ⊕ y˜i = ∆y . С другой стороны, когда 
k* ƒ= kr+1 мы эвристически можем ожидать только 2−A-долю пар, чтобы 
получить этот дифференциал. При задании L достаточно большим можно 
определить правильное итоговое значение вспомогательного ключа kr+1 .
Это работает, но не очень эффективно, поскольку на каждом шаге мы пе-
речисляем более 2A возможных значений. Можно сделать это лучше, одно-
временно угадав части kr+1 . Более конкретно, предположим, что S-блоки 
в F имеют длину ввода/вывода 1 байт, и сосредоточимся на первом байте 
∆y , который, как мы предполагаем, отличен от нуля. Можно проверить, со-
держит ли дифференциал в этом байте только 8 битов kr+1, а именно те 8 
битов, которые соответствуют (после раунда r смешивающей перестановки) 
выходным данным первого S-блока. Таким образом, действуя как указано 
выше, мы можем изучать эти 8 бит путем перечисления по всем возможным 
значениям для этих битов, и видеть, какое значение дает искомый диффе-
ренциал в первом байте с наибольшей вероятностью. Неверные прогнозы 
для этих 8 битов дают ожидаемый дифференциал в этом байте с (эвристи-
ческой) вероятностью 2−8, но правильный прогноз даст ожидаемый диффе-
ренциал с вероятностью примерно p +2−8; это потому, что с вероятностью 

249
p дифференциал имеется на всем блоке (так, в частности, для первого байта) 
и, если это не так, то мы можем рассматривать дифференциал в первом байте 
как случайный. Обратите внимание, что различные дифференциалы могут по-
требоваться, чтобы изучить различные части kr+1.
На практике различные оптимизации выполняются, чтобы улучшить эффектив-
ность указанного выше теста, или, более конкретно, чтобы увеличить разрыв между 
вероятностью того, что неправильный прогноз дает дифференциал в зависимости 
от вероятности того, что дает правильный прогноз. Одна оптимизация заключается 
в использовании дифференциала с низким весом, в которой Δy имеет много нуле-
вых байтов в позициях, которые входят в S-блоки в раунде r. Любые пары y˜1, 
y˜2, удовлетворяющие такой дифференциал, имеют равные значения, входящие в 
множество S-блоков в раунде r, и это приведет к выходным значениям y1, y2, кото-
рые равны в соответствующих позициях битов (в зависимости от заключительной 
смешивающей перестановки). Это означает, что при выполнении теста, описанного 
ранее, можно просто отказаться от любых пар (yi , yi ), которые не согласуются в 
этих позициях битов (поскольку соответствующие промежуточные значения (y˜1, 
y˜2), вероятно, не могут удовлетворить дифференциал для любого выбора итого-
вого вспомогательного ключа). Это значительно повышает эффективность атаки.
Если kr+1 известно, то взломщик может отменить заключительный этап сме-
шивания ключа, а также смешивающую перестановку и этапы подстановки 
S-блока раунда r (поскольку они не зависят от мастер-ключа), а затем приме-
нить ту же атаку, используя отличающийся дифференциал, чтобы найти вспо-
могательный ключ kr r-го раунда, и т.д. до тех пор, пока не узнает все вспомога-
тельные ключи (или, что то же самое, весь мастер-ключ).

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

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