Повторное шифрование блока открытого текста одним и тем же ключом с помощью того же или другого алгоритма неэффективно. Повторное использование того же алгоритма не повышает сложность лобового вскрытия. (Мы предполагаем, что криптоаналитику известны алгоритм и число операций шифрования). При использовании различных алгоритмов сложность лобового вскрытия может, как возрастать, так и оставаться неизменной. При этом нужно убедиться в том, что ключи для последовательных шифрований различны и независимы.
4.1. Двойное шифрование
К наивным способам повышения надежности алгоритма относится шифрование блока дважды с двумя различными ключами. Сначала блок зашифровывается первым ключом, а получившийся шифртекст - вторым ключом. Расшифрование выполняется в обратном порядке.
С = ЕК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)
Утверждается, что «у этого режима нет никаких особых достоинств», к тому же он, по-видимому, столь же уязвим к атаке «встреча посередине», как и другие режимы двойного шифрования.
4.2. Тройное шифрование
4.2.1. Тройное шифрование с двумя ключами
В более удачном методе, предложенном Тачменом, блок обрабатывается три раза с использованием двух ключей: первым ключом, вторым ключом и снова первым ключом. Тачмен предлагает, чтобы отправитель сначала зашифровал сообщение первым ключом, затем расшифровал вторым, и окончательно зашифровал первым ключом. Получатель расшифровывает сообщение первым ключом, затем зашифровывает вторым и, наконец, расшифровывает первым.
С = EK1(DK2(EK1(P)))
P = DK1(EK1(DK1(С)))
Иногда такой режим называют режимом зашифрование-расшифрование-зашифрование (Encrypt-Decrypt-Encrypt - EDE). Если блочный алгоритм использует n-битовый ключ, длина ключа описанной схемы составляет 2п бит. Эта остроумная связка ключей (зашифрования-расшифрования-зашифрования) разработана в корпорации IBM для совместимости с существующими реализациями алгоритма: задание двух одинаковых ключей эквивалентно одинарному шифрованию. Такая схема EDE сама по себе не обеспечивает заведомую безопасность, однако этот режим использовался для улучшения алгоритма DES в стандартах Х9.17 и ISO 8732.
Для предотвращения описанной выше атаки «встреча посередине», использование ключей ki и K2 чередуется. Если С=ЕK2(ЕК1(ЕК1(Р))), то криптоаналитик может заранее вычислить ЕК1(ЕК1(Р))) для любого возможного K1, а затем выполнить вскрытие. Для этого потребуется только 2n+2 шифрований.
Тройное шифрование с двумя ключами устойчиво к такой атаке. Но Меркл и Хеллман разработали другой способ согласования памяти и времени, который позволяет взломать и этот алгоритм шифрования за 2n-1 действий, используя 2n блоков памяти.
Для каждого возможного К2 расшифровывают 0 и сохраняют результат в памяти. Затем расшифровывают 0 для каждого возможного К1, чтобы получить Р. Выполняют тройное зашифрование Р, чтобы получить С, и затем расшифровывают С ключом К1. Если полученное значение совпадает со значением (хранящимся в памяти), полученным при расшифровании 0 ключом К2, то, возможно, пара K1K2 и будет искомым результатом. Проверяют, так ли это. Если нет, продолжают поиск.
Для выполнения этого вскрытия с подобранным открытым текстом нужна память огромного объема. Понадобится 2n времени и памяти, а также 2m подобранных открытых текстов. Атака не слишком практична, но все же указывает на некоторую слабость этого метода.
Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener) преобразовали эту атаку к атаке на основе открытых текстов, для которой их нужно р штук. В примере предполагается использование режима EDE.
1) Предположить первое промежуточное значение а.
2) Используя известный открытый текст, свести в таблицу для каждого возможного К1 второе промежуточное значение b при первом промежуточном значении, равном а:
b=DK1(С)
где С - шифртекст, полученный по известному открытому тексту.
3) Для каждого возможного K2 найти в таблице элементы с совпадающим вторым промежуточным значением b:
b = EK2(a)
4) Вероятность успеха равна р/т, где р - число известных открытых текстов, а т -размер блока. Если совпадения не обнаружены, нужно выбрать другое значение а и начать сначала.
Атака требует 2n+m/р времени и р - памяти. Для алгоритма DES это составляет 2120/р. При р, больших 256, эта атака выполняется быстрее, чем полный перебор.
4.2.2. Тройное шифрование с тремя ключами
Если используют тройное шифрование, рекомендуется использовать три разных ключа. Общая длина ключа станет больше, но хранение ключа обычно не вызывает затруднений. Биты дешевы.
С = EK3(DK2(EK1(P)))
P = DK1(EK2(DK3(С)))
Для наилучшего вскрытия с согласованием памяти и времени, примером которого служит «встреча посередине», понадобятся 22n операций и 2n блоков памяти. Тройное шифрование с тремя независимыми ключами настолько надежно, насколько на первый взгляд кажется надежным двойное шифрование.
4.2.3. Тройное шифрование с минимальным ключом
Известен более надежный метод использования тройного шифрования с двумя ключами, препятствующий описанной атаке и называемый тройным шифрованием с минимальным ключом (Triple Encryption with Minimum Key - TEMK). Фокус в том, чтобы получить три ключа из двух: Х1 и Х2.
K1=EX1(DX2(EX1(T1)))
K2 = EX1(DX2(EX1(T2)))
K3=EX1(DX1(EX1(T3)))