Akelarre
Akelarre | |
---|---|
Создатель | Коллектив авторов в составе G. Álvarez Marañón, A. Fúster Sabater, D. Guía Martínez, F. Montoya Vitini, A. Peinado Domínguez |
Опубликован | 1996 г. |
Размер ключа | Кратный 64 битам (рекомендуемый - 128 бит) |
Размер блока | 128 бит |
Число раундов | Любое (рекомендуемое - 4) |
Тип | SP-сеть |
Akelarre — блочный шифр, разработанный коллективом испанских авторов и представленный на SAC в 1996 году; объединяет основную разработку IDEA с концепциями от RC5. Название akelarre также используется в баскском языке для обозначения собрания ведьм[1].
Описание
[править | править код]Akelarre является 128-битным блочным шифром. При этом длина ключа переменная, должна быть кратной 64 битам; число проходов шифрования так же является изменяемым параметром. Оптимальные значения, предложенные авторами — 128-битный ключ и 4 раунда[2]. Функция шифрования в Akelarre структурно похожа на представленную в IDEA. Однако между этими шифрами в целом есть ряд существенных отличий: так, в IDEA используется 16-битный размер слова, а не 32-битный, также различается набор используемых примитивных операций. В Akelarre применяются[3]:
- сложение по модулю ;
- побитовое исключающее ИЛИ (XOR);
- операции циклического сдвига влево на переменное число бит ().
Именно использование циклического сдвига на переменное число битов определяет схожесть этого алгоритма с RC5[4]. Все перечисленные операции относятся к различным алгебраическим группам и несовместимы в том смысле, что для любой пары из них не выполняются ассоциативный и дистрибутивный законы. Это позволяет скрыть все существующие взаимосвязи между открытым и зашифрованным текстами и ключом, затруднив криптоанализ[5].
Алгоритм работы
[править | править код]![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/60/Akelarre_algorithm.png/220px-Akelarre_algorithm.png)
Структурно алгоритм может быть разделен на две подчасти:
- Алгоритм шифрования/дешифрования.
- Алгоритм расширения ключа, вводимого пользователем.
Шифрование
[править | править код]Сперва открытый текст X разбивается на 128-битные блоки, каждый из которых в свою очередь разбивается на 4 субблока X1…X4, к которым уже применяется первичное преобразование. Вся процедура шифрования происходит в три этапа.
- Входное преобразование состоит в сложении по модулю фрагментов расширенного ключа Ki1, Ki4 соответственно с субблоками X1, X4 и применении побитового исключающего ИЛИ (XOR) к фрагментам расширенного ключа Ki2, Ki3 и субблокам X2, X3 соответственно. Эти преобразования необходимы для предотвращения последствий возможного попадания на вход последовательности из всех нулей или всех единиц, а также для затруднения проведения атаки на шифр методом дифференциального криптоанализа(см. weak key[англ.]).
- Раунды шифрования:
- В начале работы каждого из раундов происходит циклический сдвиг 128-битного блока, получающегося в результате объединения субблоков, образованных в результате входного преобразования или предыдущего раунда; на -ом раунде () переменное число битов, задающих сдвиг, определяется младшими битами фрагмента ключа Km1, формируемого в результате процедуры расширения ключа.
- На следующем этапе 128-битный блок снова разбивается на 4 субблока по 32 бита, и вычисляются побитовые ИЛИ для пары из первых двух, а затем и для пары последних двух блоков. Дальнейшие преобразования полученных в результате блоков С1, С2 определяются работой AR-модуля (addition-rotation structure). Структура модуля представляет собой два столбца: С1 подается на вход первого, С2 — второго. Для С1:
- Первый 31 бит С1 циклически сдвигается влево (величина сдвига определяется 5 младшими битами С2).
- Полученный на предыдущем шаге результат складывается по модулю числа с одним из фрагментов расширенного ключа Km8.
- Последний 31 бит выходного блока предыдущего шага циклически сдвигается влево аналогично шагу 1.
- Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа с субключом Km9 аналогично шагу 2.
- Старший 31 бит выходного блока предыдущего шага циклически сдвигается влево как в шаге 1.
- Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа с субключом Km10 как в шаге 2.
- Шаги с 3 по 6 повторяются до тех пор, пока не будет осуществлено в общей сложности 7 сдвигов и 6 суммирований с субключами.
- Аналогично обрабатывается С02, только с использованием ключей Km2…Km7.
- Из полученных в результате работы модуля блоков D1, D2 путем сложения с блоками, образованными разбиением 128-битного блока в начале раунда, формируются 4 выходных значения раунда (каждый из X1, X3 суммируется с D1, а каждый из X2, X4 — с D2). Применение побитового сдвига не ко всему блоку, а только к 31 биту сделано, чтобы избежать возможной идентичности выходного и входного результатов, которая может наблюдаться при использовании составных чисел[6].
- Во время финального преобразования осуществляется циклический сдвиг образованного конкатенацией полученных после конечного раунда подблока 128-битного блока влево на количество битов, определяемое 7 последними битами подключа Kf1, после чего получившийся блок разбивается на 32-битные подблока, к которым применяются операции, аналогичные операциям входного преобразования, но уже с ключами Kf2…Kf5[7].
Расшифрование
[править | править код]Алгоритм расшифрования в сущности организован тем же образом, что и используемый для шифрования, только подключи генерируются уже на основе ключей шифрования. Соответствие между ключами для шифрования и для расшифрования имеет следующий вид (здесь начальное преобразование понимается как нулевой раунд, а финальное преобразование — как (r+1)-й раунд)[8]:
Раунд | Ключи, используемые при шифровании | Ключи, используемые при дешифровании |
---|---|---|
Начальное преобразование | ||
1-й раунд | ||
2-й раунд | ||
m-й раунд | ||
r-й раунд | ||
Финальное преобразование |
Расширение ключа
[править | править код]Для возможности работы алгоритма требуется ключ, состоящий по меньшей мере из хотя бы 22 субблоков по 32 бита (704 бита)[9]. Дальнейшее описание соответствует применению алгоритма к 128-битному ключу:
- Пользовательский ключ разбивается на 8 частей по 16 битов k1…k8.
- Каждый отдельный фрагмент возводится в квадрат с получением 32-битного значения, и происходит суммирование по модулю числа получившихся значений отдельно с каждой из констант a1, a2; в результате на основе каждого из исходных ключей ki1 образуется по два временных значения Kti и K'ti. Константы должны быть подобраны из соображений избежать возможного образования ключа, состоящего из одних нулей. Авторами предложены a1=A49ED284H и a2=73503DEH[10].
- Из полученных на предыдущем шаге временных значений формируются фрагменты предварительного расширенного ключа Ke1…Ke8. Каждый из этих фрагментов является результатом конкатенации 8 младших и 8 старших битов K'ti, а также 8 младших и 8 старших битов Kti; 16 же битов, располагающиеся в середине каждого из временных значений, обрабатываются уже схожим с обработкой k1…k8 образом для получения новых значений фрагментов расширенного ключа[11].
- Ключи, используемые в начальном преобразовании (Ki1…Ki4), работе AR-модуля (Km1…Km13 для каждого из m раундов) и финальном преобразовании (Kf1…Kf5) заполняются поочередно формируемыми в ходе работы алгоритма значениями Ke1…Ke8[12].
Устойчивость
[править | править код]Уже спустя год после того, как шифр был представлен, в работе Нильса Фергюсона и Брюса Шнайера была осуществлена атака, позволяющая осуществить взлом на основе выборки из не более, чем 100 открытых текстов. Атака происходит в 4 этапа: в первых двух происходит восстановление начального и финального преобразований битов субключей, а следующие два используют уязвимости схемы расширения ключа, причем с увеличением числа раундов в алгоритме резко увеличивается и количество информации, которое может быть получено о работе схемы. Сложность организации AR-модуля в силу его свойств (свойства четности) нисколько не затрудняет взлом[13]. В той же работе приводится и ещё одна атака, в которой дополнительно использование дифференциальной характеристики алгоритма позволяет сократить число необходимых операций в итоге до .
Ещё одна работа, в которой с успехом был осуществлен криптоанализ Akelarre, принадлежит Ларсу Кнудсену и Винсенту Риджмену. Они описывают две возможные атаки: одна основана на использовании открытого текста, другая позволяет раскрыть ключ используя только зашифрованный текст и некоторую информацию об открытом тексте — в частности, достаточно знать, что это текст на английском языке в ASCII-кодировке. Так же, как и атаки, предложенные в работе Фергюсона и Шнайера, атаки, предложенные в этой работе, не зависят от числа раундов алгоритма или размера ключа, а атака, использующая только шифротекст, относится к числу наиболее практически применимых, так как уже одного прослушивания канала достаточно для её проведения[14].
Значение
[править | править код]Задуманный как алгоритм, успешно сочетающий в себе элементы двух надежных и широко известных алгоритмов IDEA и RC5 и обладающий сложной архитектурой, Akelarre не продемонстрировал высокой криптостойкости, чем наглядно показал, что не всегда объединение компонентов двух хорошо защищенных алгоритмов дает в итоге надежный новый[15]. Как сказано в названии одной из исследовавших алгоритм работ[16]:
Два плюса иногда дают минус.
Оригинальный текст (англ.)Two rights sometimes make a wrong.
Модификации
[править | править код]После успешного криптоанализа Akelarre его проектировщики представили обновлённый вариант, названный Ake98. Этот шифр отличается от оригинального Akelarre новой AR-box (Addition-Rotation box), перестановкой слов, осуществляемой в конце прохода шифрования, а также добавлением подключей в начале каждого прохода шифрования. При этом такие параметры, как размер ключа и размер блока, остались, как и прежде, регулируемыми, но их минимальный размер создателями не определён[17]. AR-модуль работает в новой версии как генератор псевдослучайных чисел.
В 2004 году Хорхе Накаара младший и Даниэль Сантана де Фреита нашли большие классы слабых ключей для Ake98. Эти слабые ключи позволяют анализировать быстрее, чем полным перебором, используя только 71 известный фрагмент текста для 11,5 проходов шифрования в Ake98. Кроме того, в этой же работе была осуществлена оценка производительности алгоритма, которая показала, что хотя и для числа раундов 25,5 или большего алгоритм не имеет слабых ключей, он оказывается в 4 раза медленнее IDEA, в 8 раз медленнее AES, и в 14 раз — RC6[18].
Примечания
[править | править код]- ↑ Stamp M. et al, 2007, p. 160.
- ↑ Панасенко С., 2009, с. 101.
- ↑ Álvarez M. G. et al, 1996, p. 2—3.
- ↑ Панасенко С., 2009, с. 99.
- ↑ Álvarez M. G. et al, 1996, p. 2.
- ↑ Álvarez M. G. et al, 1996, p. 5—6.
- ↑ Панасенко С., 2009, с. 98—100.
- ↑ Álvarez M. G. et al, 1996, p. 6.
- ↑ Álvarez M. G. et al, 1996, p. 7.
- ↑ Álvarez M. G. et al, 1996, p. 7—8.
- ↑ Панасенко С., 2009, с. 101—102.
- ↑ Ferguson N. et al, 1997, p. 207—208.
- ↑ Ferguson N. et al, 1997, p. 210—211.
- ↑ Панасенко С., 2009, с. 102—103.
- ↑ Knudsen L. et al, 1997, p. 223.
- ↑ Панасенко С., 2009, с. 103.
- ↑ Júnior J. et al, 2005, p. 208.
- ↑ Júnior J. et al, 2005, p. 213—214.
Литература
[править | править код]- Á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 // Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 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.
- Júnior J. N., de Freitas D. S. Cryptanalysis of Ake98 (англ.) // Progress in Cryptology — INDOCRYPT 2004: 5th International Conference on Cryptology in India, Chennai, India, December 20-22, 2004. Proceedings / A. Canteaut, K. Viswanathan — Berlin, Heidelberg, New York City, London: Springer Berlin Heidelberg, 2005. — P. 206—217. — 431 p. — (Lecture Notes in Computer Science; Vol. 3348) — ISBN 978-3-540-24130-0 — ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-540-30556-9_17
- 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.