Патенты и лицензии

Ya

X : 16-битовый подблок открытого текста

Y, ■ 16-битовый подблок шифротекста

Z/^r) : 16-битовый подблок ключа

Ф : побитовое "исключающее или" (xoR) 16-битовых подблоков

ЕВ: сложение по модулю 2¹⁶ 16-битовых целых

© : умножение по модулю 2¹⁶+1 16-битовых целых при условии,

что нулевой подблок соответствует 2

Рис. 13-10. PES.

Вилли Майер (Willi Meier) исследовал три алгебраических операции IDEA и показал, что, хотя они нес о-вместимы, есть случаи, когда эти операции можно упростить так, чтобы в некоторой степени облегчить [1050]. Его вскрытие 2-этапного IDEA оказалось эффективнее вскрытия грубой силой (2 ⁴² операций), но для IDEA с 3 и более этапами эффективность этого вскрытия была ниже вскрытия грубой силой. Безопасность полного 8-этапного IDEA осталась непоколебимой.

Джоан Дэймен (Joan Daemen) открыла класс слабых ключей IDEA [405, 409]. Эти ключи не являются ел а-быми в том смысле, в котором слабы некоторые ключи DES, для которых функция шифрования обратна самой себе. Слабость этих ключей состоит в том, что взломщик может легко определить их с помощью вскрытия с выбранным открытым текстом. Например, слабым является следующий ключ (в шестнадцатиричной записи):

0000,0000,0х00,0000,0000,000х,хххх,х000

В позиции "х" может стоять любая цифра. При использовании такого ключа побитовое XOR определенных пар открытых текстов равно побитовому XOR получившихся пар шифротекстов.

В любом случае вероятность случайной генерации одного из таких слабых ключей очень мала: 1/2 ⁹⁶. Опас­ность случайно выбрать такой ключ практически не существует. К тому же, несложно модифицировать IDEA так, чтобы исключить наличие слабых ключей - достаточно выполнить XOR каждого подключа с числом OxOdae [409].

Хотя попыток выполнить криптоанализ IDEA было много, мне неизвестно ни об одной успешной.

Режимы работы и варианты IDEA

IDEA может работать в любом из режимов работы блочного шифра, описанных в главе 9. Против двойных реализаций IDEA может быть предпринято то же вскрытие "встреча посередине", что и против DES (см. раздел

15.1). Однако, так как ключ IDEA более чем в два раза длиннее ключа DES, это вскрытие непрактично. Объем нужной для такого вскрытия памяти составит 64*2 ¹²⁸ битов, или 10³⁹ байтов. Может быть во вселенной и доста­точно материи, чтобы построить такое хранилище, но я в этом сомневаюсь.

Если вы учитываете возможность использования параллельной вселенной, используйте утроенную реализ а-цию IDEA (см. раздел 15.2):

C = E_K3(D_K2(E_Ki(P)))

Такая реализация устойчива против вскрытия "встреча посередине".

Кроме того, почему бы вам не реализовать IDEA независимыми подключами, особенно если ваши средства распределения ключей позволяют работать с длинными ключами. Для IDEA нужно всего 52 16-битовых ключа, общей длиной 832 битов. Этот вариант определенно безопасней, но никто не сможет сказать насколько.

В наивной модификации может быть увеличен вдвое размер блока. Алгоритм также прекрасно работал бы с 32-битовыми подблоками вместо 16-битовых и с 256-битовым ключом. Шифрование выполнялось бы быстрее, и безопасность возросла бы в 2³² раза. Или нет? Теория, на которой основан алгоритм, опирается на то, что 2¹⁶+1 является простым числом. А 2³² + 1 простым числом не является. Может быть алгоритм и можно изм е-нить так, чтобы он работал, но его безопасность будет совсем иной. Лай говорит, что заставить работать такой алгоритм будет нелегко [926].

Хотя IDEA кажется намного безопаснее DES, не всегда можно легко заменить один алгоритм другим в с у-ществующем приложении. Если ваша база данных и шаблоны сообщений могут работать с 64-битовым кл ю-чом, реализация 128-битового ключа IDEA может быть возможной.

Для таких приложений создайте 128-битовый ключ, объединив 64-битовый ключ сам с собой. Не забывайте, что эта модификация заметно ослабляет IDEA.

Если вас больше волнует скорость работы, а не безопасность, попробуйте вариант IDEA с меньшим числом этапов. Сегодня лучшее вскрытие IDEA быстрее вскрытия грубой силой только для 2.5 и менее этапов [1050], 4-этапный IDEA будет в два раза быстрее и, насколько мне известно, его безопасность не уменьшится.

Caveat Emptor¹

IDEA - это относительно новый алгоритм, многие вопросы пока остаются открытыми. Образует ли IDEA группу? (Лай думает, что нет [926].) Не существует ли пока не открытых способов вскрытия этого шифра? У IDEA твердая теоретическая основа, но снова и снова казавшиеся безопасными алгоритмы капитулируют перед новыми формами криптоанализа. Ряд групп академических и военных исследователей не опубликовали свои результаты криптоанализа IDEA. Возможно, кто-нибудь уже добился или когда-нибудь добьется успеха.

IDEA запатентован в Европе и Соединенных Штатах [1012, 1013]. Патент принадлежит Ascom-Tech AG. Для некоммерческого использования лицензирование не нужно. При заинтересованности в лицензии для ко м-мерческого применения алгоритма следует обратиться по адресу Ascom Systec AG, Dept CMW, Cewerbepark, CH-5506, Mgenwil, Switzerland; +41 64 56 59 83; Fax: +41 64 56 59 90; idea@ascom.ch.

13.10 MMB

Недовольство использованием в IDEA 64-битового блока шифрования привело к созданию Джоном Дэйм о-ном алгоритма под названием MMB (Modular Multiplication-based Block cipher, модульный блочный шифр, и с-пользующий умножения) [385, 405, 406]. В основе ММВ лежит теория, используемая и в IDEA: перемешива то­щие операции из различных групп. ММВ - это итеративный алгоритм, главным образом состоящий из лине й-ных действий (XOR и использование ключа) и параллельное использование четырех больших нелинейных и з-меняющих обычный порядок подстановок. Эти подстановки определяются с помощью умножения по модулю 2³²-1 с постоянными множителями. Результатом применения этих действий является алгоритм, использующий и 128-битовый ключ и 128-битовый блок.

ММВ оперирует 32-битовыми подблоками текста (х₀, х_ь х₂, х₃) и 32-битовыми подблоками ключа (к₀, к_и к₂, к₃). Это делает удобным реализацию алгоритма на современных 32-битовых процессорах. Чередуясь с XOR, шесть раз используется нелинейная функция f. Вот этот алгоритм (все операции с индексами выполняются по модулю 3):

х, = х, © к„ для i = 0 до 3

¹ Предупреждение покупателю

f(x₀, х_ь x₂, x₃)

х,-=х,-©£_ж,дляг = ОдоЗ

f(x₀, x_u x₂, x₃)

x, = x, © £,₊₂, для i = О до 3

f(x₀, x_b x₂, x₃)

x, = x, © А:,, для i = О до 3

f(x₀, x_b x₂, x₃)

x,■= x,■© £_ж, для i = О до 3

f(x₀, x_b x₂, x₃)

x, = x, © £,₊₂, для i = О до 3

f(x₀, x_b x₂, x₃)

У функции f три этапа:

(1) xj = с,■ * х„ для г = 0 до 3 (Если на входе умножения одни единицы, то на выходе - тоже одни единицы.)

(2) Если младший значащий бит х₀ — 1, то х₀ — х₀ © С. Если младший значащий бит х₃ — О, то х₃ — х₃ © С.

(3) х, = х,_ч © х, © х_ж, для г = 0 до 3

Все операции с индексами выполняются по модулю 3. Операция умножения на этапе (1) выполняется по м о-дулю 2³²-1. В данном алгоритме если второй операнд - это 2³²-1, то результат также равен 2³²-1. В алгоритме используются следующие константы:

С= 2ааааааа

со = 025flcdb

ci = 2 * со

с₂= 2³ * со

с₃ = 2⁷ * со

Константа С - это "простейшая" константа с высоким троичным весом, нулевым младшим значащим битом и без круговой симметрии. У константы сО несколько иные характеристики. Константы с _ь с₂ и с₃ являются сме­щенными версиями со, и используются для предотвращения вскрытий основанных на симметрии. Подробности можно найти в [405].

