238
Трехраундовый DES. Согласно Рисуноку 6.5, выходное значение y теперь
равняется (L3, R3). Поскольку L1 = R0 и R2 = L3, есдинственными неизвестны-
ми значениями на рисунке остаются R1 и L2 (которые равны).
Теперь у нас уже больше нет входной/выходной пары для любой раундовой
функции fi. Например, выходное значение f2 равняется L1 ⊕ R2, где оба этих
значения равны. Однако, мы не знаем значения R1, которое является входным
элементом f2. Аналогично, мы можем определить входные элементы f1 и f3 ,
но не выходные элементы этих функций. Таким образом, атака, которую мы ис-
пользовали, чтобы
взломать однораундовый DES, здесь не сработает.
Вместо того, чтобы надеяться на знания о входных и выходных элементах одной из
раундовых функций, мы используем знания об определенном отношении между вход-
ными и выходными данными f1 и f3.
Обратите внимание, что выходной элемент f1
равен L0 ⊕R1 = L0 ⊕ L2, а выходной элемент f3 равен L2 ⊕ R3.
Следовательно, f1(R0)
⊕
f3(R2) = (L0 ⊕L2) ⊕ (L2 ⊕ R3) = L0 ⊕ R3, где известны и L0, и R3. То есть XOR вы-
ходных данных f1 и f3 известен. Более того, входной элемент в f1 - это R0 , а входной
элемент в f3 - это L3, оба они известны. Подытоживая, можно сказать, что мы можем
определить входные данные в f1 и f3, а также XOR их выходных данных. Сейчас мы
опишем атаку, которая находит секретный ключ на основе данной информации.
Вспомним, что расписание смены ключей
DES имеет такое свойство, что
мастер-ключ делится на «левую половину», которую мы обозначили как kL,
и «правую половину» kR, каждая из которых содержит 28 бит. Более того, 24
самых левых бита подключа, используемых в каждом раунде берутся только
из kL, а 24 самых правых бита каждого подключа берутся из kR. Это означает,
что kL влияет толко на входные данные в первые четыре S-блока в раунде, в то
время как kR влияет только на входные данные в последние четыре S-блока.
Поскольку смешивающая перестановка известна, мы также знаем, какие биты
выходного элемента каждой раундовой функции выходят из каждого S-блока.
Идея, что кроется в атаке, - это по-отдельности пересечь пространство ключей
за каждой половиной мастер-ключа, осуществляя атаку со сложностью прибли-
зительно 2 • 228 , а не 256. Такая атака будет возможна, если мы сможем про-
верить догадку о половине мастер-ключа, и мы сейчас покажем, как это можно
сделать. Скажем, мы угадали какое-то значение для kL, левую половину мастер-
ключа. Мы знаем входной элемент R0 функции f1, и поэтому используя угады-
вание kL , мы можем вычислить входной элемент в первые четыре S-блока. Это
означает, что мы можем вычислить половину выходных битов f1 (смешивающая
перестановка распространяет биты, которые мы знаем, но поскольку смешиваю-
щая перестановка известна, мы знаем точно, какие это биты). Аналогичным об-
разом мы можем вычислить одинаковые расположения в выходном элементу f3
, используя известный входной элемент L3 в f3 , а также ту же догадку для kL.
239
Наконец, мы можем вычислить XOR этих выходных значений и проверить, со-
впадают ли соответствующие биты, в известном значении XOR выходных дан-
ных f1 и f3. Если они не равны, тогда наша догадка для kL является некорректной
. Корректная догадка для kL будет всегда проходит этот тест, и поэтому не будет
исключена, но некорректная догадка ожидаемо пройдет этот тест только с вероят-
ностью приблизительно 2−16 (поскольку мы проверяем равенство 16 бит в двух
вычисленных значениях). Существует 228
возможных значений для kL, поэтому
если каждое некорректное значение остается жизнеспособным возможным зна-
чением с вероятностью2−16 , тогда мы ожидаемо отанемся с только лишь 228 •
2−16 = 212 вариантов для kL после вышеописанного.
Выполняя вышеописанное для каждой половины мастер-ключа, мы получим за
время 2 • 228 приблизительно 212 возможных значений для левой половины и 212
возможных значений для правой половины. Поскольку каждая комбинация левой и
правой половин возможна, у нас есть 224 возможных ключей, и мы можем запустить
перебор с использованием «грубой силы» по этому множеству, используя дополни-
тельную входную/выходную пару (xr , yr). (Альтернативный подход, который более
эффективный, - это просто повторить предыдущую атаку, используя 212 оставшихся
возможных значений для каждой половины ключа.) Временная сложность атаки со-
ставляет приблизительно 2 • 228 + 224 < 230, что намного меньше, чем 256.
Достарыңызбен бөлісу: