Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стимулом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии создания нового алгоритма. DES является безопасным алгоритмом, он подвергался криптоанализу добрых 20 лет и, тем не менее, наилучшим способом вскрытия остается грубая сила. Однако ключ слишком короток. Разве не плохо было бы использовать DES в качестве компонента другого алгоритма с более длинным ключом ? Это позволило бы получить преимущества длинного ключа с гарантией двух десятилетий криптоанализа .

Одним из способов объединения является многократное шифрование - для шифрования одного и того же блока открытого текста алгоритм шифрования используется несколько раз с несколькими ключами . Шифрование каскадом похоже на многократное шифрование, но использует различные алгоритмы . Существуют и другие методы.

Повторное шифрование блока открытого текста одним и тем же ключом с помощью того же или другого а л-горитма неразумно. Повторное использование того же алгоритма не увеличивает сложность вскрытия грубой силой. (Не забывайте, мы предполагаем, что алгоритм, включая количество шифрований, известен криптоан а-литику.) При различных алгоритмах сложность вскрытия грубой силой может возрастать, а может и остаться неизменной. Если вы собираетесь использовать методы, описанные в этой главе, убедитесь, что ключи для п о-следовательных шифрований различны и независимы.

15.1 Двойное шифрование

Наивным способом повысить безопасность алгоритма является шифрование блока дважды с двумя разли ч-ными ключами. Сначала блок шифруется первым ключом, а затем получившийся шифротекст шифруется вт о-рым ключом. Дешифрирование является обратным процессом.

C = Ek2( P))

Если блочный алгоритм образует группу (см. раздел 11.3), то всегда существует K3, для которого C = Ek2( Eki( P)) = Екз( P)

Если алгоритм не образует группу, то при помощи исчерпывающего поиска взломать получающийся дважды зашифрованный блок шифротекста намного сложнее. Вместо 2" (где n - длина ключа в битах), потребуется 22" попыток. Если алгоритм использует 64-битовый ключ, для обнаружения ключей, которыми дважды зашифр о-ван шифротекст, потребуется 2128 попыток.

Но при вскрытии с известным открытым текстом это не так. Меркл и Хеллман [1075] придумали способ обменять память на время, который позволяет вскрыть такую схему двойного шифрования за 2"+ шифрований, а не за 22n. (Они использовали эту схему против DES, но результаты можно обобщить на все блочные алгоритмы.) Это вскрытие называется " встреча посередине", с одной стороны выполняется шифрование а с другой - дешифрирование, получившиеся посередине результаты сравниваются .

В этом вскрытии криптоаналитику известны P1, C1, P2 и C2, такие что

C1 = Ek2( Ek1( P1)) C2 = Ek2( Ek1( P2))

Для каждого возможного К (или К1, или К2), криптоаналитик рассчитывает EK(P1) и сохраняет результат в памяти. Собрав все результаты, он для каждого К вычисляет DK(C1) и ищет в памяти такой же результат. Если такой результат обнаружен, то возможно, что текущий ключ - К2, а ключ для результата в памяти - К1. Затем криптоаналитик шифрует P1 с помощью К1 и К2. Если он получает C2, то он может гарантировать (с вероятностью успеха 1 к 22n"2m, где m - размер блока), что он узнал и К1, и К2. Если это не так, он продолжает поиск. Максимальное количество попыток шифрования, которое ему, возможно, придется предпринять, равно 2*2", или 2"+. Если вероятность ошибки слишком велика, он может использовать третий блок шифротекста, обесп е-чивая вероятность успеха 1 к 22n"3m. Существуют и другие способы оптимизации [912].

Для такого вскрытия нужен большой объем памяти: 2n блоков. Для 56-битового ключа нужно хранить 256 64-битовых блоков, или 1017 байтов. Такой объем памяти пока еще трудно себе представить, но этого хватает, чт о-бы убедить самых параноидальных криптографов в том, что двойным шифрованием пользоваться не стоит .

При 128-битовом ключе для хранения промежуточных результатов потребуется 10 39 байтов. Если предположить, что есть способ хранить бит информации, используя единственный атом алюминия , устройство памяти, нужное для выполнения такого вскрытия, будет представлять собой алюминиевый куб с ребром, длиной 1 км . Кроме того, вам понадобится куда-то его поставить ! Вскрытие "встреча посередине" кажется невозможным для ключей такого размера.

Другим способом двойного шифрования, который иногда называют Davies-Price, является вариантом CBC [435].

p = c ) е Ek2(c,-i))

Утверждается, что "у этого режима нет никаких особых достоинств", к тому же он, по видимому, так же чувствителен ко вскрытию "встреча посередине" как и другие режимы двойного шифрования .

15.2

Тройное шифрование с двумя ключами

В более интересном методе, предложенном Тачменом в [1551], блок обрабатывается три раза с помощью двух ключей: первым ключом, вторым ключом и снова первым ключом . Он предлагает, чтобы отправитель сначала шифровал первым ключом, затем дешифрировал вторым, и окончательно шифровал первым ключом . Получатель расшифровывает первым ключом, затем шифрует вторым и, наконец, дешифрирует первым .

