Алгоритм KASUMI

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

В основе алгоритма KASUMI лежит алгоритм MISTY1 (см. разд. 3.36) — один из алгоритмов семейства MISTY, разработанного в 1996-1997 гг. японской корпорацией Mitsubishi Electric [258]. Впоследствии алгоритм MISTY 1 стал одним из победителей европейского конкурса криптоалгоритмов NESSEE. Стоит отметить, что еще одним из победителей конкурса NESSEE стал алгоритм Camellia (см. разд. 3.9), также разработанный компанией Mitsubishi Electric в сотрудничестве с еще одной японской корпорацией NTT (Nippon Telegraph and Telephone).

В декабре 1998 г. был образован консорциум 3GPP (3rd Generation Partnership Project), целью которого являлась разработка стандартов мобильной связи третьего поколения [29]. Одно из направлений стандартизации — разработка протоколов и алгоритмов аутентификации и защиты данных в сетях сотовой связи.

Рабочая группа консорциума 3GPP— SAGE (Security Algorithms Group of Experts, группа экспертов по алгоритмам безопасности) — проанализировала w ряд известных на тот момент алгоритмов шифрования, и в качестве кандидата будущего стандарта шифрования данных в сетях сотовой связи был выбран алгоритм блочного симметричного шифрования MISTY 1, шифрующий 64-битные блоки данных 128-битным ключом. Поскольку к тому времени

были известны некоторые теоретические атаки на MISTY 1, алгоритм был доработан с целью его адаптации для аппаратной реализации (в том числе в условиях ограниченных вычислительных ресурсов), а также усиления против некоторых видов криптоаналитических атак [159, 260, 286], в том числе:

?      атак «встреча посередине»;

?      дифференциального криптоанализа и ряда его вариантов;

?      атак, использующих наличие слабых ключей или классов ключей;

?      линейного криптоанализа.

В результате доработки MISTY 1 был получен алгоритм KASUMI, незначительно отличающийся по своей структуре от MISTY1. Подробная спецификация KASUMI [365] появилась в конце декабря 1999 г. Слово «kasumi» — это перевод на японский английского слова «misty» («туманный») [260].

Следует учесть, что для использования алгоритма KASUMI необходимо получение лицензии у корпорации Mitsubishi Electric [364].

Структура алгоритма

имеет весьма необычную структуру— он основан на «вложенных» сетях Фейстеля [365]. Сначала 64-битный шифруемый блок данных разбивается на два 32-битных субблока, после чего выполняется 8 раундов следующих преобразований (рис. 3.102):

1.    Над обрабатываемым субблоком производятся зависящие от ключа операции FL и FO (в указанной последовательности — в нечетных раундах, в четных — наоборот).

2.    Результат этих операций накладывается побитовой логической операцией XOR на необработанный субблок.

3.     Субблоки меняются местами.

Операция FL является достаточно простой. Обрабатываемый ей субблок разбивается на два 16-битных фрагмента, над которыми выполняются следующие действия (рис. 3.103):

Рис. 3.107. Алгоритм J9

2.     Результаты зашифровывания блоков последовательности накладываются операциями XOR друг на друга.

3.    Результат предыдущей операции зашифровывается алгоритмом KASUMI на ключе, являющемся результатом применения операции XOR к ключу К2 и константе С2, используемой для модификации ключа. MAC — левые 32 бита полученного 64-битного результата зашифровывания.

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

Считается, что криптоанализ алгоритма MISTY 1 применим и к KASUMI (см., например, [184]). Есть как примеры атак, применимых к обоим алгоритмам (например, [230]), так и атак, применимых к MISTY, но неприменимых к KASUMI (например, [231]), и наоборот (например, [98]). Стоит сказать, что весьма мало различающиеся между собой алгоритмы IDEA и PES (см. разд. 3.26) имеют принципиально различные уровни криптостойкости. Поэтому рассмотрим здесь только те криптоаналитические результаты, которые имеют отношение именно к KASUMI.

