Малоресурсное шифрование

Введение

Информационные технологии необратимо проникли в повседневную деятельность каждого — жизнь обычного человека уже нельзя представить без различных гаджетов. Во многих домах используются устройства со встроенной операционной системой (помимо обычных персональных компьютеров), которые могут быть подключены к сети Интернет и даже объединены в беспроводную сеть. Везде люди окружены разнообразными терминалами, считывателями, датчиками и т. д.

Такое распространение интеллектуальных технологий резко поднимает проблему безопасности данных. Однако, сейчас невозможно предложить криптографический примитив, который можно было бы реализовать на всех типах целевых устройств. Можно утверждать, что AES (англ.: Advanced Encryption Standard) действительно сильный алгоритм с хорошей производительностью и желательно использовать AES в устройствах высокого класса, в большом количестве встроенных систем или в некоторых устройствах низкого уровня (с некоторыми ограничениями). Однако невозможно использовать обычные криптографические алгоритмы в устройствах с крайне ограниченными ресурсами. Примерами таких устройств являются:

• RFID-считыватели (англ.: Radio Frequency Identification);

• Смарт-карты (включая беспроводные);

• Беспроводные сенсоры;

• Индикаторы, датчики, контроллеры;

• Интернет вещей и др.

Основные принципы и подходы к разработке алгоритмов, предназначенных для использования в устройствах с чрезвычайно низкими ресурсами, отличаются от критериев проектирования обычно используемых криптографических алгоритмов. Эта весьма специфическая область покрывается ветвью современной криптографии — малоресурсной криптографией (англ.: Lightweight cryptography). Стандарты малоресурсной криптографии, например, ISO/IEC 29192-2:2012 и ISO/IEC 29192-2:2019 не определяют строгих критериев для классификации криптографического алгоритма как “малоресурсного”, но общие черты таких алгоритмов — чрезвычайно низкие требования к основным ресурсам целевых устройств, включая следующее:

• Размер, необходимый для аппаратной реализации;

• Вычислительная мощность микропроцессоров или микроконтроллеров;

• Оперативная память (RAM);

• Постоянная память (ROM) и т. д.

Стандарт ISO/IEC 29192-2:2012 представляет блочные шифры PRESENT и CLEFIA, применимые на устройствах с крайне ограниченными ресурсами. Следующие версии данного стандарта включают в себя множество других малоресурсных блочных шифров [8].

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

DESL & DESXL

Шифры DESL (англ.: DES Lightweight)  и DESXL (англ.: DES-Xor Lightweight) создавались для использования в RFID-считывателях, но благодаря своей простоте стали широко популярны и в других приложениях, таких как датчики температуры, геолокационные устройства.

DESL был изначально основан на классическом алгоритме DES (англ.: Data Encryption Standard) — алгоритме с симметричным ключом шифрования, размер блока которого равен 64 битам. Алгоритм DES построен на восьми S-блоках — функциях в коде программы или части аппаратной системы, принимающих на вход n бит, преобразующих их по определённому алгоритму и возвращающих на выходе m бит. В отличие от DES, DESL использует всего один S-блок вместо восьми S-блоков в DES. Критерии проектирования одиночного S-блока делают DESL устойчивым к наиболее распространенным криптоаналитическим атакам.

DESXL — это облегченная версия алгоритма DESX (англ.: DES-Xor), который является одним из широко используемых вариантов DES. В отличие от DES, DESX выполняет отбеливание (см. key whitening) входных и выходных данных с помощью определенных “подключей”, что позволяет повысить безопасность повторяющегося блочного шифра. Как и DESL, DESXL использует тот же единственный S-блок вместо 8 S-блоков в DESX. Таким образом, DESXL объединяет в себе свойства DESX и DESL: от DESL наследуется упрощение в блочной части шифрования, а от DESX — отбеливание ключа.

Относительно низкие требования к ресурсам DESL / DESXL — всего лишь результат восьмикратного сокращения требований к ПЗУ для хранения таблиц (поскольку это единственное отличие DESL / DESXL от классических алгоритмов). Если говорить о использовании DESL и DESXL на практике, то авторы DESL / DESXL утверждают в [1], что такого снижения требований достаточно для использования предложенных алгоритмов в устройствах с ограниченными ресурсами на примере пассивных RFID-считывателей.

Curupira

