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



Pdf көрінісі
бет183/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   179   180   181   182   183   184   185   186   ...   249
Криптография Катц

Безопасность AES. Как уже упоминалось, шифр AES подвергался тщатель-
ному изучению в процессе выбора и продолжает изучаться до сих пор. На се-
годняшний день не существует никаких практических криптоаналитических 
атак, которые значительно лучше, чем полный поиск ключа.
Мы пришли к выводу, что по состоянию на сегодняшний день AES представ-
ляет собой прекрасный выбор для любой криптографической схемы, которая 
требует (строгой) псевдослучайной перестановки. Этот шифр бесплатный, 
стандартизованный, эффективный и с высоким уровнем безопасности.
6.2.6 *Дифференциальный и линейный криптоанализ
Блочные шифры относительно сложны и сами по себе трудны для анализа. Тем 
не менее, не следует никого вводить в заблуждение, полагая, что сложный шифр 
трудно взломать. Наоборот, очень трудно создать безопасный блочный шифр и 
удивительно легко найти атаки на большинство конструкций (независимо от того, 
насколько сложными они представляются). Это должно служить предупреждени-
ем, что неспециалисты не должны пытаться создавать новые шифры. Учитывая 
доступность тройного DES и AES, трудно оправдать использование чего-то еще.
В этом разделе мы опишем два инструмента, которые теперь являются стан-
дартной частью набора инструментов криптоаналитика. В данном случае наша 
цель заключается в том, чтобы придать вкус некому расширенному криптоана-
лизу, а также подкрепить идею, что разработка безопасного блочного шифра 
включает в себя тщательный выбор его компонентов.
Дифференциальный криптоанализ. Этот метод, который может привести к 
атаке выбранного открытого текста на блочном шифре, был впервые представлен 
в конце 1980-х гг. Бихэмом (Biham) и Шамиром (Shamir), которые использовали 
его для атаки DES в 1993 г. Основная идея атаки заключается в том, чтобы пред-
ставить в табличной форме конкретные различия во входных данных, которые 
приводят к конкретным различиям в выходных данных с вероятностью большей, 
чем можно было бы ожидать от случайной перестановки. В частности, пусть 
дифференциал (∆x, ∆y ) появляется в некой ключевой перестановке F r с вероят-
ностью p , если для однородных входных данных x1 и x2, удовлетворяющих x1 

x2 = ∆x, и однородном выборе ключа k, вероятность того, что k (x1) ⊕ Fk (x2) =
∆y равна p. Для любого фиксированного (∆x, ∆y ) и x1, x2 , удовлетворяющих x1 

x2 = ∆x, если мы выбираем однородную функцию f : {0, 1}A → {0, 1}A, имеем 
Pr[f (x1) ⊕ f (x2) = ∆y ] = 2−A. В плохом блочном шифре, тем не менее, могут быть 
дифференциалы, которые возникают с существенно большей вероятностью. Это 


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


Достарыңызбен бөлісу:
1   ...   179   180   181   182   183   184   185   186   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет