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

открытых текстов. Они  не сумели расширить эту атаку  на  несколько  раундов,

но им удалось получить три значения маски  после  четырех  раундов.  Были  и

другие попытки криптоанализа.

 

3.3.1 Алгоритм REDOC III

     Алгоритм REDOC III представляет собой упрощенную  версию REDOC II,  тоже

разработанную Майклом Вудом. Он оперирует с 80-битовым блоком.  Длина ключа

может изменяться и  достигать  2560  байт  (204800  бит).  Алгоритм  состоит

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

подстановки не используются.

1) Создают таблицу ключей  из 256  10-байтовых  ключей,  используя   секретный

ключ.

2) Создают два 10-байтовых  блока  масок  M1  и  М2.  M1  представляет  собой

результат операции XOR первых 128  10-байтовых  ключей,  а  М2  -  результат

операции XOR вторых 128 10-байтовых ключей.

3) Для шифрования 10-байтового  блока:

    a. Выполняют операцию XOR с первым байтом блока данных и первым  байтом

       M1. Выбирают  ключ  в  таблице  ключей,  рассчитанной  в  раунде  1.

       Используют  вычисленное значение  XOR  в   качестве  индекса  таблицы.

       Выполняют  операцию XOR с каждым, кроме первого,  байтом блока  данных

       и соответствующим  байтом выбранного ключа.

    b. Выполняют операцию XOR со   вторым  байтом  блока данных  и вторым

       байтом M1. Выбирают ключ в таблице  ключей, рассчитанной в раунде  1.

       Используют  вычисленное значение  XOR  в   качестве  индекса  таблицы.

       Выполните  операцию ХОR с каждым, кроме второго, байтом блока данных

       и соответствующим  байтом выбранного ключа.

    c. Продолжают эти действия со всем блоком данных (с 3-10 байтами), пока

       не будет  использован каждый байт для  выбора ключа из  таблицы   после

       выполнения  операции XOR с ним и соответствующим  значением M1.  Затем

       выполняют  операцию XOR с каждым, кроме  использованного для выбора

       ключа,  байтом, и ключом.

    d. Повторяют этапы а-с для М2.

 

     Это несложный  и скоростной алгоритм. На  процессоре  80386  с  тактовой

частотой 33МГц он шифрует данные  со  скоростью  2.75  Мбит/сек.  По  оценке

Вуда, конвейеризированный  процессор с  трактом  данных  64  бит  и  тактовой

частотой 20 МГц может шифровать данные со скоростью свыше 1.28 Гбиг/сек.

      Алгоритм  REDOC   III   нестоек.   Он   уязвим   к   дифференциальному

криптоанализу.  Для восстановления  обеих масок   достаточно   около   223

подобранных открытых текстов.

 

3.4. Алгоритм LOKI

     Алгоритм LOKI разработан  в Австралии и впервые представлен  в 1990  году

в качестве возможной замены DES. В нем используются 64-битовый  блок  и  64-

битовый ключ.

     Используя   дифференциальный  криптоанализ,  Бихам  и Шамир взламывали

алгоритм LOKI с 11 и менее  раундами быстрее, чем  лобовым  вскрытием  [170].

Более  того,  алгоритм  характеризуется  8-битовой  комплементарностью,  что

упрощает лобовое вскрытие в 256 раз.

     Как показал  Ларе Кнудсен (Lars Knudsen), алгоритм LOKI  с 14  и менее

раундами уязвим дифференциальному криптоанализу. Кроме того,  если  в LOKI

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

уязвим дифференциальному  криптоанализу.

 

3.4.1. Алгоритм LOKI91

     В ответ  на описанные  выше  вскрытия  разработчики  LOKI  вернулись   за

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

алгоритм LOKI91. (Предыдущая версия LOKI была переименована в LOKI89).

       Чтобы   повысить   устойчивость   алгоритма    к    дифференциальному

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

