Анализ переменных блочных шифров

статистика выглядит очень  убедительно. После 8 раундов каждый бит  открытого

текста влияет не менее  чем  на  один  циклический  сдвиг.  Дифференциальная

атака требует 224 подобранных  открытых текстов для 5 раундов,  2  -  для  10

раундов, 253 -  для  12  раундов  и  268  -  для  15  раундов.  Конечно  же,

существует только  264  возможных  открытых  текстов,  поэтому  такая  атака

неприменима к алгоритму с 15 и более раундами. Оценка возможности линейного

криптоанализа показывает, что алгоритм устойчив  к нему  после 6  раундов.

Ривест рекомендует использовать не менее 12, а лучше 16, раундов. Это число

может меняться.

     Компания RSADSI  в  настоящее  время  патентует  RC5,  и  его  название

заявлено как торговая марка. Компания  утверждает,  что  плата  за  лицензию

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

 

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

     Известно множество  путей объединения блочных алгоритмов  для  получения

новых алгоритмов. Создание подобных  схем  стимулируется  желанием  повысить

безопасность,  избежав  трудности  проектирования  нового  алгоритма.   Так,

алгоритм DES относится к  надежным алгоритмам, он  подвергался  криптоанализу

добрых 20 лет и, тем не менее, наилучшим способом  взлома  остается  лобовое

вскрытие.  Однако  ключ  DES  слишком  короток.  Разве  не  плохо  было   бы

использовать DES в качестве компонента другого  алгоритма  с  более  длинным

ключом?  Это  позволило  бы  воспользоваться  преимуществами  обоих  систем:

устойчивостью, гарантированной  двумя десятилетиям криптоанализа,  и длинным

ключом.

     Один из  методов объединения - многократное  шифрование.  В  этом  случае

для шифрования одного и  того же блока открытого текста  алгоритм  шифрования

используется несколько  раз  с  несколькими  ключами.  Каскадное  шифрование

подобно  многократному  шифрованию,  но  использует   различные   алгоритмы.

Известны и другие методы.

     Повторное  шифрование блока открытого текста  одним и  тем  же  ключом  с

помощью того же или другого  алгоритма неэффективно. Повторное  использование

того  же  алгоритма   не   повышает   сложность   лобового   вскрытия.   (Мы

предполагаем,  что  криптоаналитику  известны  алгоритм  и число   операций

шифрования).  При  использовании  различных  алгоритмов  сложность  лобового

вскрытия может, как возрастать, так и оставаться неизменной. При  этом  нужно

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

независимы.

 

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)))

Здесь T1, T2 и Т3 - константы, которые необязательно хранить  в секрете.  Эта

схема гарантирует, что для  любой конкретной пары  ключей  наилучшим  методом

взлома будет вскрытие с известным открытым текстом.

 

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

      Недостаточно    просто    определить    тройное    шифрование,     его

можно    выполнить  несколькими  методами.  Решение  зависит  от   требуемых

безопасности и эффективности.

Вот два возможных режима тройного шифрования:

Внутренний СВС: Файл зашифровывается  в режиме СВС три раза  (Рис.  1а).  Для

этого нужны три различных  вектора инициализации (ВИ).

     Ci=EK3(Si(   Ci-1); Si=DK2(T(   Si-1); Ti=EK1(Pi(   Ti-1)

     Pi=Ti-1(   DK1(Ti); Ti=Si-1(   EK2(Si); Si=Ci-1(   DK3(Ci)

Где С0, S0 и T0 - векторы инициализации.

Внешний СВС: Файл шифруется  с  помощью  тройного  шифрования  (один  раз)  в

режиме СВС (Рис. 5). Для этого нужен один вектор ВИ.

     Ci=EK3(DK2(EK1(Pi(   Ci-1)))

     Pi=Ci-1(   DK1(EK2(DK3(Ci)))

 

                                    [pic]

                   Рис. 5. Тройное шифрование в режиме  СВС

 

      Оба    режима    требуют    больше    ресурсов,    чем     однократное

шифрование:   больше аппаратуры или больше  времени.  Однако  при  установке

трех шифровальных микросхем  производительность внутреннего  СВС не  меньше,

чем при однократном шифровании. Так как три шифрования СВС  независимы,  три

микросхемы могут быть загружены постоянно, подавая свой выход себе на вход.

     Напротив, во  внешнем  СВС обратная  связь лежит вне трех  процессов

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

производительность составит  только  треть  производительности  однократного

шифрования. Чтобы  получить  ту  же  производительность  для  внешнего  СВС,

потребуется чередование  векторов ВИ.

Сi = EK3(DK2(EK1(Pi(   Ci-3)))

где С0, C-1 и С-2 - векторы инициализации. Это не  поможет при программной

реализации, разве только при использовании параллельного  компьютера.

     К сожалению,  менее  сложный  режим   также  и  менее  безопасен.  Бихам

проанализировал   устойчивость   различных   режимов   к   дифференциальному

криптоанализу с подобранными шифртекстами и обнаружил,  что внутренний  СВС

только незначительно  надежнее однократного  шифрования.  Если  рассматривать

тройное шифрование как большой  единый  алгоритм,  его  внутренние  обратные

связи  позволяют  вводить  внешнюю  и  известную  информацию  во  внутреннюю