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

 

     Алгоритмы  Khufu и Khafre запатентованы. Исходный  код этих  алгоритмов

приведен в патенте.

 

3.6. Алгоритм ММВ

     Недовольство  использованием в  одном   из  криптоалгоритмов  64-битового

блока шифрования привело  к созданию Джоаной Дэймен алгоритма под названием

ММВ   (Modular    Multiplication-based    Block    cipher    -    модулярный

мультипликативный блочный  шифр). В  основе  ММВ  лежит  смешивание  операций

различных алгебраических групп. ММВ - итеративный алгоритм, главным  образом

состоящий из линейных действий (XOR и использование ключа)  и параллельного

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

подстановки определяются с  помощью умножения по модулю 232-1  с  постоянными

множителями. В итоге появляется алгоритм, использующий  128-битовый  ключ  и

128-битовый блок.

     Алгоритм ММВ  оперирует 32-битовыми подблоками текста (х0, х1,  х2,  x3)

и 32-битовыми подблоками ключа (k0, k1, k2,  k3).  Это упрощает  реализацию

алгоритма на современных 32-битовых    процессорах.  Чередуясь  с  операцией

XOR, шесть раз используется  нелинейная функция f.  Вот  этот  алгоритм  (все

операции с индексами  выполняются по модулю 4):

     xi = xi (  ki для i = 0..3

     f(х0, х1, х2, x3)

     xi = xi (  ki+1 для i = 0..3

     f(х0, х1, х2, x3)

     xi = xi (  ki+2 для i = 0..3

     f(х0, х1, х2, x3)

     xi = xi (  ki для i = 0..3

     f(х0, х1, х2, x3)

     xi = xi (  ki+1 для i = 0..3

     f(х0, х1, х2, x3)

     xi = xi (  ki+2 для i = 0..3

     f(х0, х1, х2, x3)

 

     Функция f исполняется в три шага:

   1. xi = сi * xi  для i = 0..3 (Если на входе умножения одни  единицы,  то

      на выходе - тоже одни единицы).

   2. Если младший  значащий бит х0 = 1, то  x0  =  х0  (   С.  Если  младший

      значащий  байт х3 = 0, то х3 = х3 (  С.

   3. xi = хi-1 (   xi (   хi+1 для i = 0..3.

 

     Все операции  с индексами выполняются по  модулю  4.  Операция  умножения

на шаге 1 выполняется  по  модулю  232-1.  Специальный  случай  для  данного

алгоритма: если второй операнд  равен 232-1, результат тоже  равен  232-1.  В

алгоритме используются следующие константы:

С = 2ааааааа

c0 = 025f1cdb

c1 = 2*c0

с2=23 *с0

с3=27 *с0

     Константа С - «простейшая» константа без круговой  симметрии,  высоким

троичным весом и нулевым  младшим значащим битом. У константы  с0 есть  другие

особые характеристики. Константы c1, с2  и с3  -  сдвинутые версии  с0,  и

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

     Расшифрование выполняется в обратном порядке, Этапы 2 и 3  инверсны  им

самим. На этапе 1 вместо сi используется сi-1 . Значение с0-1 = 0dad4694 .

 

   1.  Стойкость алгоритма   ММВ

     Схема алгоритма   ММВ  обеспечивает  на  каждом  раунде  значительное  и

независимое от ключа рассеивание. ММВ изначально  проектировался  в  расчете

на отсутствие слабых ключей.

     ММВ – это  уже мертвый алгоритм. Это утверждение  справедливо  по  многим

причинам, хотя криптоанализ ММВ и не был опубликован.  Во-первых,  алгоритм

проектировался без учета  требования устойчивости к линейному  криптоанализу.

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

мультипликативных множителей, но  о  существовании  линейного  криптоанализа

авторы не знали.

      Во-вторых,  Эли  Бихам  реализовал  эффективную атаку с подобранным

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

– просто циклический сдвиг  на 32 бита. В третьих, несмотря на  эффективность

программной  реализации  ММВ,  аппаратное  исполнение  менее  эффективно  по

сравнению с DES.

       Дэймен   предлагает   желающим   улучшить   алгоритм   ММВ    сначала

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

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

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

с целью устранения смещения. Однако  сам  он  не  стал  заниматься  этим,  а

разработал алгоритм 3-Way.

 

3.7. Алгоритм Blowfish

     Blowfish - это алгоритм, разработанный Брюсом Шнайером  специально  для

реализации на больших  микропроцессорах. Алгоритм Blowfish  не  запатентован.

При  проектировании  алгоритма   Blowfish   Шнайер   пытался   удовлетворить

следующим критериям:

    V Скорость.  Программа,  реализующая  алгоритм  Blowfish  на  32-битовых

      микропроцессорах, шифрует данные со скоростью 26 тактов на байт.

    V Компактность. Для  исполнения программной реализации  алгоритма Blowfish

      достаточно 5 Кбайт памяти.

    V Простота. В алгоритме  Blowfish используются только  простые операции:

      сложение, XOR и подстановка из таблицы  по 32-битовому операнду. Анализ

      его схемы  несложен, что снижает риск ошибок  реализации алгоритма.

    V Настраиваемая   стойкость.  Длина  ключа   Blowfish  переменна и может

      достигать  448 бит.

 

      Алгоритм  Blowfish  оптимизирован для применения  в   системах,   не

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

автоматического   шифрования   файлов.   При   реализации   на    32-битовых

микропроцессорах с большим размером  кэша  данных,  например,  процессорах

Pentium и PowerPC, алгоритм Blowfish заметно быстрее DES. Алгоритм  Blowfish

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

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

функции.  Большие  требования  к  памяти  не  позволяют  использовать   этот

алгоритм в смарт-картах.

 

3.7.1. Описание алгоритма  Blowfish

     Blowfish представляет собой 64-битовый блочный алгоритм  шифрования  с

ключом переменной длины. Алгоритм состоит из двух частей:  расширения  ключа

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

в несколько массивов подключей общим размером 4168 байт.

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

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

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

операции   сложения   и   XOR   над   32-битовыми   словами.    Единственные

дополнительные  операции  каждого  раунда  -   четыре   взятия   данных   из

индексированного массива.

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

должны быть вычислены  до начала зашифрования или расшифрования данных.

                                    [pic]

                          Рис 3. Алгоритм Blowfish

 

Р-массив состоит из восемнадцати 32-битовых подключей:

     Р1,Р2,...,Р18

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

     S1,0, S1,1,…, S1,255

     S2,0, S2,2,…, S2,255

     S3,0, S3,3,…, S3,255

     S4,0, S4,4,…, S4,255

Алгоритм  Blowfish  представляет  собой сеть  Файстеля,  состоящей из   16

раундов. На вход подается 64-битовый  элемент  данных  х.  Для зашифрования

данных:

     Разбить   х на  две 32-битовых половины: xL, xR

     Для i от 1 до 16:

         xL = xL (   Pi

         xR = F (xL) (   xR

         Переставить xL и xR

     Переставить  xL и xR (отнять последнюю перестановку)

     xR = xR (   P17

     xL = xL (   P18

     Объединить  xL и xR

                                    [pic]

 

                              Рис. 4. Функция F

 

Функция F рассчитывается следующим  образом ( Рис. 4.):

     Разделить  xL на четыре 8-битовых фрагмента: а, b, с и d

       F(xL)   =   ((S1,a    +    S2,bmod232)(      S3,c)    +    S4,dmod232

 

Расшифрование  выполняется точно так   же,   как   и   зашифрование,    но

Р1,Р2,...,Р18 используются в обратном порядке.

     В реализациях  Blowfish, в которых требуется очень высокая скорость,

цикл должен быть развернут, а все ключи храниться в  кэше.

     Подключи  рассчитываются  с помощью самого  алгоритма Blowfish.  Вот

какова точная последовательность действий.

   1. Сначала Р-массив, а затем четыре S-блока по  порядку инициализируются

      фиксированной  строкой. Эта строка состоит  из шестнадцатеричных цифр ?.

   2. Выполняется операция XOR над Р1 с первыми 32 битами ключа, XOR над Р2

      со вторыми 32 битами ключа, и т.д. для всех  битов  ключа  (вплоть  до

      Р18). Операция XOR выполняется циклически над битами ключа до тех пор,

      пока весь  Р-массив не будет инициализирован.

   3. Используя подключи, полученные на этапах  1  и 2,  алгоритм  Blowfish

      шифрует  строку из одних нулей.

   4. Р1 и Р2 заменяются результатом этапа 3.

   5.  Результат   этапа  3  шифруется  с   помощью   алгоритма   Blowfish   и

      модифицированных  подключей.

   6. Р3 и Р4 заменяются результатом этапа 5.

   7. Далее по ходу  процесса все элементы Р-массива, а затем все четыре  S-

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

      Blowfish.

 

     Всего для  генерации всех необходимых подключей требуется 521  итерация.

Приложения могут сохранять подключи - нет необходимости выполнять процесс

их получения многократно.

 

3.7.2. Стойкость алгоритма  Blowfish

     Серж Воденэ (Serge Vaudenay) исследовал алгоритм Blowfish с известными

S-блоками и r раундами. Как оказалось, дифференциальный  криптоанализ  может

восстановить Р-массив с помощью 28r+1  подобранных открытых  текстов.  Для

некоторых слабых ключей,  которые  генерируют  плохие  S-блоки  (вероятность

выбора такого ключа составляет  1/214),  эта  же  атака  восстанавливает  Р-

массив с помощью всего 24г+1 подобранных открытых текстов.  При  неизвестных

S-блоках эта атака может   обнаружить  использование  слабого   ключа,  но  не

может восстановить  сам  ключ  (и  также  S-блоки  и  Р-массив).  Эта атака

эффективна  только  против  вариантов с уменьшенным   числом   раундов   и

совершенно безнадежна против 16-раундового алгоритма Blowfish.  Разумеется,

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

будут. Слабым называют ключ,  для  которого  два  элемента  данного  S-блока

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

слабости ключа.

     Не известны  факты успешного криптоанализа алгоритма Blowfish.  В целях

безопасности  не  следует  реализовывать  Blowfish  с   уменьшенным   числом

раундов. Компания Kent Marsh Ltd. встроила алгоритм Blowfish в свой  продукт

FolderBolt, предназначенный  для обеспечения защиты  Microsoft  Windows  и

Macintosh. Кроме того, алгоритм входит в Nautilus и PGPfone.

 

3.8. Алгоритм RC5

     RC5 представляет  собой блочный шифр с множеством  параметров:  размером

блока, размером ключа и  числом  раундов.  Он  изобретен  Роном  Ривестом  и

проанализирован в RSA Laboratories.

      В  алгоритме  RC5  предусмотрены  три  операции:   XOR,   сложение   и

циклические сдвиги. На большинстве  процессоров операции циклического  сдвига

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

собой нелинейную функцию. Эти  циклические сдвиги, зависящие  как  от  ключа,

так и от данных - интересная операция.

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

будет  рассмотрен  64-битовый  блок  данных.  Шифрование   использует   2r+2

зависящих от ключа 32-битовых  слов - S0, S1, S2,... S2r+1 - где  r  -  число

раундов. Для зашифрования сначала нужно разделить блок открытого текста  на

два 32-битовых слова: А и В. (При упаковке байтов в слова  в  алгоритме  RC5

соблюдается соглашение о  прямом порядке (little-endian) байтов: первый  байт

занимает младшие биты регистра А и т.д.) Затем:

     A=A + S0

     B = B + S0

     Для i от 1 до r:

         A = ((A(    B) <<< B) + S2i

         В = ((В(    А) <<< А) + S2i+1

Выход находится в регистрах А и В.

     Расшифрование тоже несложно. Нужно разбить блок  открытого текста  на

два слова, А и В, а затем:

     Для i от r до 1 с шагом -1:

         B = ((B - S2i+1) >>> A)(    A

         A = ((A - S2i) >>> B)(    B

     B = B – Si

     A = A - S0

     Символом «>>>»  обозначен циклический  сдвиг   вправо.  Конечно  же,  все

сложения и вычитания  выполняются по модулю 232.

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

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

необходимости заключительное слово нулями. Затем массив  S  инициализируется

при помощи линейного конгруэнтного  генератора по модулю 232:

                          S0                       =                       Р

 

 

 

     Для i от 1 до 2(r + 1) - 1:

         Si = (Si-1 + Q) mod 232

где P = 0xb7e15163 и Q = 0x9e3779b9, эти  константы основываются на  двоичном

представлении е и phi.

Наконец, нужно подставить  L в S:

     i = j = 0

     A = B = 0

Выполнить 3n раз (где п - максимум от 2(r + 1) и с):

         A     =     S     i=     (Si     +     A     +     B)     <<<     3

 

     B= Li = (Li + A + B) <<< (A + B)

     i = (i + 1) mod 2(r +1)

     i = (j +1) mod с

 

     В действительности RC5 представляет собой  семейство  алгоритмов.  Выше

был определен RC5 с 32-битовым  словом и 64-битовым блоком,  но  нет  причин,

запрещающих использовать этот же алгоритм с 64-битовым словом и 128-битовым

блоком. Для w=64, Р  и Q  равны 0xb7e151628aed2a6b  и 0x9e3779b97f4a7c15,

соответственно. Ривест обозначил различные реализации  RC5  как RC5-w/r/b,

где w - размер слова, r - число раундов, a b - длина ключа в байтах.

     RC5 - новый алгоритм, но RSA Laboratories  потратила достаточно  много

времени,  анализируя  его  работу  с  64-битовым  блоком.  После  5  раундов