Алгоритм MISTY2

В отличие от MISTY 1, алгоритм MISTY2 не участвовал в конкурсе NESSEE (см. разд. 2.2) и не снискал такой широкой известности. MISTY2 незначительно отличается от MISTY 1: он использует те же функции, но в несколько другой последовательности.

Структура MISTY2 приведена на рис. 3.142. В данном алгоритме существует не 2, а 4 различных типа раундов, которые выполняются поочередно, после чего повторяются требуемое количество раз [255, 257].

Структура раунда 1 (после приведенных далее операций в каждом раунде субблоки меняются местами):

1.    Оба субблока обрабатываются операцией FL.

2.     Левый субблок обрабатывается операцией FO.

3.     Значение правого субблока обрабатывается операцией FL и накладывается на левый субблок операцией XOR.

Структура раунда 2:

1.    Левый субблок обрабатывается операцией FO.

2.     Значение правого субблока накладывается на левый. Структура раунда 3:

1.    Левый субблок обрабатывается операцией FO.

2.     Значение правого субблока обрабатывается операцией FL и накладывается на левый.

Структура раунда 4 аналогична раунду 2.

Процедура расширения ключа, а также структура операций FO и FL аналогичны описанным выше для алгоритма MISTY 1. Рекомендуемым количеством раундов для MISTY2 является 12, а не 8.

является более быстродействующим, чем MISTY 1 при возможности параллельной обработки данных, поскольку может выполнять по 2 раунда параллельно [257, 310].

Рис. 3.142. Структура алгоритма MISTY2

Алгоритм KASUMI

Алгоритм KASUMI несколько больше отличается от MISTY 1, чем MISTY2. Основные отличия таковы [138]:

? операция FL обрабатывает только один субблок, но в каждом раунде;

?     в данной операции присутствует дополнительное действие — вращение одного из обрабатываемых фрагментов на 1 бит;

?     в операции FO используется 3 фрагмента ключа, а не 4;

?     в операции FI используется 4 «прогона» данных через таблицы замен, а не 3, причем таблицы замен также изменены;

?     принципиально изменена процедура расширения ключа.

Алгоритм KASUMI является стандартом шифрования данных в сетях сотовой связи третьего поколения. Существует мнение, что алгоритм KASUMI менее стоек, чем MISTY 1, поскольку существуют атаки на его полнораундо- вую версию. По данным, приведенным в [236], KASUMI проигрывает MISTY 1 по всем основным параметрам. В частности, несмотря на существенно более простую процедуру расширения ключа, расширение ключа в KASUMI выполняется в 2 раза медленнее, чем в MISTY 1. Хотя считается, что изменения, внесенные в MISTY 1 с целью получения алгоритма KASUMI, должны были, наоборот, усилить алгоритм [83].

Подробное описание KASUMI и результатов его криптоанализа можно найти в разд. 3.27.

Помимо алгоритмов MISTY2 и KASUMI, часть преобразований алгоритма MISTY1 используется и в алгоритме Camellia, который подробно описан в разд. 3.9.

Криптоанализ алгоритмов MISTY1 и MISTY2

Алгоритм MISTY 1 вызвал огромный интерес у криптологов как благодаря своему участию в конкурсе NESSIE, так и из-за своего родства с не менее известным алгоритмом KASUMI.

Первичный криптоанализ алгоритма выполнен его разработчиками, его результаты опубликованы в [259]. Авторы алгоритма доказывают криптостой- кость алгоритма к линейному и дифференциальному криптоанализу, а также утверждают, что MISTY 1 устойчив к сдвиговым атакам, использованию невозможных дифференциалов и ряду других атак.

В 2001 г. невозможные дифференциалы для атаки на варианты MISTY с уменьшенным количеством раундов применил Ульрих Кюн: 4-раундовый MISTY 1 вскрывается при наличии 238 выбранных открытых текстов с помощью 262 тестовых операций шифрования; для атаки на 5-.раундовый MISTY2 требуется 228 выбранных открытых текстов и 276 операций [230]. Он же в 2002 г. предложил принципиально новую атаку (названную «slicing attack»), действующую против MISTY 1, которой для вскрытия 4-раундового

MISTY 1 требуется существенно меньше ресурсов: 2 ‘ выбранных открытых текстов и 245 операций шифрования [231].

В том же 2001 г. известные криптоаналитики Jlapc Кнудсен и Дэвид Вагнер предложили атаку на MISTY1 и MISTY2 методом интегрального криптоанализа. Данная атака позволяет вскрыть 5-раундовый MISTY 1 при наличии 234 выбранных открытых текстов выполнением 248 операций шифрования или 6-раундовый MISTY2 при наличии 234 выбранных открытых текстов выполнением 271 операций [226]. Эти результаты являются лучшими из опубликованных для алгоритмов MISTY на текущий момент.

Проводились исследования и модифицированных вариантов алгоритма. В частности, в [370] исследован вариант без функций FL. Вскрывается 6 раундов алгоритма MISTY 1 без FL-функций при наличии 212 выбранных открытых текстов выполнением 297 операций.

В результате анализа алгоритма MISTY 1, проведенного в рамках конкурса NESSIE и до него, эксперты сделали вывод, что никаких серьезных уязвимостей данный алгоритм не имеет (они особо отметили, что именно структура алгоритма с вложенными сетями Фейстеля существенно затрудняет криптоанализ [307]). На этот вывод повлияли и результаты исследований алгоритма KASUMI, который, как было сказано выше, использует те же преобразования, что и MISTY 1. В результате MISTY 1 был выбран победителем конкурса NESSIE среди 64-битных алгоритмов блочного симметричного шифрования [305].