Curupira создавался для использования в приложении геолокации, например в сенсорных датчиках.  Кроме того, он представляет собой инволюционную структуру (это означает, что процессы шифрования и дешифрования идентичны) и очень гибок с точки зрения реализации. Таким образом, шифр хорошо адаптирован к сценариям с ограниченными ресурсами. Данный шифр — вариант семейства алгоритмов, использующих стратегию Wide Trail — метод увеличения диффузии особым образом для противостояния дифференциальному и линейному криптоанализу. Другими примерами алгоритмов, использующих стратегию Wide Trail, являются AES, Anubis и Khazad. Относительно низкие потребности Curupira в ресурсах определяются следующим набором факторов:

• Размер внутреннего состояния алгоритма относительно невелик (96 бит; по сравнению со 128 битами внутреннего состояния AES);

• Возможность реализовать 8 X 8-битный S-блок Curupira S () как композицию двух 4 X 4-битных S-блоков P () и Q (), полностью унаследованных от Anubis и Khazad. Эта возможность позволяет снизить требования к ПЗУ для хранения S-блоков.

Размер блока Curupira составляет 96 бит; он принимает несколько фиксированных длин ключей: 96, 144 или 192 бита. Блок данных представлен в виде массива размером 3 X 4 байта (внутреннее состояние алгоритма); каждый раунд Curupira изменяет внутреннее состояние с помощью следующих операций:

1. Нелинейный слой γ; состоит из параллельного применения S-блока S () ко всем байтам внутреннего состояния;

2. Слой перестановки π; меняет местами каждый столбец состояния в соответствии с предопределенным правилом;

3. Линейный диффузионный слой θ; выполняет умножение состояния на заранее заданную матрицу D;

4. Ключевой дополнительный слой σ (K_r); выполняет поразрядное сложение r-раундового ключа K_r;

5. Количество раундов строго не определяется: алгоритм определяет минимальное и максимальное количество раундов для каждой разрешенной длины ключа (от 10 раундов для 96-битного ключа до 23 раундов для 192-битного). Отбеливание на входе выполняется перед первым раундом путем добавления подключа K₀. В последнем раунде операция θ не выполняется.

KATAN & KTANTAN

KATAN — это семейство блочных шифров: KATAN32, KATAN48 и KATAN64. Число в названии алгоритма представляет размер блока алгоритма в битах. Все шифры используют 80-битные ключи.

Самый маленький шифр из всего семейства, KTANTAN32, может быть реализован в 462 GE (англ.: Gate Equivalent, единица измерения, которая позволяет определять сложность цифровых электронных схем, не зависящую от технологии производства) при достижении скорости шифрования 12,5 Кбит / с (при 100 кГц). KTANTAN48, версия, рекомендуемая для RFID-меток, использует 588 GE, тогда как KATAN64, самый большой и самый гибкий шифр в семействе, использует 1054 GE и имеет пропускную способность 25,1 Кбит / с (на 100 кГц). Данный шифр используется в огромном количестве low-end устройств, например, в датчиках геолокации и метеодатчиках.

Семейство KTANTAN также содержит три алгоритма с одинаковыми размерами блоков и длиной ключа. KTANTAN более компактен в аппаратном обеспечении — он предполагает, что ключ записан в целевое устройство и не может быть изменен, кроме того, key schedule KTANTAN намного проще по сравнению с KATAN. Сам key schedule — это алгоритм, который расширяет относительно короткий главный ключ (обычно длиной от 40 до 256 бит) до относительно большого расширенного ключа (обычно несколько сотен или тысяч бит) для последующего использования в алгоритме шифрования и дешифрования. Остальные процедуры шифров KATAN и KTANTAN эквивалентны. Структура алгоритмов основана на структуре потокового шифра (вариант с двумя регистрами). Размер внутреннего состояния эквивалентен размеру блока алгоритма. Каждый из алгоритмов KATAN загружает блок данных в два внутренних регистра сдвига L₁ и L₂. Выполняет 254 раунда; каждый из которых использует нелинейные функции, которые формируют обратную связь регистров (Рис. 1). Размеры регистров и конкретные биты, используемые функциями нелинейной обратной связи, фиксированы для каждого алгоритма KATAN и KTANTAN и определены в [2]. Одна из нелинейных функций использует определенное нерегулярное значение (IR) в дополнение к нескольким битам регистра. Это значение зависит от номера раунда. KATAN48 и KATAN64 имеют те же нелинейные функции, что и KATAN32, но они используют другие биты внутренних регистров для формирования обратной связи. KATAN48 и KATAN64 также используют регистры большего размера в соответствии с размерами блоков. KATAN32 обновляет регистры один раз за раунд; KATAN48 и KATAN64 используют нелинейные функции два или три раза соответственно.

