Алгоритм Camellia

разработан компанией Mitsubishi Electric совместно с компанией Nippon Telegraph and Telephone Corporation (NTT). В его разработке приняли участие некоторые из специалистов, ранее разработавших еще один алгоритм — победитель конкурса NESSEE— MISTY1 {см. разд. 3.36): Мицуру Мацуи, Тецуя Ичикава, Тошио Токита, — а также Казумаро Аоки (Kazumaro Aoki), Масаюки Канда (Masayuki Kanda), Шихо Мориаи (Shiho Moriai) и Джунко Накаджима (Junko Nakajima).

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

Camellia шифрует данные 128-битными блоками с использованием 128-, 192- или 256-битных ключей шифрования. В зависимости от размера ключа в алгоритме предусмотрено различное количество раундов R [38]:

?       18 — для 128-битного ключа;

?      24 — для остальных размеров ключа.

Перед первым раундом выполняется входное отбеливание данных— на шифруемый блок операцией XOR накладывается 128-битный фрагмент расширенного ключа kwi. Затем 128-битный блок данных делится на два субблока по 64 бита, после чего субблоки «прогоняются» через раунды шифрования. Между каждыми шестью раундами левый субблок обрабатывается операцией FL, а правый — операцией FLI (эти операции подробно описаны далее).

По завершении последнего раунда субблоки меняются местами. Затем выполняется выходное отбеливание данных; здесь используется еще один 128- битный фрагмент расширенного ключа — кт).

Структура алгоритма на примере варианта для 128-битного ключа приведена на рис. 3.29.

В каждом раунде левый субблок обрабатывается функцией F, которая использует 64-битный фрагмент ключа kt (/ — номер раунда), и накладывается на правый субблок операцией XOR.

о

?      вычисления выполняются в конечном поле GF(2 ), обратным значением от 0 является 0, (3— элемент конечного поля GF(28), удовлетворяющий условию:

?                   

Функция h выполняет следующие преобразования:

Расшифровывание

Расшифровывание данных алгоритмом Camellia выполняется полностью аналогично зашифровыванию, но с использованием фрагментов расширенного ключа в обратной последовательности, т. е.:

?      подключ кт) используется при входном отбеливании, и наоборот, под- ключ kwi используется при выходном отбеливании данных;

?      в раундах шифрования ключи kt применяются в обратном порядке: от кг до кх;

?      в операциях FL и FLI четные фрагменты расширенного ключа используются при обработке левого субблока, нечетные — правого; и те, и другие берутся в обратной последовательности относительно зашифровывания.

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

Задача расширения ключа состоит в формировании необходимого количества фрагментов расширенного ключа (для перечисленных выше операций) из 128-, 192- или 256-битного исходного ключа шифрования К. Данная процедура состоит из нескольких этапов.

Прежде всего выполняется инициализация переменных KL и KR таким образом:

?      для 128-битного ключа KL~ К, KR =0;

?      192-битный ключ делится на 3 фрагмента по 64 бита, первые два из которых формируют KL; третий фрагмент и его побитовый комплемент формируют KR;

?      256-битный ключ делится на 2 части: KL и КR .

На следующем этапе вычисляются еще две ключевые переменные: КА и Кв . Это выполняется с использованием описанной выше функции Этаким образом (рис. 3.33):

1.     Результат операции KL@KR дважды обрабатывается функцией F (см. рис. 3.33), в качестве фрагментов ключа которой берутся константы С1 и С2 (описаны далее).

2.     На результат предыдущей операции операцией XOR накладывается KL.

3.      Снова дважды применяется функция F с использованием констант СЗ и С4 в качестве фрагментов ключа. В результате получается переменная КА.

4.      В случае, если используются 192- или 256-битные ключи, необходимо также вычислить переменную Кв. Для этого на КА операцией XOR накладывается KR , результат дважды обрабатывается функцией F с использованием констант С5 и Сб.

Константы С1…С6 приведены в табл. 3.10 (указаны шестнадцатеричные значения).

Таблица ЗЛО

С1

A09E667F3BCC908B

С2

В67АЕ8584САА73В2

СЗ

C6EF372FE94F82BE

С4

54FF53A5F1D36F1C

С5

10E527FADE682D1D

С6

B05688C2B3E6C1FD

В процессе шифрования переменные KL, KR, КА и Кв используются в качестве фрагментов расширенного ключа согласно приведенным далее таблицам (в порядке использования фрагментов).

Для 128-битного ключа— см. табл. 3.11, для остальных размеров ключей — табл. 3.12.

Таблица 3.11

 

KL

и k2

Левая и правая половины КА

k3 и к4

Левая и правая половины «< 15)

Таблица 3.11 (окончание)

^wi

KL

k5 и k6

Левая и правая половины (КА «< 15)

kx и

Левая и правая половины (К А «< 30)

k-j и

Левая и правая половины ( КL <« 45)

к9