Аналогичные исследования были проведены и в рамках проекта CRYPTREC по выбору криптоалгоритмов для электронного правительства Японии. Экс- перты проекта весьма положительно оценили алгоритм MISTY1, сделав вывод, что у него высокий запас криптостойкости, алгоритм имеет высокую скорость шифрования и весьма эффективен для аппаратной реализации [126].

Анализ алгоритмов семейства MISTY активно продолжается и в настоящее время. В качестве примера можно привести совсем недавнюю работу [238], в которой выполняется проверка стойкости преобразования FO против дифференциального криптоанализа. Стоит сказать и о том, что некоторые эксперты (например, в [310]) предрекают, что в ближайшем будущем будут появляться новые алгоритмы с MISTY-подобной структурой, поскольку данная структура весьма успешно зарекомендовала себя с точки зрения криптостойкости и быстродействия.

3.37. Алгоритм Nimbus Структура алгоритма

Алгоритм шифрования Nimbus разработан Алексисом Уорнером Мачадо (Alexis Warner Machado) из компании Gauss Informatica, Бразилия. Алгоритм исключительно прост в описании, структуру его раунда можно, фактически, представить одной формулой (рис. 3.143) [247]:

где:

?     х и у — соответственно, входное и выходное значения текущего (/-го) раунда преобразований, / = 0…4;

?       к0…к9 — фрагменты расширенного ключа (см. далее);

?     функция g() представляет собой битовую перестановку, она просто меняет местами биты №№ п и 63 – п для n = 0…31.

Рис. 3.143. Раунд алгоритма Nimbus

Расшифровывание выглядит не сложнее — так же, как и при зашифровыва- нии, выполняется 5 раундов преобразований:

где:

?     х и у— соответственно, выходное и входное значения /-го раунда расшифровывания;

?       к’п — мультипликативная обратная величина к кп по модулю 264.

Стоит сказать, что автор алгоритма не ограничивает размер блока 64 битами: можно шифровать блоками по 128 и 256 битов и более. При этом используются вычисления по модулю 2128 , 2256 и т. д. Поскольку с увеличением размера блока сложность подобных вычислений нелинейно возрастает, дальнейшее увеличение размера блока не выглядит оправданным.

Процедура расширения ключа

Алгоритм Nimbus использует ключи шифрования переменного размера, от 64 до 576 битов; размер ключа шифрования должен быть кратен 64 битам. Исходный ключ представляется в виде последовательности 64-битных блоков К0…Кт. На их основе генерируется последовательность подключей k0…k9:

1.    Выполняется инициализация подключей, состоящая в обнулении последовательности k0…k9.

2.     В цикле по i от 0 до т (т — размер ключа в 64-битных блоках) выполняются следующие действия.

• Вычисляется промежуточное значение х:

где Е() представляет собой зашифровывание входного значения алгоритмом Nimbus на наборе фиксированных подключей, который выглядит согласно табл. 3.83.

Таблица 3.83

kQ

243F6A8885A308D3

 

13198 А2Е03707345

 

A4093822299F31D1

 

082EFA98EC4E6C89

 

45282IE638D01377

 

BE5466CF34E90C6C

 

C0AC29B7C97C50DD

 

3F84D5B5B5470917

 

9216D5D98979FB

 

D131 OB A698DFB5 АС

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

• В цикле по j от 0 до 9 выполняются следующие операции:

3. Обеспечивается нечетность значений подключей k0…k4, которые используются в операциях умножения при шифровании — путем установки младших битов k0…k4 в единичное значение.

Стоит обратить внимание на следующие свойства алгоритма и процедуры расширения ключа:

?     при необходимости достаточно легко можно увеличить количество раундов алгоритма (в абсолютном большинстве алгоритмов это приводит к увеличению криптостойкости за счет снижения скорости шифрования); для этого достаточно лишь увеличить количество подключей (и соответствующие циклы в описанных выше шагах 1-3 процедуры расширения ключа) и, собственно, количество раундов алгоритма;

?     расширение ключа никоим образом невозможно выполнять «на лету», что можно считать недостатком алгоритма.

Достоинства и недостатки алгоритма

В спецификации алгоритма [247] его автор утверждал, что Nimbus обладает стойкостью против всех известных атак, в случае, если количество раундов алгоритма превышает 4 (а в спецификации установлено 5 раундов алгоритма). Однако алгоритм не был выбран во второй раунд конкурса NESSIE из-за найденной специалистами атаки, которую весьма реально осуществить на практике [307].

Данная атака была изобретена известными криптологами из института Technion, Израиль: Эли Бихамом и Владимиром Фурманом (Vladimir Furman) [71]. Атака позволяет вычислить ключ шифрования полнораундового алгоритма Nimbus на основе всего 256 выбранных открытых текстов и соответствующих им шифртекстов путем выполнения не более 210 тестовых операций шифрования. При наличии у злоумышленника возможности выбора шифртекстов для атаки требуется еще меньше материала — достаточно 136 выбранных шифртекстов (и соответствующих им открытых текстов) при той же вычислительной сложности. Впоследствии специалистам из Университета Беркли (США) удалось распространить принципы атаки, предложенной Бихамом и Фурманом, на ряд других алгоритмов шифрования [101].

Таким образом, алгоритм Nimbus оказался наиболее слабым из всех алгоритмов блочного шифрования, участвовавших в конкурсе NESSIE.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100