Key schedule в KATAN основан на регистре сдвига с линейной обратной связью (англ.: LFSR). Другой LFSR используется для подсчета раундов и остановки шифрования при необходимости. Самый старший бит последнего LFSR формирует вышеупомянутое нерегулярное значение.

Требования к ресурсам KATAN и KTANTAN чрезвычайно низкие из-за следующего набора факторов:

• Использование регистров сдвига, которые очень легко могут быть реализованы аппаратно; функции обратной связи также очень просты, хотя и обеспечивают необходимую нелинейность;

• Обработка небольших блоков данных: от 32 до 64 бит;

• Размер внутреннего состояния невелик и его размер равен размеру блока (+ дополнительно LSFR для подсчета раундов);

• Key schedule в KTANTAN предельно прост.

PRESENT

PRESENT —  пример шифра-сети замещения-перестановки. Данный блочный шифр изначально создан для замены относительно тяжелого шифра AES в таких устройствах как RFID-считыватели и сенсорные сети. PRESENT выполняет 31 раунд на 64-битном блоке данных и позволяет использовать 80- или 128-битные ключи. Каждый раунд состоит из следующих операций:

• Добавление раундового ключа операцией XOR;

• Использование диффузионного слоя (S-слой);

• Использование слоя трансформации смешения (P-слой).

PRESENT основан на слоях преобразования Serpent [3] и DES [4], которые были подробно проанализированы. Диффузионный слой выполняет нелинейную замену 16 4-битных подблоков текущего состояния, используя параллельный S-блок Serpent 4 X 4.

Слой преобразования перемешивания выполняет предварительно определенную перестановку битового уровня. Он основан на слое преобразования смешивания DES и кажется наиболее простым для реализации. В программном обеспечении P-уровень может быть реализован как битовые операции или с использованием соответствующей таблицы «P-блок». Также PRESENT выполняет отбеливание выходных данных после финального раунда.

Hummingbird

Hummingbird может обеспечить необходимую безопасность с блоком небольшого размера и устойчив к наиболее распространенным атакам, таким как линейный и дифференциальный криптоанализ. Кроме того, в исходном исследовании предлагается эффективная программная реализация Hummingbird на 8-битном микроконтроллере ATmega128L от Atmel и 16-битном микроконтроллере MSP430 [7].

Hummingbird шифрует 16-битные блоки данных с помощью 256-битного ключа.

Базовая архитектура Hummingbird оригинальна и гибридна (с элементами блочного и потокового шифров). Процедуру шифрования можно представить, как непрерывно работающую роторную машину. Четыре идентичных внутренних блочных шифра играют роль виртуальных роторов. Они выполняют набор операций с короткими 16-битными блоками данных.

Hummingbird использует сложение по модулю 216 для смешивания регистров внутреннего состояния с блоком данных, который нужно обработать. В качестве альтернативы высокоуровневая структура алгоритма может быть представлена как 4-раундовый блочный шифр с операциями обратной связи, которые позволяют использовать внутреннее объединение блоков шифра в качестве дополнительного преимущества структуры алгоритма (Рис. 2). Относительно низкие требования к ресурсам Hummingbird достигаются за счет простых арифметических и логических операций и использования чрезвычайно коротких блоков данных.

Основные подходы к проектированию малоресурсных алгоритмов шифрования

Одна из тенденций криптографии в общем предполагает, что криптографические примитивы должны быть как можно сложнее и «тяжелее». В связи с этим, основные параметры блочных шифров (размер блока, длина ключа, размер внутреннего состояния и т. д.) постоянно увеличиваются. Это компенсирует непрерывное увеличение вычислительной мощности компьютерных систем и лавинообразный рост объемов обрабатываемых данных. Следовательно, требования к ресурсам (и сложность их реализации) для блочных шифров неизбежно растут, чтобы сделать блочные шифры более криптоустойчивыми и эффективными.

Этот подход в принципе не подходит для встраиваемых систем, особенно для систем с крайне ограниченными ресурсами. Малоресурсная криптография делает стоимость внедрения наиболее важным критерием. Уровень безопасности и производительность алгоритмов также должны быть адекватными, т.е. очень желательно найти компромисс между этими тремя характеристиками; и такой компромисс сильно зависит от ресурсов целевых устройств.

