Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Ya


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

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

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

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

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

 

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

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


Рис. 13-10. PES.

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

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

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

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

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

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

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

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


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

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

C = EK3(DK2(EKi(P)))

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

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

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

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

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

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

Caveat Emptor1

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; [email protected].

13.10 MMB

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

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

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

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


f(x0, хь x2, x3)

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

f(x0, xu x2, x3)

x, = x, © £,+2, для i = О до 3

f(x0, xb x2, x3)

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

f(x0, xb x2, x3)

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

f(x0, xb x2, x3)

x, = x, © £,+2, для i = О до 3

f(x0, xb x2, x3)

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

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

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

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

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

С= 2ааааааа

со = 025flcdb

ci = 2 * со

с2= 23 * со

с3 = 27 * со

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

Дешифрирование является обратным процессом. Этапы (2) и (3) заменяются на свою инверсию. На этапе (1) вместо с,"1 используется с„ с,"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 может быть 270 сильных ключей, гораздо больше чем у DES, вероят­ность случайно выбрать один из этих сильных ключей будет приблизительно 1 к 1000. Лично я думаю, что пр о-странство ключей Skipjack - плоское, но то, что об этом никто не заявил публично, вызывает тревогу.

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


Глава 14




Поделиться с друзьями:


Дата добавления: 2014-11-29; Просмотров: 402; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.