Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Трехраундовый DES.
| Двухраундовый DES. В двухраундовом DES, выходной элемент y равен (L2,
R2), где L1 = R0 R1 = L0 ⊕ f1(R0) L2 = R1 = L0 ⊕ f1(R0) R2 = L1 ⊕ f2(R1). L0, R0, L2 и R2 известны из полученной входной/выходной пары (x, y), и, таким образом, мы также знаем L1 = R0 и R1 = L2. Это означает, что мы знаем вхоной/ выходной элементы и f1, и f2, и поэтому тот же самый метод , который был ис- пользован для атаки на однораундовый DES, может быть использован здесь для определения как k1, так и k2 за время приблизительно 2 • 216. Данная атака рабо- тает, даже если k1 и k2 являются полностью независимыми ключами, хотя, фак- тически, расписание смены ключей DES подтверждает, что многие из битов k1 и k2 равны (что можно использовать для ускорения атаки в дальнейшем). 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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|