На примере рассмотренных выше алгоритмов можно попытаться обобщить основные методы, которые используют авторы облегченных алгоритмов для поиска необходимого баланса:

• Уменьшение основных параметров алгоритма: размера блока, длины ключа (естественно, в разумных пределах) и внутреннего состояния алгоритма;

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

• Упрощение слоев преобразований, например, снижение требований к ПЗУ за счет использования S-блоков 4 X 4 (в идеале — одного S-блока 4 X 4) или использования их состава для замены более крупных подблоков;

• Использование недорогих (с точки зрения реализации), но эффективных элементов, таких как зависящие от данных перестановки битов, регистры сдвига и т. д.;

• Разработка алгоритмов key schedule, которые могут выводить подключи на месте (т. е. подключи не нужно предварительно вычислять).

• Использование операций, которые допускают компромиссы при реализации в соответствии с ресурсами, доступными на целевой платформе.

Ограничения и компромиссы

Как было сказано выше, цель разработки малоресурсного алгоритма шифрования — найти компромисс между низкими требованиями к ресурсам, производительностью и криптографической стойкостью алгоритма (включая безопасное использование целевого устройства с алгоритмом внутри). Ограничения ресурсов вынуждают криптографов разрабатывать облегченные алгоритмы с небольшим или относительно небольшим размером блока и длиной ключа. В частности, это позволяет злоумышленнику атаковать облегченный алгоритм, используя атаку сопоставления зашифрованного текста: для m-битового блочного шифра равные блоки зашифрованного текста могут ожидаться после шифрования 2^m/2 блоков данных (см. “Атака Дней рождения”); это может быть связано с утечкой информации о блоках открытого текста. Злоумышленник может составить исчерпывающий словарь блоков для текущего ключа после шифрования 2^m блоков данных. Таким образом, атака по совпадению шифротекста эффективна, например, против 16-, 32- и 48-битных блочных шифров. Поэтому очень небезопасно использовать алгоритмы с небольшими размерами блоков в таких режимах, как ECB (англ.: Electronic Codebook) — необходимо предусмотреть некоторые ограничения для использования таких алгоритмов: использовать их в сложных режимах, регулярно менять ключ и т.д. К сожалению, такие ограничения или рекомендации создают дополнительную нагрузку на целевое устройство; соблюдение рекомендаций может быть невозможно для конкретного алгоритма (например, семейство алгоритмов KTANTAN не позволяет изменять ключ).

Следовательно, необходимо понимать, что малоресурсные криптографические примитивы могут быть использованы в системах с относительно низкими или средними требованиями к безопасности или в системах, которые могут учитывать специфику используемого алгоритма, что позволяет найти желаемый компромисс.

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

Заключение

Мы рассмотрели некоторые примеры малоресурсных блочных шифров и выделили обобщенные подходы к разработке таких шифров. Кроме того, выделены ограничения и компромиссы, связанные с реализацией малоресурсных алгоритмов шифрования.

Список литературы

[1] G. Leander, C. Paar, A. Poschmann, and K. Schramm. New Lightweight DES Variants. FSE 2007, LNCS, vol. 4593, pp. 196-210. Springer, 2007.

[2] C. De Cannière, O. Dunkelman, M. Knežević. KATAN & KTANTAN – A Family of Small and Efficient Hardware-Oriented Block Ciphers. CHES’09, LNCS, vol. 5747, pp. 272-288. Springer, 2009

[3] R. J. Anderson, E. Biham, and L. R. Knudsen. Serpent: A Proposal for the Advanced Encryption Standard. Available at http://www.cl.cam.ac.uk

[4] FIPS Publication 46-3. Data Encryption Standard (DES). U. S. Department of Commerce / National Institute of Standards and Technology. Reaffirmed 1999 October 25.

[5] Sergey Panasenko and Sergey Smagin. Lightweight Cryptography: Underlying Principles and Approaches. International Journal of Computer Theory and Engineering, Vol. 3, No. 4, August 2011

[6] NIST Interagency Report 8114. Report on Lightweight Cryptography. March 2017

[7] D. Engels, X. Fan, G. Gong, H. Hu, and E. M. Smith. Hummingbird: Ultra-Lightweight Cryptography for Resource-Constrained Devices. FC 2010 Workshops, LNCS, vol. 6054, pp. 3-18.

[8] https://www.iso.org/standard/78477.html