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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СВЯЗИ, ИНФОРМАТИЗАЦИИ И ТЕЛЕКОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ РЕСПУБЛИКИ УЗБЕКИСТАН

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ  ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

 

 

 

 

 

 

                                         КУРСОВАЯ РАБОТА

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                                                Выполнил : Рузикулов А.

 

Гр. 235-10  АХр

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                     Ташкент 2013

Блочные шифры

 

3.1. Алгоритм Lucifer

     В конце  шестидесятых годов корпорация IBM  запустила  исследовательскую

программу  по  компьютерной  криптографии,  названную  Lucifer  (Люцифер)  и

руководимую сначала Хорстом  Файстелем  (Horst  Feistel),  а затем Уолтом

Тачменом (Walt Tuchman). Такое же имя - Lucifer - получил блочный алгоритм,

появившийся в результате  этой  программы в начале  семидесятых годов.  В

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

таким именем. Один из них  содержит ряд пробелов  в  спецификации  алгоритма.

Все это привело к заметной путанице.

     Алгоритм Lucifer представляет собой сеть  перестановок  и подстановок,

его основные блоки напоминают блоки алгоритма DES. В DES  результат  функции

f складывается операцией XOR  с входом  предыдущего раунда,  образуя вход

следующего раунда. У S-блоков алгоритма Lucifer 4-битовые входы и выходы,

вход S-блоков представляет собой перетасованный выход  S-блоков  предыдущего

раунда, входом S-блоков первого  раунда служит  открытый  текст.  Для  выбора

используемого S-блока из двух возможных  используется  бит  ключа.  (Lucifer

реализует все это в  едином Т-блоке с  9  битами  на  входе  и  8  битами  на

выходе). В отличие от  алгоритма DES,  половины  блока между раундами  не

переставляются, да и само понятие половины  блока  в  алгоритме  Lucifer  не

используется. У этого  алгоритма  16  раундов,  128-битовые  блоки  и  более

простая, чем в DES, схема  развертки ключа.

     Применив дифференциальный криптоанализ к первой  реализации  алгоритма

Lucifer, Бихам и Шамир показали, что Lucifer  с 32-битовыми  блоками и 8

раундами можно взломать с помощью 40 подобранных  открытых  текстов  за  229

операций. Этот же метод позволяет  вскрыть Lucifer с 128-битовыми  блоками и

8 раундами с помощью  60 подобранных открытых текстов  за  253  шагов.  Другая

дифференциальная  атака  вскрывает  18-раундовый,  128-битовый   Lucifer   с

помощью 24 подобранных открытых  текстов  за  221  операций.  Во  всех  этих

вскрытиях   использовались   стойкие   S-блоки   алгоритма   DES.   Применив

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

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

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

основе связанных ключей  позволяет  взломать  128-битовый  Lucifer  с любым

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

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

реализация Lucifer еще слабее.

     Некоторые  полагают, что Lucifer надежнее DES из-за большей длины ключа

и малочисленности опубликованных сведений. Но очевидно, что это не  так.  На

алгоритм Lucifer выданы нескольких патентов США. Сроки действия  всех  этих

патентов уже истекли.

3.2. Алгоритм Madryga

     В. Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм  в 1984

году. Его можно эффективно реализовать программным путем:  в  алгоритме  нет

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

     Стоит  перечислить   задачи,  которые  решал   автор  при  проектировании

алгоритма:

    V Без помощи ключа открытый текст  невозможно  получить  из  шифртекста.

      (Это означает  только то, что алгоритм стоек).

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

      шифртекста  и открытого текста,  должно  быть  статистически   равно

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

      (Это означает, что никакое вскрытие с открытым текстом не  может быть

      эффективнее  лобового вскрытия).

    V Опубликование  алгоритма не влияет на  стойкость   шифра.  (Безопасность

      полностью  определяется ключом).

    V Изменение одного  бита  ключа  должно  радикально  изменять  шифртекст

      одного  и того же открытого текста, а изменение одного  бита  открытого

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

      (лавинный  эффект).

    V Алгоритм должен  содержать  некоммутативную   комбинацию  подстановок  и

      перестановок.

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

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

    V  Избыточные  группы  битов  открытого   текста  должны  быть  полностью

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

    V Длина шифртекста должна совпадать с длиной открытого текста.

    V Между любыми возможными ключами и особенностями шифртекста недопустимы

      простые  взаимосвязи.

    V Все возможные ключи должны обеспечивать стойкость  шифра.  (Не  должно

      быть слабых  ключей).

    V  Длина   ключа  и  текст  должны  иметь  возможность  варьирования  для

      реализации  различных требований к безопасности.

    V  Алгоритм  должен  допускать  эффективную   программную  реализацию  на

      мэйнфреймах, мини- и микрокомпыотерах и с помощью дискретной  логики.

      (По существу, число функций,  используемых  в алгоритме,  ограничено

      операциями XOR и битовым сдвигом).

 

     Алгоритм DES удовлетворял  первым девяти требованиям, но  последние  три

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

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

тех, кто считает, что 56 битов - слишком малая величина.  Такие  люди  могут

реализовать этот алгоритм с любой длиной ключа. А  любой,  кто  когда-нибудь

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

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

 

3.3.1. Описание алгоритма  Madryga

     Алгоритм  Madryga  состоит из  двух  вложенных циклов.  Внешний цикл

повторяется  восемь  раз  (для  гарантии  надежности  число   циклов   можно

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

Внутренний  цикл  превращает  открытый  текст  в  шифртекст  и   выполняется

однократно над каждым 8-битовым  блоком  (байтом)  открытого  текста.  Таким

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

алгоритмом.

      Итерация  внутреннего  цикла  оперирует   с  3-байтовым  окном  данных,

называемым рабочим кадром (Рис. 1.).  Это  окно  сдвигается  на  1  байт  за

итерацию. (При работе с последними 2 байтами данные  полагаются  циклически

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

переменное число позиций, а для последнего байта исполняется  операция XOR  с

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

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

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

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

влияют результаты XOR. Благодаря  этому процесс в целом обратим.

 

|Движущийся     |WF(1)  |WF(2)  | |WF(3)   |         |        |       |

|рабочий кадр   |       |       | |        |         |        |       |

|               |8 битов|8 битов| |8 битов |         |        |       |

|               |ROT            | |        |         |        |       |

|Перемещение    |Объект сдвига  | | |Счетчик сдвига   |        |       |

|               |16 бит         | |3 бита             |        |       |

|               | | | |XOR      |                   |        |       |

|Хэш ключа      |1|2|3|…        |KL                 |        |       |

|               | | | |         |                   |        |       |

 

                   Рис. 1. Одна итерация алгоритма  Madryga

 

     Поскольку  каждый байт данных влияет  на два байта слева и на  один  байт

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

16 байтов слева и 8 байтов  справа.

      При   зашифровании  каждая  итерация  внутреннего цикла устанавливает

рабочий кадр на предпоследний  байт открытого текста и циклически  перемещает

его  к  третьему  с  конца  байту  открытого  текста.  Сначала   весь   ключ

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

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

чтобы минимизировать избыточные операции с битами ключа). Младшие  три  бита

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

остальных двух байтов. Далее  конкатенация  двух  старших  байтом  циклически

сдвигается влево на переменное число битов (от 0 до 7).  Затем  над  младшим

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

Наконец  рабочий  кадр  смещается  вправо  на  один  байт  и  весь   процесс

повторяется.

       Случайная   константа   предназначена   для   превращения   ключа   в

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

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

константой.   Для   64-битового   ключа   Мадрига   рекомендует    константу

0x0fle2d3c4b5a6978.

     При расшифровании процесс повторяется в обратном  порядке.  В каждой

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

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

направлении до байта, расположенного  на  2  байта левее последнего  байта

шифртекста. 2 байта шифртекста в процессе циклически  сдвигаются  вправо,  а

ключ - влево. После циклических  сдвигов выполняется операция XOR.

 

3.2.2. Криптоанализ алгоритма Madryga

     Ученые Квинслендского технического университета (Queensland  University

of Technology) исследовали алгоритм  Madryga  и некоторые другие  блочные

шифры. Они обнаружили, что  лавинный  эффект  при  преобразовании  открытого

текста в шифртекст в этом алгоритме не проявляется. Кроме того,  во  многих

шифртекстах доля единиц превышала доли нулей.

     Формальный  анализ  этого  алгоритма   не  производит  впечатления   особо

надежного. При поверхностном  знакомстве с ним Эли Бихам пришел  к  следующим

выводам:

    Алгоритм состоит  только из линейных операций (циклический  сдвиг и XOR),

    незначительно изменяемых в зависимости от данных.

 

    Это ничуть  не напоминает мощь S-блоков DES.

 

    Четность всех  битов шифртекста и открытого текста неизменна и зависит

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

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

    текста.

 

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

однако этот алгоритм не вызывает  у  многих  криптоаналитиков  положительных

эмоций. Некоторые вообще не рекомендуют использовать алгоритм Madryga.

 

3.3. Алгоритм REDOC

     REDOC II представляет  собой еще один  блочный   алгоритм,  разработанный

Майклом Вудом (Michael Wood) для корпорации Cryptech. В нем используются 20-

байтовый (160-битовый) ключ и 80-битовый блок.

      Алгоритм  REDOC  II  выполняет   все   манипуляции   -   перестановки,

подстановки и операции XOR с ключом - с байтами. Этот  алгоритм  удобен  для

программной реализации. В REDOC II использованы переменные таблицы  функций.

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

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

II используются зависимые  от ключа и  открытого   текста  наборы  таблиц  (по

сути, S-блоки). В REDOC II 10  раундов,  каждый  раунд  состоит  из  сложной

последовательности манипуляций  с блоком.

     Другая уникальная  особенность  REDOC  II  —  использование   масок.  Это

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

данной функции для  данного раунда. Для выбора  таблиц  функций  используются

как значение данных, так  и маски.

     При условии,  что самое эффективное средство  взлома  этого  алгоритма  -

лобовое  вскрытие,  REDOC  II  весьма  надежен:  для восстановления   ключа

требуется 2160 операций. Томас  Кузик (Thomas Cusick)  выполнил  криптоанализ

одного раунда REDOC II, но расширить  вскрытие на несколько  раундов  ему  не

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

выполнили криптоанализ одного раунда REDOC II  с помощью 2300  подобранных