Композиции шифров

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

ММВ (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) >> 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 раундов

статистика выглядит очень убедительно. После 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. Существуют и другие способы

Страницы: 1, 2, 3, 4, 5