C = Dk2( P)))

P = Ek2( Dk1(C)))

Иногда такой режим называют шифрование-дешифрирование-шифрование (encrypt-decrypt-encrypt, EDE) [55]. Если блочный алгоритм использует и-битовый ключ, то длина ключа описанной схемы составляет 2n бит. Любопытный вариант схемы шифрование-дешифрирование-шифрование был разработан в IBM для совместимости с существующими реализациями алгоритма: задание двух одинаковых ключей эквивалентно одинарному шифрованию. этим ключом. Схема шифрование-дешифрирование-шифрование сама по себе не обладает ник а-кой безопасностью, но этот режим был использован для улучшения алгоритма DES в стандартах X9.17 и ISO 8732 [55, 761].

K1 и K2 чередуются для предотвращения описанного выше вскрытия "встреча посередине" . Если C = EK1 (EK1 (EK1 (P))), то криптоаналитик для любого возможного K1 может заранее вычислить EK1 (EK1 (P))

и затем выполнить вскрытие. Для этого потребуется только 2n+2 шифрований.

Тройное шифрование с двумя ключами устойчиво к такому вскрытию . Но Меркл и Хеллман разработали другой способ размена памяти на время, который позволяет взломать этот метод шифрования за 2n-1 действий, используя 2n блоков памяти [1075].

Для каждого возможного K2 расшифруйте 0 и сохраните результат. Затем расшифруйте 0 для каждого возможного K1, чтобы получить P. Выполните тройное шифрование P, чтобы получить C, и затем расшифруйте C ключом K1. Если полученное значение совпадает с значением (хранящемся в памяти), полученным при деши ф-рировании 0 ключом K2, то пара K1 K2 является возможным результатом поиска. Проверьте, так ли это. Если нет, продолжайте поиск.

Выполнение этого вскрытия с выбранным открытым текстом требует огромного объема памяти . Понадобится 2n времени и памяти, а также 2m выбранных открытых текстов. Вскрытие не очень практично, но все же чувствительность к нему является слабостью алгоритма.

Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener) преобразовали это вскрытие ко вскрытию с известным открытым текстом, для которого нужно p известных открытых текстов. В примере предполагается, что используется режим EDE.

(1) Предположить первое промежуточное значения a.

(2) Используя известный открытый текст, свести в таблицу для каждого возможного K1 второе промежуточное значение b, при первом промежуточном значении, равном a:

b = Dk1(C)

где C - это шифротекст, полученный по известному открытому тексту.

(3) Для каждого возможного K2 найти в таблице элементы с совпадающим вторым промежуточным значение

b = Ек2(а)

(4) Вероятность успеха равно pim, где p - число известных открытых текстов, а m - размер блока. Если совпадения не обнаружены, выберите другое а и начните сначала.

Вскрытие требует 2n+m 7 времени и p - памяти. Для DES это равно 2120 7 [1558]. Для p, больших 256, это вскрытие быстрее, чем исчерпывающий поиск.

Тройное шифрование с тремя ключами

Если вы собираетесь использовать тройное шифрование, я рекомендую три различных ключа. Общая длина ключа больше, но хранение ключа обычно не является проблемой . Биты дешевы.

C = Екз( Dk2( Ek1( P)))

P = Dk1( Ek2( Окз(С)))

Для наилучшего вскрытия с разменом памяти на время, которым является "встреча посередине", потребуется 22n действий и 2n блоков памяти [1075]. Тройное шифрование с тремя независимыми ключами безопасно н а-столько, насколько на первый взгляд кажется безопасным двойное шифрование .

Тройное шифрование с минимальным ключом (TEMK)

Существует безопасный способ использовать тройное шифрование с двумя ключами, противостоящий описанному вскрытию и называемый Тройным шифрованием с минимальным ключом (Triple Encryption with Minimum Key, TEMK) [858]. Фокус в тои, чтобы получить три ключа из: X1 и X2.

К1 = Dx2( Ex1(71)))

К2 = Dx2( Ex1(72)))

K3 = Ex 1( Dx2( Ex1(73)))

71, 72 и 73 представляют собой константы, которые необязательно хранить в секрете. Эта схема гарантирует, что для любой конкретной пары ключей наилучшим будет вскрытие с известным открытым текстом .

Режимы тройного шифрования

Недостаточно просто определить тройное шифрование, нужно выбрать один из способов его использования . Решение зависит от требуемых безопасности и эффективности . Вот два возможных режима тройного шифров а-ния:

Внутренний CBC: Файл три раза шифруется в режиме CBC (см. 14tha). Для этого нужно три различных IV.

C, = (S, е C,-1); S, = Dk2( 7; е s,-1); 7; = ( е 7; 1) P = е (7;); 7; = S,-1 е Ек2 (S,); S, = C,-1 е (C, )

C0, S0 и Г0 являются IV.

Внешний CBC: Файл троекратно шифруется в режиме CBC (см. 14thb). Для этого нужен один IV.

С, = Екз( Dk2( Ек1( P е с-1))) P = с-1 е Dk1( Ек2( Dкз(с,)))