внесены следующие изменения:

   1. Алгоритм генерации   подключей  модифицирован с тем,  чтобы половины

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

   2. Алгоритм генерации  подключей  модифицирован так,  что число позиций

      циклического  сдвига левого подключа составляло то 12, то 13 битов.

   3. Исключены начальная  и заключительная операции XOR с  блоком и ключом.

   4. Изменена функция S-блока с целью сгладить профили XOR S-блоков  (чтобы

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

      исключить  все значения х, для которых f(x) = 0, где f - комбинация Е-,

      S- и Р-блоков.

 

     Алгоритм LOKI не  запатентован - реализовать и использовать  LOKI  может

кто угодно.

 

3.4.2. Описание алгоритма  LOKI91

      Механизм  алгоритма  LOKI91  подобен  DES  (Рис.   2).   Блок   данных

расщепляется на левую  и правую половины и проходит 16  раундов,  что  весьма

напоминает  DES.  В  каждом  раунде  правая  половина  сначала  подвергается

операции XOR с частью ключа, а затем расширяющей перестановке (Табл. 3).

 

                                    [pic]

                           Рис. 2. Алгоритм LOKI91

                    Таблица 3. Перестановка с расширением

4, |3, |2, |1, |32, |31, |30, |29, |28, |27, |26,  |25,  |  |28,  |27,  |26,

|25, |24, |23, |22, |21, |20, |19, |18, |17, |  |20,  |19,  |18,  |17,  |16,

|15, |14, |13, |12, |11, |10, |9, | |12, |11, |10, |9, |8, |7, |6,  |5,  |4,

|3, |2, |1 | |

     48-битовый выход  разделяется  на  четыре  12-битовых   блока.  В  каждом

блоке  выполняется такая подстановка с использованием  S-блока:  берется

каждый 12-битовый  вход,  2  старших  и  2  младших  бита  используются  для

образования номера r, а восемь внутренних битов образуют номер с.  Выход S-

блока, О, имеет следующее  значение:

     О(r,с) = (с + ((r*17) ( 0xff) & 0xff)31 mod Pr

 

                           Таблица 4. Значения Pr

r |1, |2, |3, |4, |5, |6, |7, |8, |9, |10, |11, |12, |13, |14,  |15,  |16  |

|Pr |375, |379, |391, |395, |397, |415, |419, |425, |433, |445, |451,  |463,

|471, |477, |487, |499 | |

     Затем четыре  8-битовых  результата  снова   объединяются,  образуя  32-

битовое число,  которое  подвергается  операции  перестановки,  описанной  в

табл. 3. Наконец, для получения  новой левой  половины  выполняется  операция

XOR правой половины с  прежней левой половиной, а  левая  половина  становится

новой правой  половиной.  После  16  раундов  для  получения  окончательного

шифртекста снова выполняется операция XOR над блоком и ключом.

 

                  Таблица 5. Перестановка с помощью  Р-блока

32, |24, |16, |8, |31, |23, |15, |7, |30, |22, |14, |6, |29, |21,  |13,  |5,

| |28, |20, |12, |4, |27, |19, |11, |3, |26, |18, |10, |2, |25, |17, |9,  |1

| |

     Подключи генерируются  из  ключа достаточно  прямолинейно.  64-битовый

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

служит левая половина. Далее она циклически сдвигается влево на 12 или  1  3

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

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

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

 

3.4.3. Криптоанализ алгоритма LOKI91

     Кнудсен предпринял попытку криптоанализа LOKI91,  но  нашел,  что этот

алгоритм устойчив к дифференциальному криптоанализу.  Все же  он  обнаружил

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

который упрощает лобовое вскрытие почти вчетверо.  Это метод опирается на

слабость схемы развертки  ключей. Кроме того, этот метод  пригоден  и  в  том

случае,  когда алгоритм  используется  в качестве  однонаправленной   хэш-

функции.

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

помощью 232 подобранных открытых текстов для выбранных ключей или с  помощью

248 известных открытых  текстов для выбранных ключей. Эффективность атаки  не

зависит от числа раундов  алгоритма. (В той же работе Бихам вскрывает LOKI89

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

текстов  для  выбранных  ключей  или  233  известных  открытых  текстов  для

выбранных  ключей).  Усложнив  схему  развертки  ключа,  несложно   повысить

устойчивость LOKI91 к подобной атаке.

 

3.5. Алгоритмы Khufu и Khafre

     В 1990 году  Ральф Меркл  (Ralph  Merkle)  предложил два алгоритма.  В

основу конструкции заложены следующие принципы:

    V 56-битовый размер  ключа DES слишком мал. Так как  стоимость  увеличения

      размера  ключа  пренебрежимо  мала  (компьютерная  память  недорога  и

      доступна), длину ключа следует увеличить.

    V Широкое использование  в DES перестановок, хотя и удобно  для аппаратных

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

      скоростные  реализации DES  выполняют  перестановки  с  помощью  таблиц

      подстановок.  Таблицы подстановок могут обеспечить  те же характеристики

      «рассеивания»,  что  и  собственно  перестановки,  и  намного  повысить

      гибкость  реализации.

    V S-блоки DES, содержащие  всего 64 4-битовых  элементов,  слишком  малы.

      Теперь, с  увеличением объема памяти, должны  возрасти и S-блоки.  Более

      того, все  восемь S-блоков в DES используются  одновременно. Хотя это  и

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

      ненужным  ограничением. Должны быть реализованы  больший размер S-блоков

      и последовательное (а не параллельное) их использование.

    V   Общепризнанно,   что   начальная   и   заключительная   перестановки

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

    V Все скоростные реализации DES  заранее  вычисляют  ключи  для  каждого

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

    V В  отличие от  DES,  критерии  проектирования  S-блоков  должны  быть

      общедоступны.

 

      В  настоящее   время  к  этому  перечню   Меркл,  возможно,  добавил бы

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

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

 

 

 

3.5.1 Алгоритм Khufu

     Khufu - это 64-битовый блочный шифр. 64-битовый открытый  тест  сначала

расщепляется на две 32-битовые  половины, L и  R.  Над  обеими  половинами  и

определенными частями ключа  выполняется  операция  XOR.  Затем,  аналогично

DES, результаты проходят  некоторую  последовательность  раундов.  В  каждом

раунде младший значащий байт L используется как вход S-блока. У каждого S-

блока 8 входных битов  и 32 выходных бита.  Далее  выбранный  в  S-блоке  32-

битовый  элемент  подвергается  операции  XOR  с  R.  Затем   L   циклически

сдвигается на число, кратное  восьми битам, L и R меняются местами,  и  раунд

завершается. Сам S-блок не статичен,  он  меняется  каждые  восемь  раундов.

Наконец, по окончании последнего раунда, над L и R выполняется операция  XOR

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

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

начале и конце исполнения алгоритма, главное назначение ключа - генерация S-

блоков. Эти S-блоки секретны, по существу, это часть  ключа.  Полный  размер

ключа алгоритма Khufu  равен 512  бит (64  байт),  алгоритм  предоставляет

способ генерации S-блоков по  ключу.  Вопрос  о  достаточном  числе  раундов

остается открытым. Как  указывает Меркл, 8-раундовый алгоритм Khufu уязвим  к

вскрытию с подобранным  открытым текстом. Он рекомендует использовать 16,  24

или 32 раунда. (Меркл  ограничивает  количество  раундов числами,  кратными

восьми).

     Поскольку  S-блоки Khufu зависят от ключа и секретны, алгоритм  устойчив

к дифференциальному криптоанализу. Известна дифференциальная  атака на  16-

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

открытых текстов, однако этот метод не удалось расширить на  большее число

раундов. Если принять, что  лучший метод взлома  Khufu  -  лобовое вскрытие,

стойкость алгоритма  впечатляет.  512-би-овый  ключ  обеспечивает  сложность

вскрытия 2512 - это огромное число в любом случае.

 

3.5.2. Алгоритм Khafre

     Khafre - это вторая криптосистема, предложенная Мерклом. (Khufu  (Хуфу)

и Khafre (Хафр) - имена египетских фараонов).  Конструкция этого алгоритма

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

предварительные вычисления. S-блоки не зависят  от  ключа.  Вместо  этого  в

Khafre используются  фиксированные S-блоки.  Блок  шифрования  подвергается

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

и после каждых восьми раундов  шифрования.

     Меркл предполагал, что в алгоритме Khafre следует использовать 64-  или

128-битовые ключи и что  в этом алгоритме понадобится  большее число  раундов,

чем в Khufu. Это, наряду с тем,  что каждый  раунд Khafre  сложнее раунда

Khufu, делает Khafre  менее скоростным.  Зато  алгоритму Khafre  не  нужны

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

данных.

     В 1990 году  Бихам  и Шамир применили свой  метод дифференциального

криптоанализа к алгоритму Khafre. Им удалось взломать  16-раундовый Khafre

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

шифрований.  На  их  персональном  компьютере   это   заняло   около   часа.

Преобразование этой атаки  в атаку с  известным  открытым  текстом  потребует

около 238 шифрований.  Алгоритм  Khafre  с 24  раундами  можно взломать  с

помощью атаки с подобранным  открытым текстом за 253 шифрования, а с  помощью

атаки с известным открытым текстом – за 259 шифрования.