Меню Главная Случайная статья Настройки Akelarre Материал из https://ru.wikipedia.org Akelarre — блочный шифр, разработанный коллективом испанских авторов и представленный на SAC в 1996 году; объединяет основную разработку IDEA с концепциями от RC5. Название akelarre также используется в баскском языке для обозначения собрания ведьм[1]. Содержание 1 Описание 2 Алгоритм работы 2.1 Шифрование 2.2 Расшифрование 2.3 Расширение ключа 3 Устойчивость 4 Значение 5 Модификации 6 Примечания 7 Литература Описание Akelarre является 128-битным блочным шифром. При этом длина ключа переменная, должна быть кратной 64 битам; число проходов шифрования так же является изменяемым параметром. Оптимальные значения, предложенные авторами — 128-битный ключ и 4 раунда[2]. Функция шифрования в Akelarre структурно похожа на представленную в IDEA. Однако между этими шифрами в целом есть ряд существенных отличий: так, в IDEA используется 16-битный размер слова, а не 32-битный, также различается набор используемых примитивных операций. В Akelarre применяются[3]: сложение по модулю ${\displaystyle 2^{m}}$; побитовое исключающее ИЛИ (XOR); операции циклического сдвига влево на переменное число бит (${\displaystyle x\lll y}$). Именно использование циклического сдвига на переменное число битов определяет схожесть этого алгоритма с RC5[4]. Все перечисленные операции относятся к различным алгебраическим группам и несовместимы в том смысле, что для любой пары из них не выполняются ассоциативный и дистрибутивный законы. Это позволяет скрыть все существующие взаимосвязи между открытым и зашифрованным текстами и ключом, затруднив криптоанализ[5]. Алгоритм работы Структурно алгоритм может быть разделен на две подчасти: Алгоритм шифрования/дешифрования. Алгоритм расширения ключа, вводимого пользователем. Шифрование Сперва открытый текст X разбивается на 128-битные блоки, каждый из которых в свою очередь разбивается на 4 субблока X1…X4, к которым уже применяется первичное преобразование. Вся процедура шифрования происходит в три этапа. Входное преобразование состоит в сложении по модулю ${\displaystyle 2^{32}}$ фрагментов расширенного ключа Ki1, Ki4 соответственно с субблоками X1, X4 и применении побитового исключающего ИЛИ (XOR) к фрагментам расширенного ключа Ki2, Ki3 и субблокам X2, X3 соответственно. Эти преобразования необходимы для предотвращения последствий возможного попадания на вход последовательности из всех нулей или всех единиц, а также для затруднения проведения атаки на шифр методом дифференциального криптоанализа(см. weak key[англ.]). Раунды шифрования: В начале работы каждого из ${\displaystyle r}$ раундов происходит циклический сдвиг 128-битного блока, получающегося в результате объединения субблоков, образованных в результате входного преобразования или предыдущего раунда; на ${\displaystyle m}$-ом раунде (${\displaystyle m=1,2,\ldots ,r}$) переменное число битов, задающих сдвиг, определяется младшими битами фрагмента ключа Km1, формируемого в результате процедуры расширения ключа. На следующем этапе 128-битный блок снова разбивается на 4 субблока по 32 бита, и вычисляются побитовые ИЛИ для пары из первых двух, а затем и для пары последних двух блоков. Дальнейшие преобразования полученных в результате блоков С1, С2 определяются работой AR-модуля (addition-rotation structure). Структура модуля представляет собой два столбца: С1 подается на вход первого, С2 — второго. Для С1: Первый 31 бит С1 циклически сдвигается влево (величина сдвига определяется 5 младшими битами С2). Полученный на предыдущем шаге результат складывается по модулю числа ${\displaystyle 2^{32}}$ с одним из фрагментов расширенного ключа Km8. Последний 31 бит выходного блока предыдущего шага циклически сдвигается влево аналогично шагу 1. Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа ${\displaystyle 2^{32}}$ с субключом Km9 аналогично шагу 2. Старший 31 бит выходного блока предыдущего шага циклически сдвигается влево как в шаге 1. Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа ${\displaystyle 2^{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]: Раунд Ключи, используемые при шифровании Ключи, используемые при дешифровании Начальное преобразование ${\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 бита)[9]. Дальнейшее описание соответствует применению алгоритма к 128-битному ключу: Пользовательский ключ разбивается на 8 частей по 16 битов k1…k8. Каждый отдельный фрагмент возводится в квадрат с получением 32-битного значения, и происходит суммирование по модулю числа ${\displaystyle 2^{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]. В той же работе приводится и ещё одна атака, в которой дополнительно использование дифференциальной характеристики алгоритма позволяет сократить число необходимых операций в итоге до ${\displaystyle 2^{32}}$. Ещё одна работа, в которой с успехом был осуществлен криптоанализ Akelarre, принадлежит Ларсу Кнудсену и Винсенту Риджмену. Они описывают две возможные атаки: одна основана на использовании открытого текста, другая позволяет раскрыть ключ используя только зашифрованный текст и некоторую информацию об открытом тексте — в частности, достаточно знать, что это текст на английском языке в ASCII-кодировке. Так же, как и атаки, предложенные в работе Фергюсона и Шнайера, атаки, предложенные в этой работе, не зависят от числа раундов алгоритма или размера ключа, а атака, использующая только шифротекст, относится к числу наиболее практически применимых, так как уже одного прослушивания канала достаточно для её проведения[14]. Значение Задуманный как алгоритм, успешно сочетающий в себе элементы двух надежных и широко известных алгоритмов IDEA и RC5 и обладающий сложной архитектурой, Akelarre не продемонстрировал высокой криптостойкости, чем наглядно показал, что не всегда объединение компонентов двух хорошо защищенных алгоритмов дает в итоге надежный новый[15]. Как сказано в названии одной из исследовавших алгоритм работ[16]: Два плюса иногда дают минус. Модификации После успешного криптоанализа 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. Jnior J. et al, 2005, p. 208. Jnior J. et al, 2005, p. 213—214. Литература lvarez M. G., Fster S. A., Gua 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 с. 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. Jnior 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.