rijndael (Курсовая - Построение и исследование криптосистемы на основе Rijndael), страница 4

Мы рассмотрим построение линейногоприближения, содержащего биты открытого текста X и биты входа последнему раунда Y . (То есть мы рассматриваем те же объекты, что и в дифференциальном криптоанализе.)Уравнение (1) может быть повторно сформулировано, чтобы формальнозависеть от ключа. Для этого предположим, что правая сторона уравненияявляется суммой бит подключа.

Это можно сделать, так как ключ постоянный, и любая сумма его комбинации бит равняется 0 или 1 и не зависит от Xи Y . Однако, в уравнении (1) с правой стороны стоит 0. Поэтому будем считать, что если сумма бит подключа равняется 0, то уравнение будет иметь тоже самое отклонение ε (знак сохраниться). В противном случае, отклонениеε просто изменит знак на противоположный.Обратим внимание, если pL = 1, то это подразумевает, что шифр имееткатастрофическую слабость.

Если pL = 0, то это также признак катастрофической слабости.Чтобы построить линейные приближения, которые имеют высокую эффективность соотношения и, следовательно, могут использоваться в линейном криптоанализе, рассматрим сначала свойства единственного нелинейногокомпонента шифра: S-блока. Для него можно построить линейные приближения между наборами бит его входа и выхода.Следовательно, возможно связать линейные приближения S-блоков вместе так, чтобы промежуточные биты сократились, и мы полчили бы линейноеприближение, которое имеет большую эффективность и содержит только биты открытого текста и биты входа последнего раунда.173.2.2 Линейный анализ S-блока.Перед рассмотрением атаки на полный шифр, сначала получим знания об линейной уязвимости S-блока.

Рассмотрим S-блок со входом X = [X1 X2 X3 X4 ]и соответствующим выходом Y = [Y1 Y2 Y3 Y4 ]. Все линейные приближениямогут быть исследованы, чтобы определить их пригодность для линейногоанализа, вычисляя для каждого отклонение. Следовательно, мы просмотримвсе выражения вида (1), где X и Y — вход и выход S-блока, соответственно.Рассмотрим общий вид линейного выражения для S-блокаa1 X1 ⊕ a2 X2 ⊕ a3 X3 ⊕ a4 X4 ⊕ b1 Y1 ⊕ b2 Y2 ⊕ b3 Y3 ⊕ b4 Y4 = 0,где ai ∈ {0, 1}, bi ∈ {0, 1}.

Наборы коэффициентов ai и bi называются “суммойвхода” и “суммой выхода”, соответственно. Они показывают какие биты входаи выхода присутствуют в конкретном линейном выражении. Их также удобнозаписывать в шестнадцатиричном виде. Например, если сумма входа и суммавыхода равны 6 и B, то линейное выражение имеет следующий видX2 ⊕ X3 ⊕ Y1 ⊕ Y3 ⊕ Y4 = 0.Полное перечисление всех линейных приближений S-блока в нашем криптоалгоритме приведено в таблице 2. Каждый элемент в таблице представляет число выполнения линейного выражения заданного суммой входа (строкатаблицы) и суммой выхода (столбец таблицы) минус 8. Следовательно, поделив это число на 16, результат даст нам значение отклонения данноголинейного выражения.0123456789ABCDEF0+8000000000000000100-40-4000+400000-4020+20+20+60-20-20-20+20+230-60-20+20-20+20-20+20-240+2-20+200-20+2+60+200-250+2+20-200-2-4+2-20+20-4-2600-2-2+2+2000+4-2+2+2-20+4700-2+2+2-20000-2-6+2-2008 9 A B C D E F0 0 0 0 0 0 0 00 0 -2 -2 -2 -2 0 0-4 0 0 0 -2 +2 +2 +20 0 +2 +6 0 0 -2 +2-4 0 0 0 +2 -2 -2 -20 0 -2 +2 0 0 +2 -20 +8 0 0 0 0 0 00 0 -6 +2 +2 +2 0 0-4 0 0 0 -4 0 0 00 0 -2 +2 -2 -2 0 +40 0 0 0 +2 +2 +2 +20 0 +2 +2 0 0 -2 -20 0 0 0 -2 +6 -2 -20 0 -2 -2 0 0 -6 +2+4 0 0 0 -4 0 0 00 0 +2 -2 +2 +2 0 +4Таблица 2.

