Глава 15

Объединение блочных шифров

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

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

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

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

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

C = Ek2( EKi{ P)) P = DKi{ Dk2(C))

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

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

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

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

C2 = Ек2( ЕкД P2))

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

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

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

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

q = Pi ф EK2(q p = dki( q) ф ek2(q

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

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

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

с = eki( dki( EKi( P))) p = Dk1( Ek2( DKi(C)))

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

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

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

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

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

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

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

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

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

b = DKi(C)

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

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