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

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

[image]

[image]

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

[image]

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

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

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

[image]

[image]

Для каждого возможного K (или K1, или K2), криптоаналитик рассчитывает EK(P1) и сохраняет результат в памяти. Собрав все результаты, он для каждого 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-битовом ключе для хранения промежуточных результатов потребуется 1039 байтов. Если предположить, что есть способ хранить бит информации, используя единственный атом алюминия, устройство памяти, нужное для выполнения такого вскрытия, будет представлять собой алюминиевый куб с ребром, длиной 1 км. Кроме того, вам понадобится куда-то его поставить! Вскрытие "встреча посередине" кажется невозможным для ключей такого размера.

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

[image]

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