Комбинированные методы шифрования

Комбинированные методы шифрования, композиция шифров

Комбинированные методы шифрования

Важнейшим требованием к системе шифрования является ее стойкость. К сожалению, повышение стойкости при помощи любого метода приводит, как правило, к трудностям и при шифровании открытого текста и при его расшифровке. Одним из наиболее эффективных методов повышения стойкости шифртекста является метод комбинированного шифрования. Этот метод заключается в использовании и комбинировании нескольких простых способов шифрования. Шифрование комбинированными методами основывается на результатах, полученных К.Шенноном. Наиболее часто применяются такие комбинации, как подстановка и гамма, перестановка и гамма, подстановка и перестановка, гамма и гамма. Так, например, можно использовать метод шифрования простой перестановкой в сочетании с методом аналитических преобразований или текст, зашифрованный методом гаммирования, дополнительно защитить при помощи подстановки.

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

Один из методов объединения – многократное шифрование. В этом случае для шифрования одного и того же блока открытого текста алгоритм шифрования используется несколько раз с несколькими ключами. Каскадное шифрование подобно многократному шифрованию, но использует различные алгоритмы. Известны и другие методы.

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

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

С = Е_К2 (Е_{К 1}{Р));

P = D_Kl (D _К2 (C)).

Однако, если блочный алгоритм образует группу, всегда существует такой К₃, для которого:

С = Е _К2 (Е _{К 1} (Р)) = Е_К3 (Р).

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

Однако при атаке с известным открытым текстом это не так. Меркл и Хеллман предложили способ согласования памяти и времени, который позволяет вскрыть такую схему двойного шифрования за 2ⁿ⁺¹ шифрований, а не за 2²ⁿ. Такая атака называется « встреча посередине »: с одной стороны выполняется зашифрование, а с другой – расшифрование, а полученные посередине результаты сравниваются.

В этой атаке криптоаналитику известны значения Р₁ С₁ Р₂ и С₂, такие что:

С₁ = Е _К2 (Е _{К 1} (Р₁));

С₂ = Е _К2 (Е _{К 1} (Р₂)).

Для каждого возможного К криптоаналитик рассчитывает Е_К (Р₁)и сохраняет результат в памяти. Собрав все результаты, он для каждого К вычисляет D_K (C₁)и ищет в памяти такой же результат. Если такой результат обнаружен, то, возможно, что текущий ключ – К₂, а ключ для результата в памяти – К₁. Затем криптоаналитик зашифровывает Р₂ ключами К₁ и К₂. Если он получает С₂, он может почти быть убежденным, что он восстановил и К₁ и K₂. В противном случае он продолжает поиск. Максимальное количество попыток шифрования, которое ему придется предпринять, составляет 2*2ⁿ, т.е. 2ⁿ⁺¹. Для такого вскрытия нужен большой объем памяти: 2ⁿ блоков. Для 56-битового ключа нужно хранить 2⁵⁶ 64-битовых блоков, или 10¹⁷ байт. Такой объем памяти пока еще трудно себе представить, но этого хватает, чтобы убедить самых осторожных криптографов в ненадежности двойного шифрования.

При 128-битовом ключе для хранения промежуточных результатов потребуется огромная память в 10³⁹ байт. Так что атака «встреча посередине» при ключе такого размера представляется невозможной.

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

C = E _{К 1}D _К2 (E _{К 1} (P)));

P = D _{К 1} (E _К2 (D _{К 1} (C))).

Иногда такой режим называют режимом зашифрование-расшифрование-зашифрование (Encrypt-Decrypt-Encrypt - EDE). Если блочный алгоритм использует n -битовый ключ, длина ключа описанной схемы составляет 2п бит. Эта остроумная связка ключей EDE разработана в корпорации IBM для совместимости с существующими реализациями алгоритма: задание двух одинаковых ключей эквивалентно одинарному шифрованию. Такая схема EDE сама по себе не обеспечивает заведомую безопасность, однако этот режим использовался для улучшения криптостойкости алгоритма DES.

