Рассмотрим вариант алгоритма DES, называемый DES-WEAK. В DES-WEAK,
в раунде нет перестановки P и все S-блоки заменены. Все новые S-блоки
идентичны и определяются следующим образом. Пусть b0, . . ., b5 представляют шесть входных битов S-блока и a0,
a1, a2 и a3 четыре выходных бита. Тогда a0 = b3 ... b0b1b5, a1 = b0 ... b1b3b5, a2 = b1 ... b2b3b5,
и a3 = b2 ≪ b4 ≥ b1b3b5.
• Разработайте алгоритм для максимально эффективного взлома 16-раундового DES-WEAK.
Мы подошли к этому дизайну так, как я упомянул ниже.
Мы используем дифференциальный криптоанализ для восстановления ключа. Рассмотрим
дифференциал 000100 поступает в S-блок S2. Пусть один из двух
входы с заданным дифференциалом
быть b0b1b2b3b4b5, а соответствующий вывод — a0a1a2a3. Пусть
выход для второго входа (= b0b1b2b2(b3 ≥ 1)b4b5) будет a 0 0 a 0 1 a 0 2
а 0 3 . Тогда a0 ≪ a 0 0 = 1, a1 ≥ a 0 1 = b1b5, a2 ≥ a 0 2 = b2b5
и a3 ≥ a 0 3 = b1b5. Следовательно, выходной дифференциал равен 1000 на
заданный входной дифференциал с
вероятность 1 2 + 1 2 · 1 4 = 5 8 (либо b5 равно нулю, либо b5 равно единице и
оба b1, b2 равны нулю).
Проблема с этим дифференциальным выходом заключается в том, что в следующем раунде
после расширения два S-блока получат ненулевой дифференциал. Предполагать
что в первом раунде дифференциал в S1 равен 000000, а
левый полудифференциал тоже все нули. Затем, в следующем раунде,
дифференциал в S1 будет 000001, а в S2 будет 010000. Пусть
проанализируем оба. Сначала рассмотрим S1. С теми же обозначениями для первого
вход и два выхода (теперь второй вход — это b0b1b2b3b4(b5 ≪
1)), получаем a0 ≪ a 0 0 = b0b1, a1 ≥ a 0 1 = b1b3, a2 ≥ a 0 2 = b2b3
и a3 ≥ a 0 3 = b1b3. Следовательно, вывод
дифференциал равен 0000 с вероятностью 1 2 х 3 4 + 1 2 х 1 4 = 1 2
(либо b3 равно нулю, либо одно из значений b0, b1 равно нулю или
b3 равно единице, а оба b1, b2 равны нулю). Рассмотрим S2. Теперь второй вход
равно b0(b1 ≪ 1)b2b3b4b5, поэтому мы получаем a0 ≥ a 0 0 = b0b5,
a1 → a 0 1 = b3b5, a2 → a 0 2 = 1 и a3 → a 0 3 = b3b5. Следовательно
выходной дифференциал 0010 с
вероятность 1 2 + 1 2 · 1 4 = 5 8 (либо b5 равно нулю, либо b5 равно единице и
оба b0, b3 равны нулю). В следующем раунде, после применения расширения,
разница в этих двух S-блоках становится 000000 000100, что равно
точно такой же дифференциал, который вошел в первый раунд в
эти двое! Теперь, используя этот анализ, мы можем получить характеристику
с большой вероятностью следующим образом. Пусть Z обозначает нулевой дифференциал на
32 бита, P означает дифференциал 0000 0010 0000 0000 0000 0000 0000
0000
, и PË обозначают дифференциал
0000 1000 0000 0000 0000 0000 0000 0000
. Приведенный выше анализ показывает следующую последовательность преобразования
дифференциалы: [P, Z] p=1 âââ [Z, P] p= 5 8 ââââ [P, PË] p= 5 16 ââââ
[P , Z Ë ] p=1 âââ [Z, PË] p= 5 16 ââââ [P , P Ë ] p= 5 8 ââââ [P, Z].
Общая вероятность вышеуказанной характеристики равна 5 4 2 14 .
Повторяем это еще раз, а затем берем только первые два раунда
из этого мы получаем четырнадцатираундовую характеристику с вероятностью 5 9 2
31 — 9 — 10 — 4
. Следовательно, используя несколько тысяч пар открытого текста, DES-WEAK можно взломать.
Теперь перед нами стоит новая задача, и мы застряли в ней. Упомянутый ниже дизайн представляет собой небольшую модификацию вышеупомянутого вопроса, над которым мы работали. Схема выглядит следующим образом..
Рассмотрим вариант алгоритма DES, в котором все S-блоки
заменены. Все новые S-блоки идентичны и определяются следующим образом.
Пусть b1, b2, · · · , b6 представляют шесть входных битов S-блока. Его
выход: b1 · (b2 · b3 · b4), (b3 · b4 · b5) · b6, b1 · (b4 · b5 ·
b2), (b5 · b2 · b3)  b6. Здесь âââ побитовая операция XOR, и â·â
это побитовое умножение. Разработайте алгоритм для взлома 16-раундового DES
с новыми S-блоками максимально эффективно.
В этом проекте операция перестановки все еще присутствует, а вывод S-блока отличается. Итак, как мы можем подойти к этому, как мы сделали выше, учитывая, что поле перестановок все еще существует.