Левая половина (КА <«45)

^10

Правая половина (КL «< 60)

ки и к]2

Левая и правая половины (КА «< 60)

кз,х и

Левая и правая половины (KL <« 77)

к]3 и *14

Левая и правая половины (KL «< 94)

к]5 и к

Левая и правая половины (КА «< 94)

кХ1 и ?18

Левая и правая половины (KL «< 111)

к

14VVO

КА«<Ш

Таблица 3.12

kwi

Kl

и к2

Левая и правая половины Кв

к3 и *4

Левая и правая половины (К R «< 15)

и

Левая и правая половиныА «< 15)

и *2,jc

Левая и правая половины (КR «< 30)

и &8

Левая и правая половиныв «< 30)

к9 и

Левая и правая половины ( КL «< 45)

и кп

Левая и правая половиныА «< 45)

и JC

Левая и правая половины (KL «< 60)

Таблица 3.12 (окончание)

 

KL

kl3 и кы

Левая и правая половины (KR «< 60)

к]5 и кх6

Левая и правая половины (Кв «< 60)

кХ1 и *18

Левая и правая половиныL «< 11)

и

Левая и правая половины (КА <« 11)

^19 и ^20

Левая и правая половины (KR «< 94)

&21 И &22

Левая и правая половины (КА «< 94)

^23 и ^24

Левая и правая половины (КL «< 111)

Ь

лWO

Кв «<111

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

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

Первые отзывы известных экспертов об алгоритме Camellia также были крайне положительными. В частности, в работах [208] и [404] отмечена исключительно высокая криптостойкость Camellia. JIapc Кнудсен в [208] утверждает следующее:

?      любые практически осуществимые атаки на Camellia будут возможны только после принципиальных прорывов в области криптоанализа;

?      Camellia— один из наиболее стойких современных алгоритмов шифрования.

В оценке ресурсоемкости и быстродействия алгоритма Camellia эксперты были далеко не так единодушны:

?      в [88] отмечается, что Camellia существенно проигрывает в скорости алгоритму Rijndael;

?      в [236] показано, что Camellia предъявляет достаточно высокие требования к оперативной и энергонезависимой памяти;

?     и наоборот, авторы отчета CRYPTREC (Camellia— один из рекомендованных экспертами алгоритмов для защиты в рамках проекта CRYPTREC, который посвящен созданию электронного правительства Японии) отметили высокую скорость шифрования (особенно на серверных платформах), быструю процедуру расширения ключа и достаточно невысокие требования к энергонезависимой памяти [127].

Весьма много исследований было посвящено ослабленному варианту алгоритма Camellia— с уменьшенным количеством раундов, а также без входного/ выходного отбеливания и операций FLJFLL Стоит упомянуть следующие работы:

?     в [65], в частности, описана атака на 9-раундовый вариант Camellia, который вскрывается при наличии 2105 выбранных открытых текстов выполнением 264 операций шифрования; там же отмечается, что линейный криптоанализ неприменим для вскрытия алгоритма;

П авторами [368] найден 9-раундовый усеченный дифференциал, с помощью которого возможна атака на 11-раундовую версию Camellia;

П в работе [397] предложена атака методом поиска коллизий на 9-раундовую версию Camellia, для которой требуется 2113,6 выбранных открытых текстов и 2121 операций шифрования (128-битный ключ) или 213 выбранных открытых текстов и 2175,6 операций (192-битный ключ); там же предложена атака на 10-раундовую версию с 256-битным ключом, для которой необходимо 214 выбранных открытых текстов и 2239,9 операций;

?     в совсем недавней работе [399] применен метод невозможных дифференциалов, найден 8-раундовый невозможный дифференциал, с помощью которого атакована 12-раундовая версия; для атаки требуется 2120 выбранных открытых текстов и 2181 операций.

Работы, анализирующие варианты, более близкие к исходной версии Camellia, встречаются существенно реже. Этим примечательна, например, работа [403], в которой применена Square-атака, вскрывающая 9-раундовый алгоритм Camellia (включая операции FL/FLI после шестого раунда, но без входного и выходного отбеливания) при наличии 260,5 выбранных открытых текстов выполнением 22022 операций шифрования.

был исследован и с точки зрения атак, использующих утечку информации по побочным каналам. В этой связи широко известны, в частности, следующие работы:

?     авторы работы [294] утверждают, что Camellia — один из лучших алгоритмов, представленных во втором раунде конкурса NESSIE, с точки зрения защищенности от атак по потребляемой мощности;

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

Camellia— один из алгоритмов — победителей конкурса NESSIE [305] (см. разд. 2.2). В рамках исследований, проведенных во время конкурса NESSIE, не было выявлено каких-либо проблем с криптостойкостью данного алгоритма [307]. В настоящее время также не найдено каких-либо серьезных уязвимостей в алгоритме Camellia, однако видно, что активный анализ этого алгоритма будет продолжаться.

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