Для предотвращения описанной выше атаки «встреча посередине», использование ключей K₁ и К₂ чередуется. Тройное шифрование с двумя ключами устойчиво к такой атаке. Но Меркл и Хеллман разработали другой способ согласования памяти и времени, который позволяет взломать и этот алгоритм шифрования за 2^n–1 действий, используя 2ⁿ блоков памяти.

Для выполнения этого вскрытия с подобранным открытым текстом нужна память огромного объема. Атака не слишком практична, но все же указывает на некоторую слабость этого метода.

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

С = E _К3 (D _К2 (E _{К 1} (P)));

P = D _{К 1} (E _К2 (D _К3 (C))).

Для наилучшего вскрытия с согласованием памяти и времени, примером которого служит «встреча посередине», понадобятся 2²ⁿ операций и 2ⁿ блоков памяти.

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

S_i = E _{К 1} (S_i-1 ⊕ I₁); I₁ = I₁ +1;

T_i = E _К2 (T_{i -1} ⊕ I₂); I₂ = I₂ +1;

C_i = P_i ⊕ S_i ⊕ T_i.

где S_i, и T_i – внутренние переменные, а I₁ и I₂ - счетчики. Две копии блочного алгоритма работают в некотором гибридном режиме OFB/счетчика, а открытый текст, S_i и T_i, объединяются операцией XOR. Ключи К₁ и K ₂ независимы.

9.1.4. Схема xDES¹. Используется как компонент ряда блочных алгоритмов с увеличенными размерами ключей и блоков. Эти схемы никак не зависят от DES, и в них может использоваться любой блочный алгоритм.

Первый, xDES¹, представляет собой просто схему с блочным шифром в качестве базовой функции. Размер блока вдвое больше размера блока используемого блочного шифра, а размер ключа втрое больше, чем у используемого блочного шифра. В каждом из трех раундов правая половина шифруется блочным алгоритмом и одним из ключей, затем выполняется операция XOR (исключающее или) результата с левой половиной, и половины переставляются.

Это быстрее обычного тройного шифрования, так как тремя шифрованиями шифруется блок, длина которого вдвое больше длины блока используемого блочного алгоритма. Но при этом возможна простая атака «встреча посередине», которая позволяет найти ключ с помощью таблицы размером 2^k, где к - размер ключа блочного алгоритма. Правая половина блока открытого текста шифруется с помощью всех возможных значений К₁, выполняется операция XOR с левой половиной открытого текста, и полученные значения сохраняются в таблице. Затем правая половина шифртекста шифруется с помощью всех возможных значений К₃, и выполняется поиск совпадений в таблице. При совпадении пара ключей К₁ и К₃ - возможный вариант правого ключа. После нескольких попыток вскрытия останется только один кандидат. Таким образом, xDES нельзя назвать идеальным решением. Более того, известно вскрытие с подобранным открытым текстом, доказывающее, что xDES¹ ненамного прочнее используемого в нем блочного алгоритма.

В xDES² эта идея расширяется до 5-раундового алгоритма, размер блока которого в 4, а размер ключа – в 10 раз превышают размеры блока и ключа используемого блочного шифра. Эта схема также быстрее тройного шифрования: для шифрования блока, который в четыре раза больше блока используемого блочного шифра, нужно 10 шифрований. Однако этот метод уязвим к дифференциальному криптоанализу, и использовать его не стоит. Такая схема остается чувствительной к дифференциальному криптоанализу, даже если используется DES с независимыми ключами раундов.

9.1.5. Пятикратное шифрование. Если тройное шифрование недостаточно надежно – скажем, вы хотите зашифровать ключи тройного шифрования еще более сильным алгоритмом – кратность шифрования можно увеличить. Очень устойчиво к вскрытию «встреча посередине» пятикратное шифрование. (Аргументы, аналогичные рассмотренным для двойного шифрования, показывают, что четырехкратное шифрование по сравнению с тройным лишь незначительно повышает надежность).

