Akelarre — блочный шифр , разработанный коллективом испанских авторов и представленный на в 1996 году; объединяет основную разработку IDEA с концепциями от RC5 . Название akelarre также используется в баскском языке для обозначения собрания ведьм .

Описание

Akelarre является 128-битным блочным шифром. При этом длина ключа переменная, должна быть кратной 64 битам; число проходов шифрования так же является изменяемым параметром. Оптимальные значения, предложенные авторами — 128-битный ключ и 4 раунда . Функция шифрования в Akelarre структурно похожа на представленную в IDEA. Однако между этими шифрами в целом есть ряд существенных отличий: так, в IDEA используется 16-битный размер слова, а не 32-битный, также различается набор используемых примитивных операций. В Akelarre применяются :

• сложение по модулю ${\displaystyle 2^{m}}$ ;
• побитовое исключающее ИЛИ ( XOR );
• операции циклического сдвига влево на переменное число бит ( ${\displaystyle x\lll y}$ ).

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

Алгоритм работы

Структурно алгоритм может быть разделен на две подчасти:

1. Алгоритм шифрования/дешифрования.
2. Алгоритм расширения ключа, вводимого пользователем.

Шифрование

Сперва открытый текст X разбивается на 128-битные блоки, каждый из которых в свою очередь разбивается на 4 субблока X ₁ …X ₄ , к которым уже применяется первичное преобразование. Вся процедура шифрования происходит в три этапа.

• Входное преобразование состоит в сложении по модулю ${\displaystyle 2^{32}}$ фрагментов расширенного ключа K _i1 , K _i4 соответственно с субблоками X ₁ , X ₄ и применении побитового исключающего ИЛИ (XOR) к фрагментам расширенного ключа K _i2 , K _i3 и субблокам X ₂ , X ₃ соответственно. Эти преобразования необходимы для предотвращения последствий возможного попадания на вход последовательности из всех нулей или всех единиц, а также для затруднения проведения атаки на шифр методом дифференциального криптоанализа (см. ).
• Раунды шифрования:

1. В начале работы каждого из ${\displaystyle r}$ раундов происходит циклический сдвиг 128-битного блока, получающегося в результате объединения субблоков, образованных в результате входного преобразования или предыдущего раунда; на ${\displaystyle m}$ -ом раунде ( ${\displaystyle m=1,2,\ldots ,r}$ ) переменное число битов, задающих сдвиг, определяется младшими битами фрагмента ключа K _m1 , формируемого в результате процедуры расширения ключа.
2. На следующем этапе 128-битный блок снова разбивается на 4 субблока по 32 бита, и вычисляются побитовые ИЛИ для пары из первых двух, а затем и для пары последних двух блоков. Дальнейшие преобразования полученных в результате блоков С ₁ , С ₂ определяются работой AR-модуля (addition-rotation structure). Структура модуля представляет собой два столбца: С ₁ подается на вход первого, С ₂ — второго. Для С ₁ :
   • Первый 31 бит С ₁ циклически сдвигается влево (величина сдвига определяется 5 младшими битами С ₂ ).
   • Полученный на предыдущем шаге результат складывается по модулю числа ${\displaystyle 2^{32}}$ с одним из фрагментов расширенного ключа K _m8 .
   • Последний 31 бит выходного блока предыдущего шага циклически сдвигается влево аналогично шагу 1.
   • Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа ${\displaystyle 2^{32}}$ с субключом K _m9 аналогично шагу 2.
   • Старший 31 бит выходного блока предыдущего шага циклически сдвигается влево как в шаге 1.
   • Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа ${\displaystyle 2^{32}}$ с субключом K _m10 как в шаге 2.
   • Шаги с 3 по 6 повторяются до тех пор, пока не будет осуществлено в общей сложности 7 сдвигов и 6 суммирований с субключами.

Аналогично обрабатывается С ₀₂ , только с использованием ключей K _m2 …K _m7 .

Из полученных в результате работы модуля блоков D ₁ , D ₂ путем сложения с блоками, образованными разбиением 128-битного блока в начале раунда, формируются 4 выходных значения раунда (каждый из X ₁ , X ₃ суммируется с D ₁ , а каждый из X ₂ , X ₄ — с D ₂ ). Применение побитового сдвига не ко всему блоку, а только к 31 биту сделано, чтобы избежать возможной идентичности выходного и входного результатов, которая может наблюдаться при использовании составных чисел .