Дешифрирование является обратным процессом. Этапы (2) и (3) заменяются на свою инверсию. На этапе (1) вместо с,"¹ используется с„ с,"¹ = 0dad4694.

Безопасность ММВ

Схема ММВ обеспечивает на каждом этапе значительное и независимое от ключа рассеяние. В IDEA pa c-сеяние до определенной степени зависит от конкретных подключей. В отличие от IDEA у ММВ нет слабых ключей.

К сожалению ММВ - это умерший алгоритм [402]. Это утверждение справедливо по многим причинам, хотя криптоанализ ММВ и не был опубликован. Во первых, он проектировался без учета требований устойчивости к линейному криптоанализу. Выбор мультипликативных множителей обеспечил устойчивость к дифференциал ь-ному криптоанализу, но о линейном криптоанализе авторам алгоритма было еще неизвестно.

Во вторых, Эли Бихам реализовал эффективное вскрытие с выбранным ключом [160], использующеее тот факт, что все этапы идентичны, а ключ при использовании просто циклически сдвигается на 32 бита. В третьих, несмотря на то, что программные реализации ММВ были бы очень эффективны, в аппаратном исполнении а л-горитм менее эффективен, чем DES.

Дэймон предлагает, что тот, кто захочет улучшить ММВ, должен сначала проанализировать умножение по модулю с помощью линейного криптоанализа и подобрать новый множитель, а затем сделать константу С ра з-личной для каждого этапа [402]. Затем, улучшив использование ключа, добавляя к ключам этапов константы с целью устранения смещения. Но сам не стал заниматься этим и разработал З-Way (см. раздел 14.5).

13.11 CA-1.1

СА - это блочный шифр, основанный на клеточных автоматах и разработанный Говардом Гутовицом (Howard Gutowitz) [677, 678, 679]. Он шифрует 384-битовые блоки открытого текста 1088-битовым ключом (на самом деле используется два ключа - 1024-битовый и 64- битовый). Из-за природы клеточных автоматов алг о-ритм наиболее эффективен при реализации в больших параллельных интегрированных схемах.

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

Обратимые правила (простые параллельные перестановки подблоков состояния) нелинейны. Необратимые правила полностью определяются ключом, а обратимые зависят как от ключа, так и от случайной информации, вставленной в ходе шифрования необратимыми правилами.

СА-1.1 основан на структуре блочных связей. То есть, обработка блока сообщения частично отделена от о б-работки потока случайной информации, вставленной при шифровании. Эта случайная информация служит для связи друг с другом стадий шифрования. Она также может быть использована для связи с потоком шифроте к-ста. Информация связи генерируется как часть шифрования.

Так как СА-1.1 представляет собой новый алгоритм, слишком рано делать какие-либо заявления о его без о-пасности. Гутовиц упоминает некоторые возможные вскрытия, включая дифференциальный криптоанализ, но ему не удалось вскрыть алгоритм. В качестве стимула Гутовиц предложил награду в 1000 долларов для "первого человека, который разработает доступную процедуру вскрытия СА-1.1."

СА-1.1 запатентован [678], но доступен для некоммерческого использования. При необходимости получить лицензию на алгоритм или объявленную награду за криптоанализ обращайтесь к Говарду Гутовицу по адресу Howard Cutowitz, ESPCI, Laboratorie d'Electronique, 10 rue Vauquelin, 75005 Paris, France.

13.12 SKIPJACK

Skipjack разработан NSA в качестве алгоритма шифрования для микросхем Clipper и Capstone (см. разделы 24.16 и 24.17). Так как этот алгоритм объявлен секретным, его подробности никогда не публиковались. Он б у-дет реализован только как защищенная от взлома аппаратура.

Этот алгоритм объявлен секретным не потому, что это повышает его надежность, а потому что NSA не х о-чет, чтобы Skipjack использовался без механизма условного вручения ключей Clipper. Агентство не хочет, чт о-бы программные реализации алгоритма распространились по всему миру.

