К наивным способам повышения надежности алгоритма относится шифрование блока дважды с двумя различными ключами. Сначала блок зашифровывается первым ключом, а получившийся шифртекст - вторым ключом. Расшифрование выполняется в обратном порядке.
С = ЕК1(Ek2(Р))
P = DK1(DK1(C))
Если блочный алгоритм образует группу, всегда существует такой К3, для которого:
С = ЕК2(ЕК1(Р)) = ЕК3(Р)
Если алгоритм не образует группу, взломать итоговый дважды зашифрованный блок шифртекста с помощью полного перебора намного сложнее. Вместо 2n (где п – длина ключа в битах), потребуется 22n попыток. Если алгоритм использует 64-битовый ключ, для обнаружения ключей, которыми дважды зашифрован шифртекст, понадобится 2128 попыток.
Однако при атаке с известным открытым текстом это не так. Меркл и Хеллман предложили способ согласования памяти и времени, который позволяет вскрыть такую схему двойного шифрования за 2n+1 шифрований, а не за 22n. (Они использовали эту схему против DES, но результаты можно обобщить на все блочные алгоритмы). Такая атака называется «встреча посередине»: с одной стороны выполняется зашифрование, а с другой - расшифрование, а полученные посередине результаты сравниваются.
В этой атаке криптоаналитику известны значения P1, С1, Р2 и С2, такие что:
C1=EK2(EK1(Pt))
С2=ЕК2(ЕК1(Р2))
Для каждого возможного К криптоаналитик рассчитывает ЕК(Р1) и сохраняет результат в памяти. Собрав все результаты, он для каждого К вычисляет DK(C1) и ищет в памяти такой же результат. Если такой результат обнаружен, то, возможно, что текущий ключ – К2, а ключ для результата в памяти – К1. Затем криптоаналитик зашифровывает Р2 ключами К1 и К2. Если он получает С2, он может почти быть убежденным (с вероятностью 1 к 22m-2n, где т - размер блока), что он восстановил и К1 и К2. В противном случае он продолжает поиск. Максимальное количество попыток шифрования, которое ему придется предпринять, составляет 2*2n, т.е. 2n+1. Если вероятность ошибки слишком велика, криптоаналитик может использовать третий блок шифртекста, обеспечивая вероятность успеха 1 к 23m-2n. Существуют и другие способы оптимизации.
Для такого вскрытия нужен большой объем памяти: 2n блоков. Для 56-битового ключа нужно хранить 256 64-битовых блоков, или 1017 байт. Такой объем памяти пока еще трудно себе представить, но этого хватает, чтобы убедить самых осторожных криптографов в ненадежности двойного шифрования.
При 128-битовом ключе для хранения промежуточных результатов потребуется огромная память в 1039 байт. Если предположить, что каждый бит информации хранится на единственном атоме алюминия, запоминающее устройство, нужное для такого вскрытия, будет представлять собой алюминиевый куб с ребром 1 км. Кроме того, понадобится куда-то его поставить. Так что атака «встреча посередине» при ключах такого размера представляется невозможной.
Другой способ двойного шифрования, который иногда называют методом Дэвиса-Прайса (Davies-Price), представляет собой вариант режима шифрования СВС.
Сi =Ek1(PiÅ Ek2(Ci-1))
Pi=Dk1(Ci)Å Ek2(Ci-1)
Утверждается, что «у этого режима нет никаких особых достоинств», к тому же он, по-видимому, столь же уязвим к атаке «встреча посередине», как и другие режимы двойного шифрования.
Метки:
Двойное шифрование,
Двойное шифрование