• Во время финального преобразования осуществляется циклический сдвиг образованного конкатенацией полученных после конечного раунда подблока 128-битного блока влево на количество битов, определяемое 7 последними битами подключа K _f1 , после чего получившийся блок разбивается на 32-битные подблока, к которым применяются операции, аналогичные операциям входного преобразования, но уже с ключами K _f2 …K _f5 .

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

Алгоритм расшифрования в сущности организован тем же образом, что и используемый для шифрования, только подключи генерируются уже на основе ключей шифрования. Соответствие между ключами для шифрования и для расшифрования имеет следующий вид (здесь начальное преобразование понимается как нулевой раунд, а финальное преобразование — как (r+1)-й раунд) :

Раунд	Ключи, используемые при шифровании	Ключи, используемые при дешифровании
Начальное преобразование	${\displaystyle K_{01},K_{02},K_{03},K_{04}}$	${\displaystyle -K_{(r+1)2},K_{(r+1)3},K_{(r+1)4},-K_{(r+1)5}}$
1-й раунд	${\displaystyle K_{11},K_{12},K_{13}...K_{1(13)}}$	${\displaystyle (K_{(r+1)1})^{-1},K_{r2},K_{r3}...K_{r13}}$
2-й раунд	${\displaystyle K_{21},K_{22},K_{23}...K_{2(13)}}$	${\displaystyle (K_{r1})^{-1},K_{(r-1)2},K_{(r-1)3}...K_{(r-1)13}}$
m-й раунд	${\displaystyle K_{m1},K_{m2},K_{m3}...K_{m13}}$	${\displaystyle (K_{(r+2-m)1})^{-1},K_{(r+1-m)2},K_{(r+1-m)3}...K_{(r+1-m)13}}$
r-й раунд	${\displaystyle K_{r1},K_{r2},K_{r3}...K_{r13}}$	${\displaystyle (K_{21})^{-1},K_{12},K_{13}...K_{1(13)}}$
Финальное преобразование	${\displaystyle K_{(r+1)1},K_{(r+1)2},K_{(r+1)3},K_{(r+1)4}}$	${\displaystyle (K_{11})^{-1},-K_{01},K_{02},K_{03},-K_{04}}$

Расширение ключа

Для возможности работы алгоритма требуется ключ, состоящий по меньшей мере из хотя бы 22 субблоков по 32 бита (704 бита) . Дальнейшее описание соответствует применению алгоритма к 128-битному ключу:

1. Пользовательский ключ разбивается на 8 частей по 16 битов k ₁ …k ₈ .
2. Каждый отдельный фрагмент возводится в квадрат с получением 32-битного значения, и происходит суммирование по модулю числа ${\displaystyle 2^{32}}$ получившихся значений отдельно с каждой из констант a ₁ , a ₂ ; в результате на основе каждого из исходных ключей k _i1 образуется по два временных значения K _ti и K' _ti . Константы должны быть подобраны из соображений избежать возможного образования ключа, состоящего из одних нулей. Авторами предложены a ₁ =A49ED284H и a ₂ =73503DEH .
3. Из полученных на предыдущем шаге временных значений формируются фрагменты предварительного расширенного ключа K _e1 …K _e8 . Каждый из этих фрагментов является результатом конкатенации 8 младших и 8 старших битов K' _ti , а также 8 младших и 8 старших битов K _ti ; 16 же битов, располагающиеся в середине каждого из временных значений, обрабатываются уже схожим с обработкой k ₁ …k ₈ образом для получения новых значений фрагментов расширенного ключа .
4. Ключи, используемые в начальном преобразовании ( K _i1 …K _i4 ), работе AR-модуля ( K _m1 …K _m13 для каждого из m раундов) и финальном преобразовании ( K _f1 …K _f5 ) заполняются поочередно формируемыми в ходе работы алгоритма значениями K _e1 …K _e8 .

Устойчивость