Безопасен ли Skipjack? Если NSA захочет создать безопасный алгоритм, оно, скорее всего, это сделает. С другой стороны, если NSA захочет создать алгоритм с лазейкой, то оно сможет сделать и это. Вот что было опубликовано [1154, 462].

— Это итеративный блочный шифр.

— Размер блока - 64 бита.

— Алгоритм использует 80-битовый ключ.

— Он может быть использован в режимах ЕСВ, СВС, 64-битовый OFB, либо 1-, 8-, 16-, 32- или 64-битовый CFB.

— Операция шифрования или дешифрирования состоит из 32 этапов.

— NSA начало работу над ним в 1985 и завершило проверку в 1990.

В документации на микросхему Mykotronx Clipper утверждается, что задержка в выдаче результата, прис у-щая алгоритму Skipjack, составляет 64 такта. Это означает, что на каждый этап приходится два такта: один предположительно для подстановки с помощью S-блока, а другой - для заключительного XOR в конце каждого этапа. (Не забывайте, перестановки при аппаратных реализациях не занимают времени.) В документации Mykotronx эта двухтактная операция называется "G-блоком", а все вместе - "сдвигом". (Часть G-блока носит название "F-таблицы" и является таблицей констант, а может быть таблицей функций.)

По одним слухам Skipjack использует 16 S-блоков, а по другим для хранения S-блоков нужно всего 128 байт

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

Еще один слух утверждает, что этапы Skipjack, в отличие от DES, работают не с половиной блока. Это вм е-сте с замечанием о "сдвигах" и случайном заявлении на Crypto '94 о том, что в Skipjack применяется "48-битовая внутренняя структура", позволяет сделать вывод, что алгоритм по своей схеме похож на SHA (см. ра з-дел 18.7), но использует четыре 16-битовых подблока. Три подблока, обработанные зависящей от ключа одн о-направленной функцией, дают 16 битов, которые подвергаются операции XOR с оставшимся подблоком. Затем весь блок циклически сдвигается на 16 битов и поступает на вход следующего этапа, или сдвига. При этом та к-же используются 128 байтов данных S-блока. Я подозреваю, что S-блоки зависят от ключа.

По своей структуре Skipjack вероятно похож на DES. NSA понимает, что его защищенная от взлома аппар а-тура в конце концов будет вскрыта и исследована, они не будут рисковать никакими передовыми криптограф и-ческими методами.

То, что NSA планирует использовать алгоритм Skipjack для шифрования своей Системы защиты сообщений (Defense Messaging System, DMS), свидетельствует о безопасности алгоритма. Чтобы убедить скептиков, NIST разрешил комиссии "уважаемых неправительственных экспертов . . . получить доступ к конфиденциальным подробностям алгоритма, чтобы они исследовали его возможности и опубликовали результаты своих исслед о-ваний" [812].

В предварительном отчете этой комиссии экспертов [262] (окончательного отчета не было, и возможно ник о-гда не будет) сообщалось:

Принимая во внимание, что стоимость вычислительных мощностей уменьшается в два раза каждые 18 месяцев, ело ле­ность вскрытия Skipjack сравняется с сегодняшней сложностью вскрытия DES только через 36 лет. Следовательно, риск, что Skipjack будет взломан в ближайшие 30-40 лет, незначителен.

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

Устойчивость Skipjack к криптоанализу не зависит от хранения в тайне самого алгоритма.

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

NSA.

Остался без ответа вопрос, является ли плоским пространство ключей Skipjack (см. раздел 8.2). Даже если у Skipjack нет ключей, слабых в смысле DES, ряд особенностей процесса использования ключа может сделать одни ключи сильнее других. У Skipjack может быть 2⁷⁰ сильных ключей, гораздо больше чем у DES, вероят­ность случайно выбрать один из этих сильных ключей будет приблизительно 1 к 1000. Лично я думаю, что пр о-странство ключей Skipjack - плоское, но то, что об этом никто не заявил публично, вызывает тревогу.

Skipjack запатентован, но в соответствии с соглашением о секретности патента [1122] этот патент хранится в тайне. Патент будет опубликован тогда и только тогда, когда алгоритм Skipjack будет успешно восстановлен кем-то посторонним. Это дает возможность правительству воспользоваться и преимуществом защиты патентом, и преимуществом конфеденциальности торгового секрета.

Глава 14