Еще в процессе разработки алгоритм KASUMI был подвергнут первичному анализу командой разработчиков [159]. А после того, как спецификация алгоритма была определена, KASUMI был предоставлен для исследования трем независимым группам специалистов-криптологов. Причем криптоанализ проводился именно с учетом специфики использования алгоритма KASUMI — в качестве блочного шифра, на котором построены функции потокового шифрования /8 и аутентификации J9. В результате анализа все группы специалистов сделали вывод о том, что, во-первых, не обнаружено каких-либо атак на алгоритм KASUMI, осуществимых на практике; во-вторых, алгоритм полностью соответствует его предполагаемым применениям. Однако, считая недостаточным время, отведенное на данные исследования, рабочей группой консорциума 3GPP было принято решение о повторном исследовании алгоритма и пересмотре данных выводов каждые 5 лет [159J.

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

?      Исследователи из Великобритании Марк Бланден (Mark Blunden) и Эдриан

Эскотт (Adrian Escott) предложили атаку на связанных ключах на 5-

раундовую версию KASUMI. Для успешного осуществления данной атаки

10

требуется наличие примерно 2 выбранных открытых текстов и около 2 ~ тестовых операций шифрования. Данная атака стала возможной благодаря тому, что процедура расширения ключа алгоритма KASUMI существенно упрощена по сравнению с MISTY 1 с целью упростить аппаратную реализацию алгоритма и ускорить процесс развертки ключа шифрования. Алгоритм MISTY 1 с оригинальной процедурой расширения ключа подобной атаке не подвержен. Аналогичная атака возможна и на 6-раундовую версию KASUMI; для нее необходимо наличие такого же количества выбранных

1 1 л

открытых текстов и около 2 попыток шифрования [98].

?      Группа японских специалистов: Хидема Танака (Hidema Tanaka), Нобую- ки Сугио (Nobuyuki Sugio) и Тошинобу Канеко (Toshinobu Kaneko), — успешно атаковала методом дифференциального криптоанализа 5-раундовую версию алгоритма, которая вскрывается при наличии 222 выбранных открытых текстов выполнением 263 операций шифрования [371].

?     Несколько раньше Танака, Канеко и Чикаши Ишии (Chikashi Ishii) исследовали 4-раундовую модификацию алгоритма KASUMI, в которой отсутствовали функции FL. Не удивительно, что такой вариант оказался еще

‘более слабым и для его вскрытия требуется всего 1416 выбранных открытых текстов и 222 тестовых операций шифрования [371].

?     Ульрих Кюн (Ulrich Kuhn) из исследовательского подразделения Дрезденского банка предложил атаку на 6-раундовую версию алгоритма KASUMI с использованием невозможных дифференциалов; для атаки необходимо наличие 255 выбранных открытых текстов и выполнение 2100 операций шифрования [230].

Стоит отметить, что и эти атаки на усеченные версии алгоритма (за исключением атаки на алгоритм без функции FL) достаточно сложно осуществимы на практике.

Из всего вышесказанного можно было бы сделать однозначный вывод об отсутствии серьезных недостатков у алгоритма KASUMI и( что данный алгоритм будет достаточно широко применяться уже в ближайшем будущем. Однако в последнее время были обнаружены новые методы атак на алгоритм KASUMI, существенно более эффективные, чем предыдущие; кроме того, возникли сомнения в эффективности самого алгоритма KASUMI.

?     В 2005 г. Эли Бихам, Орр Данкельман (Orr Dunkelman) и Натан Келлер атаковали полнораундовую версию алгоритма KASUMI методом дифференциального криптоанализа на связанных ключах. Для успешной атаки требуется 254,6 выбранных открытых текстов и 276,1 операций за- шифровывания (есть и вариант атаки с адаптивным выбором открытых текстов и шифртекстов, которой требуется меньше данных, но более сложная их обработка; оба варианта атаки являются теоретическими и маловероятно реализуемыми на практике). Кроме того, вышеперечисленные криптоаналитики существенно усилили упомянутую ранее атаку

1 ^

Кюна на 6-раундовую версию: новая атака требует наличия всего 2 открытых текстов и шифртекстов с адаптивным выбором и 213 операций шифрования [66].

?     В конце 2005 г. специалист из Малайзии Йи Вей Jloy (Yee Wei Law) доказал, что далеко не на всех аппаратных платформах алгоритм KASUMI более эффективен, чем MISTY 1. В частности, процедура расширения ключа KASUMI, несмотря на то, что она более проста, чем у MISTY 1, выполняется почти в 2 раза дольше, чем в MISTY 1 [236].                                                                                                                                   ,

?     А совсем недавно, в начале 2006 г., Эли Бихам, Натан Келлер и Элад Баркан (Elad Barkan) опубликовали работу, в которой рассмотрены практически реализуемые атаки на протоколы защиты в сотовых сетях второго поколения (GSM), в том числе на протокол, использующий в своей основе алгоритм KASUMI (еще не введенный в действие, но планируемый в ближайшее время) [42].

все еще считается достаточно сильным. Однако исследования продолжаются.

Вы можете следить за любыми ответами на эту запись через 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