263
Пусть F будет блочным шифром с n-битной длиной блока и ключа, и задает
(a) Предположим, что с данной парой (m1, m2) можно найти, за постоянное
время, все ключи k2 , так что m2 = F −1(m1). Покажите, как восстановить весь
ключ для F r (с высокой вероятностью) приблизительно за время 2n, используя
три известных пары вход/выход.
(b) В общем, будет невозможно найти k2 , как указано выше, в течение посто-
янного времени. Тем не менее, покажите, что при использовании этапа предва-
рительной обработки, требующей времени 2n , можно, задав m2, найти (в прин-
ципе) в течение постоянного времени все ключи k2 так, чтобы m2 = F −1(0n).
(c) Предположим, что k1
известно, и что указанный выше этап предвари-
тельной обработки уже запущен. Покажите, как использовать значение y = F
r(x) для единственного выбранного открытого текста x, чтобы определить k2 в
течение постоянного времени.
(d) Поместите указанные выше компоненты вместе, чтобы разработать атаку,
которая восстанавливает весь ключ F r при выполнении,
приблизительно в тече-
ние времени 2n и запрашивании шифрования примерно 2n выбранных входов.
Допустим, что список ключей DES модифицируется следующим образом:
левая половина мастер-ключа используется, чтобы получить все вспомогатель-
ные ключи в раундах 1-8, тогда как правая половина мастер-ключа использу-
ется, чтобы получить все вспомогательные ключи в раундах 9–16. Покажите
атаку на эту модифицированную схему, которая
восстанавливает весь ключ
приблизительно за время 228.
6.15 Пусть f:{0, 1}m×{0, 1}A→{0, 1}A и g:{0,1}n×{0,1}A→{0,1}A
будут безопасными блочными шифрами с m > n, и определим Fk1 ,k2 (x) = fk1
(gk2 (x)). Покажите атаку с регенерацией ключа F с использованием времени
O(2m) и пространства O(A • 2n).
Определите DESYk,kt (x) = DESk (x ⊕ kr). Длина ключа DESY равна 120 би-
там. Покажите атаку на DESY с регенерацией ключа, требующую времени и
пространства ≈ 264.
Выберите случайные S-блоки и смешивающие перестановки для сетей SPN
разных размеров и разработайте дифференциальные атаки на них. Мы реко-
мендуем попробовать пятираундовые SPN с блоками длиной 16 и 24 бита, ис-
пользуя S-блоки с 4-битным входом/выходом. Запишите код, чтобы вычислить
таблицы дифференциалов и провести атаку.
Обеспечьте компромисс по времени/пространству для 40-битного DES (т.е.
зафиксируйте первые 16 битов ключа DES на нуле). Рассчитайте необходимые
264
время и память, и эмпирически оцените вероятность успеха. Эксперименталь-
но проверьте увеличение вероятности успеха,
поскольку количество таблиц
увеличивается. (Предупреждение: это большой проект).
Для каждой из следующих конструкций функции сжатия h из блочного шиф-
ра F, либо покажите атаку, либо докажите устойчивость к коллизиям в модели
идеального шифра:
(a) h(k, x) = Fk (x).
(b) h(k, x) = Fk (x) ⊕ k ⊕ x.
(c) h(k, x) = Fk (x) ⊕ k.
Рассмотрите использование DES, чтобы сконструировать функцию сжатия
следующим образом: Определите h :{0,1}112→{0, 1}64 как h(x,x ) DES
(DES (064)) где |x1| = |x2| = 56.
(a) Запишите явную коллизию в h.
Достарыңызбен бөлісу: