Сети Фейстела

CRAB

Этот алгоритм был разработан Бертом Калиски [Burt Kaliski] и Мэттом Робшоу [Matt Robshaw] из RSA Laboratories [810]. В основе Crab лежит идея использовать методы однонаправленных хэш-функций для созд а-ния быстрого алгоритма шифрования. Следовательно, Crab очень похож на MD5, и в этом разделе предполаг а-ется, что вы знакомы с материалом раздела 18.5.

У Crab очень большой блок: 1024 байта. Так как Crab был представлен скорее как материал для исследов а-ния, а не реальный алгоритм, конкретной процедуры генерации ключей не было предложено. Авторы рассмо т-рели метод, который позволяет превратить 80-битовый ключ в три вспомогательных подключа, хотя алгоритм позволяет легко использовать ключи переменной длины. В Crab используется два набора больших подключей:

Перестановка чисел с 0 до 255: Р₀, Р_и Р₂, ..., Р₂₅₅-

Массив из 2048 32-битовых чисел: S₀, S_u S₂,..., S₂₀₄₁.

Все эти подключи должны быть вычислены до шифрования или дешифрирования. Для шифрования 1024-байтового блока X

(1) Разделите Хна 256 32-битовых подблоков: Х₀, Х_и Х₂, ..., Х₂₅₅.

(2) Переставьте подблоки Хв соответствии с Р.

(3) For r=0 to 3 For g = 0 to 63

A = X(4g) <<< 2r B = X(4g+1) <<< 2r C = X(4g+2) <<< 2r D = X(4g+3) <<< 2r For step s = 0 to 7

A = A © (В + ЦВ, C, D) + Ssnr+sg+s)

TEMP = D

D = C

C = B

B = A«< 5

A = TEMP X(4g) <<< 2r = A X_{4g+_l) <<< 2r = B

X(4^+2) <« 2r = С

Х(4_я+з) <« 2r = D

(4) Снова объединить X₀, X\, X₂, ..., X₂₅₅, получая шифротекст.
Функции ЦВ, С, D) аналогичны используемым в MD5:

UB, С, D) = {BaC)w ((­ В) л D)

ЦВ, С, D) = (В л D) v (С л (­ D))

ЦВ, C, D) = B®C®D

ЦВ, C, D) = C®(Bv(­ D))

Дешифрирование представляет собой обратный процесс. Генерирование подключей является непростой з а-дачей. Вот как по 80-битовому ключу К может быть сгенерирован массив перестановок Р.

(1) Проинициализируйте К₀, К\, К₂, ..., К₉ 10 байтами К.

(2) For г=10 to 255

K_t = К,_2 © К,.6 © К.л © К,_ло

(3) For г=10 to 255, Р, = i

(4) m=0

(5) For7=0 to 1

For г = 256 to 1 step -1

m = (K₂₅₆,i + K₂₅₇.i) mod i

K2si-i = K25₁_i «< 3

Переставить Р, и Р,_л

S-массив из 2048 32-битовых слов может быть сгенерирован аналогичным образом либо по тому же 80-битовому ключу, либо по другому ключу. Авторы предупреждают, что эти детали должны "рассматриваться только в качестве мотивации, могут быть и другие эффективные схемы, обеспечивающие лучшую безопасность" [810].

Crab был предложен как испытательный стенд для новых идей, а не как рабочий алгоритм. Во многом он использует те же приемы, что и MD5. Бихам заметил, что очень большой блок упрощает криптоанализ алг о-ритма [160]. С другой стороны Crab может позволять эффективно использовать очень большой ключ. В этом случае "упрощение криптоанализа" может ничего не значить.

14.7 SXAL8/MBAL

Это 64-битовый блочный алгоритм из Японии [769]. SXAL8 - это основной алгоритм, a MBAL представляет собой расширенную версию с переменной длиной блока. Так как внутри MBAL выполняется ряд умных дейс т-вий, авторы утверждают, что они могут обеспечить достаточную безопасность за малое число этапов. При длине блока 1024 байта MBAL примерно в 70 раз быстрее, чем DES. К несчастью в [1174] показано, что MBAL чу в-ствителен к дифференциальному криптоанализу, а в [865] - что он чувствителен и к линейному криптоанал изу.

14.8 RC5

RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].

Используется три действия: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную оп е-рацию.

RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2г+2 зависящих от ключа 32-битовых слов - S₀, S_u S₂, ... S_2r+l - где г - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала разделим блок открытого текста на два 32-битовых слова: А и В. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра А, и т.д.) Затем:

A = A + S₀

B = B + S_X

For i = 1 to r:

A = ((A® B) <« B) + 5*2,

В = ((B ® A) <« A) + S_2l+1 Результат находится в регистрах А и В.

Дешифрирование также просто. Разбейте блок открытого текста на два слова, А и В, а затем: For i = r down to 1:

B = ((B - S_2l+1) >»A)®A

A = ((A - S_2i) >» B)®B

B = B - S_X

A = A - S₀

Символ ">»" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 2³².

Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с-сив L из с 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S ини­циализируется при помощи линейного конгруэнтного генератора по модулю 2 ³²:

forJ=lto 2(r +l) - l:

S_l = (S_l.₁ + Q) mod 2³²

Р = 0xb7el5163 и Q = 0х9е3779Ь9, эти константы основываются на двоичном представлении е и phi.

Наконец, подставляем L в S:

i = j = О

А =В = 0

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

A = Si = (Si + A + B)«<l

B = Li = (Li + A + B) <« (А+В)

j = (j+l) mod 2(r +l)

j = (j +l) mod с

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым ел о-вом и 64-битовым блоком, не существуе причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, Р и Q равны 0xb7el51628aed2a6b и 0x9e3779b97f4a7cl5, соответственно. Ривест обозначил различные реализации RC5 как RC5- wlrlb, где w - это размер слова, г - число этапов, а Ъ -длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 2 ²⁴ выбранных открытых текстов для 5 этапов, 2⁴⁵ для 10 этапов, 2⁵³ для 12 этапов и 2⁶⁸ для 15 этапов. Конечно же, существует только 2^м возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утве р-ждает, что плата за лицензирование будет очень мала, но это лучше проверить.

14.9 Другие блочные алгоритмы

Существует алгоритм, называемый в литературе CRYPTO-MECCANO [301], но он не является безопасным. Четыре японских криптографа на Eurocrypt '91 представили алгоритм, основанный на хаотичных отображениях [687, 688], Бихам выполнил криптоанализ этого алгоритма на той же конференции [157]. Другой алгоритм оп и-рается на подмножества некоторого множества случайных кодов [693]. Существует множество алгоритмов, о с-нованных на теории кодов, исправляющих ошибки: вариант алгоритма МакЭлайса (МсЕНесе) (см. раздел 19.7) [786, 1290], алгоритм Rao-Nam [1292, 733, 1504, 1291, 1056, 1057, 1058, 1293], варианты алгоритма Rao-Nam [464, 749, 1503] и алгоритм Li-Wang [964, 1561] - все они небезопасны. CALC также небезопасен [1109]. Алг о-ритм TEA (Tiny Encryption Algorithm, Крошечный алгоритм шифрования) слишком нов, чтобы его коммент и-ровать [1592]. Другим алгоритмом является Vino [503]. MacGuffm, блочный алгоритм, предложенный Мэттом Блэйзом и мной, также небезопасен [189], он был взломан на той же конференции, на которой он был предл о-жен. BaseKing, похожий по философии на З-way, но использующий 192-битовый блок [385], слишком нов, чт о-бы его комментировать.

Кроме того, существует множество блочных алгоритмов, разработанных вне криптографического сообщес т-ва. Некоторые из них используются различными военными и правительственными организациями. У меня нет данных о таких алгоритмах. Существуют также десятки частных коммерческих алгоритмов. Некоторые из них могут быть хороши, некоторые нет. Если компания предполагает, что опубликование ее алгоритмов не будет служить интересам компании, то лучше согласиться с ней и не использовать эти алгоритмы.

14.10 Теория проектирования блочного шифра

В раздел 11.1 я описывал принципы Шеннона для смешения и рассеяния. Спустя пятьдесят лет после того, как эти принципы были впервые сформулированы, они остаются краеугольным камнем проектирования хор о-

шего блочного шифра.

Смешение служит для маскировки взаимосвязей между открытым текстом, шифротекстом и ключом. По м-ните, как даже незначительная зависимость между этими тремя вещами может быть использована при дифф е-ренциальном и линейном криптоанализе? Хорошее смешение настолько усложняет статистику взаимосвязей, что не работают даже мощные криптографические средства.

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

Для безопасности достаточно одного смешения. Алгоритм, состоящий из единственной зависящей от ключа таблицы соответствия 64 битов открытого текста 64 битам шифротекста был бы достаточно сильным. Проблема в том, что для такой таблицы потребовалось бы слишком много памяти: 1020 байтов. Смысл создания блочного шифра и состоит в создании чего-то похожего на такую таблицу, но предъявляющего к памяти более умеренные требования.

Прием состоит в том, чтобы в одном шифре в различных комбинациях периодически перемежать смешив а-ние (с гораздо меньшими таблицами) и диффузию. Это называется результирующим шифром.Иногда блоч­ный шифр, который включает последовательные перестановки и подстановки, называют сетью перестановок-подстановок(substitution-permutation network), или SP-сетью.

Взгляните снова на функцию f в DES. Перестановка с расширением и Р-блок реализуют диффузию, a S-блоки - смешение. Перестановка с расширением и Р-блок линейны, S-блоки - нелинейны. Каждая операция сама по себе очень проста, но вместе они работают очень хорошо.

На примере DES также можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифраПри этом предполагается, что простая функция этапа будет п о-следовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зав и-сели от всех битов ключа и всех битов исходных данных, нужно 5 этапов [1078, 1080]. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.

Большинство блочных алгоритмов являются сетями Фейстела(Felstel networks). Эта идея датируется нача­лом 70-х годов [552, 553]. Возьмите блок длиной п и разделите его на две половины длиной и/2: L и R. Конечно, п должно быть четным. Можно определить итеративный блочный шифр, в котором результат у-го этапа опреде­ляется результатом предыдущего этапа:

U = Дм

К, - это подключ, используемый на /-ом этапе, a f - это произвольная функция этапа.

Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах. Почему это так важно? Гарантируется, что эта функция является обращаемой. Так как для объед и-нения левой половины с результатом функции этапа используется XOR, следующее выражение обязательно я в-ляется истинным:

Ц_л © Щ._и К,)© Щ._и £,■)= Ц_л

Гарантируется, что шифр, использующий такую конструкцию, обратим, если можно восстановить исходные данные f на каждом этапе. Сама функция f неважна, он не обязана быть обратимой. Мы можем спроектировать f настолько сложной, насколько захотим, и нам не потребуется реализовывать два различных алгоритма - один для шифрования, а другой для дешифрирования. Структура сети Фейстела автоматически позаботится об этом.