С = Е_{К 1} (D_К2 (Е_К3 (D_К2 (Е_{К 1} (Р)))));

Р = D_{К 1} (Е_К2 (D _К3 (Е _К2 (D_{К 1} (С))))).

Эта конструкция обратно совместима с тройным шифрованием, если К₂=К₃, и с однократным шифрованием, если К₁ = К₂ = К₃. Конечно, она будет еще надежней, если использовать пять независимых ключей.

9.1.6. Отбеливание. Отбеливанием(whitening) называют такое преобразование, при котором выполняется операция XOR над входом блочного алгоритма и частью ключа и XOR над выходом блочного алгоритма и другой частью ключа. Смысл этих действий в том, чтобы помешать криптоаналитику восстановить пары – «открытый текст / шифртекст», для исследуемого блочного алгоритма. Метод заставляет криптоаналитика угадывать не только ключ алгоритма, но и одно из значений отбеливания. Так как операция XOR выполняется и до, и после исполнения блочного алгоритма, этот метод считается устойчивым к атаке «встреча посередине».

C = K₃ ⊕ E _К2 (P ⊕ K₁);

P =K₁ ⊕ D _К2 (C ⊕ K₃).

Если К₁ = К₃, то для вскрытия «в лоб» потребуется 2^{n+m / p} операций, где п - размер ключа, т - размер блока, а р –число известных открытых текстов. Если К₁ и К₃ различны, то для вскрытия «в лоб» с тремя известными открытыми текстами потребуется 2^{n+ m +1} операций. Против дифференциального и линейного криптоанализа такие меры обеспечивают защиту на уровне всего нескольких битов ключа. Но с вычислительной точки зрения это очень дешевый способ повышения надежности блочного алгоритма.

9.1.7. Каскадное применение блочных алгоритмов. Произведем шифрование сначала алгоритмом А и ключом К_A, а затем еще раз алгоритмом В и ключом К_B. Этот прием, иногда называемый каскадным применением, егоможно распространить и на большее количество алгоритмов и ключей.

Пессимисты утверждают, что совместное использование двух алгоритмов не гарантирует повышения безопасности. Алгоритмы могут взаимодействовать каким-то хитрым способом, что на самом деле их надежность даже уменьшится. Даже тройное шифрование тремя различными алгоритмами может оказаться не столь безопасным, как вы рассчитываете. Криптография – довольно тонкое искусство, если вы не совсем понимаете, что делаете, то можете легко попасть впросак.

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

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

Для потоковых алгоритмов порядок шифрования значения не имеет. При использовании блочных алгоритмов можно сначала использовать алгоритм А, а затем алгоритм В и наоборот.Между алгоритмами можно вставить хороший потоковый шифр. Это не причинит вреда и может значительно повысить безопасность.

При этом, ключи для каждого алгоритма в каскаде должны быть независимыми. Если алгоритм А использует 64-битовый ключ, а алгоритм В –128-битовый ключ, то получившийся каскад должен использовать 192-битовый ключ. При использовании зависимых ключей у пессимистов гораздо больше шансов оказаться правыми.

9.1.8. Объединение различных блочных алгоритмов. Вот еще один способ объединения нескольких блочных алгоритмов, надежность которого с гарантией не хуже надежности обоих алгоритмов. Для двух алгоритмов (и двух независимых ключей):

1. Генерируется строка случайных битов R того же размера, что и сообщение М;

2. Зашифровывается R первым алгоритмом;

3. Зашифровывается М ⊕ R вторым алгоритмом.

4. Шифртекст сообщения представляет собой объединение результатов этапов 2 и 3.

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

Этот метод можно расширить для нескольких алгоритмов, но добавление каждого алгоритма увеличивает размер шифртекста. Сама по себе идея неплоха, но, не слишком практична.