Уже спустя год после того, как шифр был представлен, в работе Нильса Фергюсона и Брюса Шнайера была осуществлена атака, позволяющая осуществить взлом на основе выборки из не более, чем 100 открытых текстов. Атака происходит в 4 этапа: в первых двух происходит восстановление начального и финального преобразований битов субключей, а следующие два используют уязвимости схемы расширения ключа, причем с увеличением числа раундов в алгоритме резко увеличивается и количество информации, которое может быть получено о работе схемы. Сложность организации AR-модуля в силу его свойств (свойства четности) нисколько не затрудняет взлом . В той же работе приводится и ещё одна атака, в которой дополнительно использование дифференциальной характеристики алгоритма позволяет сократить число необходимых операций в итоге до ${\displaystyle 2^{32}}$ .

Ещё одна работа, в которой с успехом был осуществлен криптоанализ Akelarre, принадлежит Ларсу Кнудсену и Винсенту Риджмену. Они описывают две возможные атаки: одна основана на использовании открытого текста , другая позволяет раскрыть ключ используя только зашифрованный текст и некоторую информацию об открытом тексте — в частности, достаточно знать, что это текст на английском языке в ASCII-кодировке . Так же, как и атаки, предложенные в работе Фергюсона и Шнайера, атаки, предложенные в этой работе, не зависят от числа раундов алгоритма или размера ключа, а атака, использующая только шифротекст , относится к числу наиболее практически применимых, так как уже одного прослушивания канала достаточно для её проведения .

Значение

Задуманный как алгоритм, успешно сочетающий в себе элементы двух надежных и широко известных алгоритмов IDEA и RC5 и обладающий сложной архитектурой, Akelarre не продемонстрировал высокой криптостойкости, чем наглядно показал, что не всегда объединение компонентов двух хорошо защищенных алгоритмов дает в итоге надежный новый . Как сказано в названии одной из исследовавших алгоритм работ :

Два плюса иногда дают минус.

Оригинальный текст (англ.)

Two rights sometimes make a wrong.

Модификации

После успешного криптоанализа Akelarre его проектировщики представили обновлённый вариант, названный Ake98 . Этот шифр отличается от оригинального Akelarre новой AR-box (Addition-Rotation box), перестановкой слов, осуществляемой в конце прохода шифрования, а также добавлением подключей в начале каждого прохода шифрования. При этом такие параметры, как размер ключа и размер блока, остались, как и прежде, регулируемыми, но их минимальный размер создателями не определён . AR-модуль работает в новой версии как генератор псевдослучайных чисел .

В 2004 году Хорхе Накаара младший и Даниэль Сантана де Фреита нашли большие классы слабых ключей для Ake98. Эти слабые ключи позволяют анализировать быстрее, чем полным перебором , используя только 71 известный фрагмент текста для 11,5 проходов шифрования в Ake98. Кроме того, в этой же работе была осуществлена оценка производительности алгоритма, которая показала, что хотя и для числа раундов 25,5 или большего алгоритм не имеет слабых ключей, он оказывается в 4 раза медленнее IDEA , в 8 раз медленнее AES , и в 14 раз — RC6 .

Примечания

Литература

• Álvarez M. G., Fúster S. A., Guía M. D., Montoya V. F., Peinado D. A. Akelarre: a New Block Cipher Algorithm // SAC’96, Third Annual Workshop on Selected Areas in Cryptography - Queen’s University, Kingston, Ontario, 1996, Proceedings. — 1996. — С. 1—14 .
• Глава 3 // — СПб. : , 2009. — С. 97—103. — 576 с. — ISBN 978-5-9775-0319-8
• Ferguson N., Schneier B. Cryptanalysis of Akelarre // SAC’97: Fourth Annual Workshop on Selected Areas in Cryptography, Carleton University, Ottawa, 1997, Proceedings. — 1997. — С. 201—212 .
• Knudsen L. R., Rijmen V. Two Rights Sometimes Make a Wrong // SAC’97: Fourth Annual Workshop on Selected Areas in Cryptography, Carleton University, Ottawa, 1997, Proceedings. — 1997. — С. 213—223 .
• , (англ.) // : 5th International Conference on Cryptology in India, Chennai, India, December 20-22, 2004. Proceedings / , — Berlin, Heidelberg, New York City, London: , 2005. — P. 206—217. — 431 p. — ( ; Vol. 3348) — ISBN 978-3-540-24130-0 — ISSN ; —
• Stamp M., Low M. R. Applied cryptanalysis: breaking ciphers in the real world. — John Wiley & Sons, Inc., Hoboken, New Jersey, 2007. — P. 160. — ISBN 978-0-470-11486-5 .