Akelarre

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Akelarre
Создатель:

Коллектив авторов в составе G. Álvarez Marañón, A. Fúster Sabater, D. Guía Martínez, F. Montoya Vitini, A. Peinado Domínguez

Опубликован:

1996 г.

Размер ключа:

128 бит (оптимальный)

Размер блока:

128 бит (оптимальный)

Число раундов:

4 (оптимальное)

Тип:

SP-сеть

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

Описание[править | править вики-текст]

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

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

Алгоритм работы[править | править вики-текст]

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

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

Шифрование[править | править вики-текст]

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

  • Входное преобразование состоит в сложении по модулю фрагментов ключа K01, K04 соответственно с субблоками X01, X04 и применении побитового исключающего ИЛИ (XOR) к фрагментам расширенного ключа K02, K03 и субблокам X02, X03 соответственно. Эти преобразования необходимы для предотвращения негативного эффекта от возможного попадания на вход последовательности из всех нулей или всех единиц, а так же для осложнения дифференциального криптоанализа(см. weak key[en]).
  • Раунды шифрования:
  1. В начале работы каждого из i раундов происходит циклический сдвиг 128-битного блока, получающегося в результате объединения субблоков, образованных в результате входного преобразования или предыдущего раунда; переменное число битов, задающих сдвиг, определяется младшими битами фрагмента ключа Kj1, формируемого в результате процедуры расширения ключа.
  2. На следующем этапе 128-битный блок снова разбивается на 4 субблока по 32 бита, и вычисляются побитовые ИЛИ для пары из первых двух, а затем и для пары последних двух блоков. Дальнейшие преобразования полученных в результате блоков С01, С02 определяются работой AR-модуля (addition-rotation structure). Структура модуля представляет собой два столбца: С01 подается на вход первого, С02 - второго. Для С01:
    • Первый 31 бит С01 циклически сдвигается влево (величина сдвига определяется 5 младшими битами С02).
    • Полученный на предыдущем шаге результат складывается по модулю числа с одним из фрагментов расширенного ключа Kj8.
    • Последний 31 бит выходного блока предыдущего шага циклически сдвигается влево аналогично шагу 1.
    • Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа с субключом Kj9 аналогично шагу 2.
    • Старший 31 бит выходного блока предыдущего шага циклически сдвигается влево как в шаге 1.
    • Получившийся на предыдущем шаге 32-битный блок складывается по модулю числа с субключом Kj10 как в шаге 2.
    • Шаги с 3 по 6 повторяются до тех пор, пока не будет осуществлено в общей сложности 7 сдвигов и 6 суммирований с субключами.
Аналогично обрабатывается С02, только с использованием ключей Kj2...Kj7.
Полученные в результате работы модуля блоки D1, D2 поступают на вход финального преобразования. Применение побитового сдвига не ко всему блоку, а только к 31 биту сделано, чтобы избежать возможного нежелательного эффекта при использовании составных чисел, когда результат на выходе оказывается идентичен входному.
  • Во время финального преобразования осуществляется циклический сдвиг образованного конкатенацией полученных после конечного раунда субблоков 128-битного блока влево на количество битов, определяемое 7 последними битами субключа Kf1, после чего получившийся блок разбивается на 32-битные субблоки, к которым применяются операции, аналогичные операциям входного преобразования, но уже с ключами Kf2...Kf5.

Дешифрование[править | править вики-текст]

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

Расширение ключа[править | править вики-текст]

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

  1. Пользовательский ключ разбивается на 8 частей по 16 битов k'1...k'8.
  2. Каждый отдельный фрагмент возводится в квадрат с получением 32-битного значения и происходит суммирование по модулю числа с константами a'1,a'2. Константы должны быть подобраны из соображений избежать возможного образования ключа, состоящего из одних нулей. Авторами предложены a'1=A49ED284H и a'2=73503DEH[4].
  3. 16 битов, располагающиеся в середине, используются в дальнейшей работе цикла для получения новых значений фрагментов расширенного ключа, а на основе 8 последних и 8 первых битов сформированных на предыдущем шаге 32-битных значений строятся субключи Kt'1...Kt'8 - используемые в начальном преобразовании, работе AR-модуля и финальном преобразовании ключи формируются из данных фрагментов[5].

Устойчивость[править | править вики-текст]

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

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

Значение[править | править вики-текст]

Задуманный как алгоритм, успешно сочетающий в себе элементы двух надежных и широко известных алгоритмов IDEA и RC5 и обладающий сложной архитектурой, Akelarre оказался достаточно слабоустойчивым, чем наглядно продемонстрировал, что не всегда объединение компонентов двух хорошо защищенных алгоритмов дает в итоге надежный новый (как сказано в названии одной из исследовавших алгоритм работ - "two rights sometimes make a wrong" (рус.: "два плюса иногда дают минус")[7][2].


Модификации[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]