Линейные приближения для S-блока.3.2.3 Построение линейного приближения.Как только была собрана информация о линейных приближениях для Sблока, мы можем начать построение линейных приближений полного шифра.18Это достигается путем связывания соответствующих линейных приближенийS-блоков. Построение линейного приближения, содержащего биты открытоготекста и биты входа последнего раунда, дает возможность напасть на шифр,извлекая биты подключа последнего раунда. Рассмотрим детально построение линейного приближения для нашего криптоалгоритма.В нашем построении мы будем использовать два линейных приближенияS-блока.X2 ⊕ X3 ⊕ Y1 ⊕ Y4 = 0X1 ⊕ X4 ⊕ Y2 ⊕ Y3 = 0, с вероятностью 16/16 и отклонением + 8/16;, с вероятностью 12/16 и отклонением + 4/16.Пусть Xm = [a0 .

. . a31 ] и Ym = [b0 . . . b31 ] будут теперь суммой входаи суммой выхода нашей системы, имеющих длину 32 бит. Записывать ихзначения будем в виде 8 шестнадцатиричных цифр. Зададим значение дляXm равное [09 09 09 09], которое соответствует линейной комбинации битвходной последовательностиx4 ⊕ x7 ⊕ x12 ⊕ x15 ⊕ x20 ⊕ x23 ⊕ x28 ⊕ x31 ,и по которому требуется определить значение для Ym .По аналогии с дифференциальным криптоанализом, подробно исследуемдействие каждого преобразования на приближение. Обозначения для нихоставим прежние.Для начала возьмем преобразование AddRoundKey(), чтобы узнать влияние ключа. До преобразования X и Ki — это последовательности бит состояния и ключа раунда i, соответственно.

Тогда на выходе преобразованиямы получаем последовательность X ′ = X ⊕ Ki и линейное приближение(x4 ⊕ k4 ) ⊕ (x7 ⊕ k7 ) ⊕ (x12 ⊕ k12 ) ⊕ (x15 ⊕ k15 )⊕⊕(x20 ⊕ k20 ) ⊕ (x23 ⊕ k23 ) ⊕ (x28 ⊕ k28 ) ⊕ (x31 ⊕ k31 ) =3P= x′4 ⊕ x′7 ⊕ x′12 ⊕ x′15 ⊕ x′20 ⊕ x′23 ⊕ x′28 ⊕ x′31 =x′i·8+4 ⊕ x′i·8+7i=0Далее эта последовательность X поступает на вход нелинейного преобразования SB, на котором мы стараемся выбрать такие линейные приближенияS-блока, чтобы их можно было бы соединить между раундами. Этот выборнепосредственно влияет на вероятность и отклонение конечного приближения всего шифра.

В нашем случае выберем линейное приближение S-блокаX1 ⊕ X4 = Y2 ⊕ Y3 . После преобразования получаем последовательность X ′′и линейное приближение′3Xx′′i·8+5 ⊕ x′′i·8+6 =3Xi=0x′′i·8+5 ⊕ x′′i·8+6 +x′i·8+4 ⊕ x′i·8+7i=0i=0или3X3Xxi·8+4 ⊕ xi·8+7 = κ0 , где κ0 =i=0i=0Полученная комбинация выполняется с вероятностьюpL = 1/2 + 233X3Y14= 1/2 + .1632i=019ki·8+4 ⊕ ki·8+7 .Преобразование SR работает как перестановка индексов нашего приближения и в итоге получаем последовательность X ′′′ и линейное приближение(из-за симметричности оно остается прежним), вероятность которого не изменяется33XX′′′x′′′xi·8+4 ⊕ xi·8+7 = κ0 .⊕x+i·8+5i·8+6i=0i=0В преобразование MC следует подробно исследовать зависимость каждогобита на выходе от бит на входе преобразования.

Снова (как и в дифференциальном анализе) рассмотрим только первые два байта s0 = [α7 . . . α0 ] иs1 = [β7 . . . β0 ] состояния S. Тогда состояние Se равняетсяse0 = 02 • s0 ⊕ 03 • s1se1 = 03 • s0 ⊕ 02 • s1или более подробноse0 = se0 = αe7αe6αe5αe4αe3αe2αe1αe0βe7βe6βe5βe4βe3βe2βe1βe0     =          =     α6 ⊕ β6 ⊕ β7α5 ⊕ β5 ⊕ β6α4 ⊕ β4 ⊕ β5α3 ⊕ α7 ⊕ β3 ⊕ β4 ⊕ β7α2 ⊕ α7 ⊕ β2 ⊕ β3 ⊕ β7α1 ⊕ β1 ⊕ β2α0 ⊕ α7 ⊕ β0 ⊕ β1 ⊕ β7α7 ⊕ β0 ⊕ β7α6 ⊕ α7 ⊕ β6α5 ⊕ α6 ⊕ β5α4 ⊕ α5 ⊕ β4α3 ⊕ α4 ⊕ α7 ⊕ β3 ⊕ β7α2 ⊕ α3 ⊕ α7 ⊕ β2 ⊕ β7α1 ⊕ α2 ⊕ β1α0 ⊕ α1 ⊕ α7 ⊕ β0 ⊕ β7α0 ⊕ α7 ⊕ β7В нашем случае нужно получить выражение, зависящее от бит α2 , α1 , β2и β1 . Для этого рассмотрим линейную комбинацию бит αe2 ⊕ αe1 ⊕ βe2 ⊕ βe1 .αe2 ⊕ αe1 ⊕ βe2 ⊕ βe1 = (α1 ⊕ β1 ⊕ β2 ) ⊕ (α0 ⊕ α7 ⊕ β0 ⊕ β1 ⊕ β7 )⊕⊕(α1 ⊕ α2 ⊕ β1 ) ⊕ (α0 ⊕ α1 ⊕ α7 ⊕ β0 ⊕ β7 ) = α2 ⊕ α1 ⊕ β2 ⊕ β1В итоге, после преобразования получаем последовательность X ′′′′ и линейное приближение, вероятность которого по прежнему не изменяется3Xi=0x′′′′i·8+5⊕x′′′′i·8+6+3Xxi·8+4 ⊕ xi·8+7 = κ0 .i=0Далее снова следует преобразование AddRoundKey(), которое добавит кнашему приближению сумму определенных бит ключа K1 первого раунда.

