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-го раунда, и т.д. до тех пор, пока не узнает все вспомога-
тельные ключи (или, что то же самое, весь мастер-ключ).
Достарыңызбен бөлісу: