28 апреля 2014

ARMADILLO – многоцелевой облегченный криптоалгоритм

Сергей Панасенко,
зам. директора Фирмы «АНКАД»
по науке и системной интеграции,
кандидат технических наук.

Алгоритм ARMADILLO разработан коллективом специалистов из Швейцарии и Франции в 2010 г.

ARMADILLO представляет собой многоцелевой криптографический алгоритм, который может быть основой для следующих применений [1]:

вычисления кодов аутентификации сообщений (MAC – Message Authentication Code) и хэширования;
генерации псевдослучайных чисел;
потокового шифрования.

Алгоритм ARMADILLO предназначен для использования в устройствах с ограниченными ресурсами, прежде всего, в радиочастотных идентификаторах (RFID – Radio-frequency Identification), поэтому структура алгоритма является крайне простой с целью простоты реализации и предъявления минимальных требований к ресурсам.

ARMADILLO запатентован компанией ORIDAO (Франция) [2].

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

ARMADILLO (известный также под названием ARMADILLO1) во многом представляет из себя шаблонный алгоритм, ряд параметров которого не определен. В частности, не определены основные параметры размеров, а именно:

размер вектора инициализации (IV – Initialization Vector или Initial Value) алгоритма c;
размер блока обрабатываемых данных m.

Общий размер блока входных данных алгоритма k равен c + m, а начальное значение блока X представляет собой результат конкатенации вектора инициализации и блока обрабатываемых данных M:

X = IV || M,

где:

|| – операция конкатенации;
IV – значение вектора инициализации.

В качестве левой части блока может использоваться не только вектор инициализации, но и, например, значение секретного ключа, состояние итеративной хэш-функции и пр. – в зависимости от конкретного применения алгоритма.

Перед обработкой блок входных данных расширяется до размера 2k, его значение D формируется как результат конкатенации блока X и блока, значение которого представляет собой побитовый комплемент к X, т. е.:

Расширенный блок входных данных D обрабатывается с помощью управляемой перестановки P(), которая будет описана далее. Перестановка P() управляется с помощью k-битного (нерасширенного) блока входных данных X.

Левая k-битная половина результата перестановки отбрасывается, а на правую половину (обозначена как S) операцией XOR снова накладывается блок входных данных X.

Результат всей этой последовательности действий представляется как конкатенация двух значений V_c и V_t, первое из которых имеет размер c, а второе – m. Авторы алгоритма предлагают различную трактовку V_c и V_t в зависимости от применения алгоритма, например [1]:

значение V_t может быть использовано в качестве MAC;
значение V_c может трактоваться как хэш-значение.

Описанная выше структура проиллюстрирована на рис. 1.

Рис

Рис. 1. Структура алгоритма ARMADILLO

Управляемая перестановка

Как было сказано выше, P() представляет собой управляемую перестановку. Данная перестановка в алгоритме не определена, в качестве варианта предлагается использовать перестановку, определенную в [3] (также подробно описана в [4]).

Основным элементом перестановки P() является элементарная управляемая перестановка P_2/1(), которая переставляет или не переставляет значения двух входных битов в зависимости от значения управляющего бита b (см. рис. 2):

y₁ = x₁₊_b;

y₂ = x_2-_b,

где:

x₁ и x₂ – входные биты;
y₁ и y₂ – выходные биты.

Рис

Рис. 2. Элементарная управляемая перестановка

Элементарные перестановки, количество которых равно половине размера входных данных (т. е., в данном случае, k элементарных перестановок, параллельно обрабатывающих 2k-битный блок) формируют активный уровень перестановки P(), управляемый k-битным вектором B. Активный уровень показан на рис. 3.

Рис

Рис. 3. Активный уровень

Наконец, перестановка P() формируется чередованием активных уровней элементарных управляемых перестановок и фиксированных перестановок, перемешивающих целиком 2k-битный блок (см. рис. 4). В общем случае, фиксированные перестановки могут быть уникальными для каждого уровня.

Рис

Рис. 4. Структура управляемой перестановки P()

В описании алгоритма ARMADILLO [1] не определены следующие параметры управляемой перестановки P():

количество активных уровней;
фиксированная перестановка;
как именно на основе блока X формируются управляющие биты.

Таким образом, алгоритм ARMADILLO представляет собой шаблон, на основе которого могут быть сформированы криптографические алгоритмы с уточненными параметрами.

ARMADILLO2

ARMADILLO2 – это еще один шаблонный алгоритм, предложенный теми же авторами в [1]. Как утверждают его авторы, ARMADILLO2 является еще более гибким, чем оригинальный алгоритм.

ARMADILLO2 использует те же концепции, что и алгоритм ARMADILLO; основные отличия ARMADILLO2 от исходного алгоритма состоят в следующем:

входной блок X не удваивается перед обработкой управляемой перестановкой;
вместо управляемой перестановки P() используется концептуально схожая перестановка Q(), в которую, в числе прочего, внедрена промежуточная операция XOR с корректирующей константой, в которой чередуются единичные и нулевые биты;
управляющая последовательность перестановки Q() предварительно обрабатывается дополнительной управляемой перестановкой Q(), которая управляется значением M.

Структура алгоритма ARMADILLO2 изображена на рис. 5.

Рис

Рис. 5. Структура алгоритма ARMADILLO2

Криптоанализ ARMADILLO и ARMADILLO2

Поскольку основой алгоритма является управляемая перестановка P(), можно предполагать, что криптоанализ алгоритмов, основанных на данной перестановке, может быть в той или иной степени применим к алгоритму ARMADILLO.

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

в работе [5] описана возможная атака на CIKS-1, основанная на замерах времени выполнения операций шифрования; в атаке используется тот факт, что в программной реализации алгоритма время выполнения управляемой перестановки является функцией от управляющих перестановкой данных; аппаратная реализация алгоритма данной атаке не подвержена, однако, авторы работы [5] утверждают, что программные реализации алгоритма вполне возможны – например, в смарт-картах; именно они могут быть основной мишенью для данной атаки; атака не позволяет напрямую получить значение секретного ключа алгоритма, однако, она позволит значительно снизить область возможных значений ключа; атака успешна при наличии порядка 10000 пар текстов и результатов соответствующих измерений;
в работе [6] предложена атака на вариант алгоритма CIKS-1 с уменьшенным числом раундов (6 из 8); как и в предыдущей атаке, здесь эксплуатируются особенности управляемой перестановки; атака позволяет существенно сузить область возможных значений ключа, но может использоваться только против слабых ключей;
в работе [7] применен дифференциальный криптоанализ, с помощью которого можно вычислить ключ последнего раунда алгоритма CIKS-1 выполнением 2⁸⁸ операций; для атаки требуется наличие около 2⁵⁶ пар текстов.

В результате можно сделать вывод, что программные реализации алгоритма ARMADILLO подвержены атакам по времени выполнения (впрочем, алгоритм ARMADILLO (как и CIKS-1) не предназначен для программных реализаций [1]).

Отметим, что остальные атаки могут быть проведены как на программные, так и на аппаратные реализации алгоритма CIKS-1, однако, область применения данных атак достаточно узка. Тем не менее, атаки эксплуатируют именно особенности управляемой перестановки P(), общей для алгоритмов CIKS-1 и ARMADILLO, следовательно, ARMADILLO может быть подвержен данным атакам.

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

Авторы работы [9] использовали атаку «встреча посередине» (meet-in-the-middle), с помощью которой им удалось инвертировать алгоритм ARMADILLO2, в результате чего стали возможны следующие атаки на данный алгоритм:

вычисление ключа при использовании алгоритма для вычисления MAC, а также при его применении в качестве алгоритма потокового шифрования;
вычисление первого и второго прообраза при использовании алгоритма в качестве хэш-функции.

При этом, некоторые из описанных в [9] атак на ARMADILLO2 (в зависимости от конкретных параметров алгоритма) по ресурсоемкости оказались на грани практической применимости.

Таким образом, алгоритмы семейства ARMADILLO весьма интересны своей необычной структурой, предопределяемой их назначением – это многоцелевые криптоалгоритмы для использования в устройствах с ограниченными ресурсами. Однако, благодаря предложенным в 2011 г. атакам, их практическое применение не выглядит целесообразным.

Литература

Badel S., Dagtekin N., Nakahara J. Jr., Ouafi K., Reffé N., Sepehrdad P., Sušil P., Vaudenay S. ARMADILLO: a Multi-Purpose Cryptographic Primitive Dedicate to Hardware. // http://infoscience.epfl.ch – 2010.
ORIDAO Home Page. // http://www.oridao.com.
Moldovyan A. A., Moldovyan N. A. A cipher based on data-dependent permutations. // Journal of Cryptology, Vol. 15, pp 61-72 – January 2002.
Moldovyan N., Sklavos N., Koufopavlou O. Pure DDP-Based Cipher: Architecture Analysis, Hardware Implementation Cost and Performance up to 6.5 Gbps. // The International Arab Journal of Information Technology, Vol. 2, No. 1, January 2005.
Furlong M., Heys H. A Timing Attack on the CIKS-1 Block Cipher. // http://www.engr.mun.ca – Memorial University of Newfoundland, St John’s, NL, Canada.
Kidney B. J., Heys H. M., Norvell T. S. A Weight Based Attack on the CIKS-1 Block Cipher. // http://www.engr.mun.ca – Memorial University of Newfoundland – November 12, 2003.
Kidney B. J., Heys H. M., Norvell T. S. A Differential Attack on the CIKS-1 Block Cipher. // http://www.engr.mun.ca – Memorial University of Newfoundland, St John’s, NL, Canada – CCECE 2004, Niagara Falls, May 2004.
Sepehrdad P., Sušil P., Vaudenay S. Fast Key Recovery Attack on ARMADILLO1 and Variants. // http://infoscience.epfl.ch – EPFL, Lausanne, Switzerland.
Abdelraheem M. A., Blondeau C., Naya-Plasencia M., Videau M., Zenner E. Cryptanalysis of ARMADILLO2. // http://eprint.iacr.org – 2011.