И20пусть Y1 — последовательность бит состояния после этого преобразования.В результате, мы получаем линейное приближение первого раунда3Xy1,i·8+5 ⊕ y1,i·8+6 +i=0где3Xxi·8+4 ⊕ xi·8+7 = κ0 ⊕ κ1 ,i=0κ0 =3Xki·8+4 ⊕ ki·8+7 и κ1 =3Xk1,i·8+5 ⊕ k1,i·8+6 .i=0i=0вероятность которого равна pL = 1/2 + 1/32, а отклонение ε = +1/32.Проделав те же операции для второго раунда, получим линейное приближение первых двух раундов, которое и требовалось построить3Xyi·8+4 ⊕ yi·8+7 +i=0гдеκ0 =3X3Xxi·8+4 ⊕ xi·8+7 = κ0 ⊕ κ1 ⊕ κ2 ,i=0ki·8+4 ⊕ki·8+7 , κ1 =i=03Xk1,i·8+5 ⊕k1,i·8+6 и κ2 =i=03Xk2,i·8+4 ⊕k2,i·8+7 .i=0Вероятность полученного приближения равна7pL = 1/2 + 2 ·µ416¶4 µ ¶481·= 1/2 + ,1632а отклонение равно ε = +1/32.Следует заметить, что мы получили линейное приближение с одинаковыми суммой входа Xm = [09 09 09 09] и суммой выхода Ym = [09 09 09 09].В результате, если исключить сумму бит ключа с правой стороны приближения, то полученное выражение3Xi=0yi·8+4 ⊕ yi·8+7 +3Xxi·8+4 ⊕ xi·8+7 = 0i=0должно выполняться с вероятностью pL = 1/2 + 1/32, если сумма κ0 ⊕ κ1 ⊕κ2 = 0, или с вероятностью pL = 1/2 − 1/32, если сумма κ0 ⊕ κ1 ⊕ κ2 = 1.Но в любом случае эффективность приближения будет равна |ε| = 1/32.3.2.4 Извлечение бит подключа последнего раунда.Если обнаружено линейное приближение R-1 раундов с достаточно большойвероятностью для шифра с числом раундов R, то можно напасть на шифр,извлекая биты подключа последнего раунда.

В нашем случае, возможно извлечь биты из подключа K3 последнего раунда. Этот процесс основываетсяна частичном расшифровании последнего раунда шифртекста. Те позицииподключа K3 , которые были бы вовлечены в приближение на последнем раунде, называются целевым частичным подключем.21В нашем случае, в целевой частичный подключ входят биты с 4 по 7, с 12по 15, с 20 по 23 и с 28 по 31. Соответственно, нам нужно перебрать все 216возможных значения подключаK3′ = [K3,4 .

. . K3,8 , K3,12 . . . K3,15 , K3,20 . . . K3,23 , K3,28 . . . K3,31 ].Для каждого значения подключа мы выберем 213 случайных открытых текстов X. Далее для каждого такого текста получим шифртекст на неизвестномключе K (предполагаем, что нам заранее были известен набор пар открытого текста и шифртекста), и произведем его частичное расшифрование натекущем ключе-кандидате. Подставим значения бит в наше линейное приближение и проверим выполняется ли оно.

Если результат верный (то естьприближение выполняется), то увеличиваем счет ключа-кандидата. В концеподсчитываем вероятность p выполнения приближения и эффективность |ε|для каждого значения подключа.Ниже приведена часть результата нашей атаки.FFFFFFFFFFFFFFFFFFFFFK3′A 1A 1A 1A 1A 1A 1A 1A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2|ε|0.012090.006590.008540.009400.001460.009640.000240.006100.010250.004520.030400.003540.007450.004880.012820.020750.008420.015990.004760.015750.004039ABCDEF0123456789ABCDКак видно из результатов, полученная эффективность очень близка кожидаемой (1/32 = 0.03125).