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

Hack Proof

Не всегда возможно использовать обычные криптографические алгоритмы в устройствах с крайне ограниченными ресурсами. Примерами таких устройств являются:

RFID-считыватели (англ.: Radio Frequency Identification);
Смарт-карты (включая беспроводные);
Беспроводные сенсоры;
Индикаторы, датчики, контроллеры;
Интернет вещей и др.

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

Размер, необходимый для аппаратной реализации;
Вычислительная мощность микропроцессоров или микроконтроллеров;
Оперативная память (RAM);
Постоянная память (ROM) и т. д.

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

DESL & DESXL

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

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

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

Относительно низкие требования к ресурсам DESL / DESXL — всего лишь результат восьмикратного сокращения требований к ПЗУ для хранения таблиц (поскольку это единственное отличие DESL / DESXL от классических алгоритмов).

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 изменяет внутреннее состояние с помощью следующих операций:

Нелинейный слой γ; состоит из параллельного применения S-блока S () ко всем байтам внутреннего состояния;
Слой перестановки π; меняет местами каждый столбец состояния в соответствии с предопределенным правилом;
Линейный диффузионный слой θ; выполняет умножение состояния на заранее заданную матрицу D;
Ключевой дополнительный слой σ (Kr); выполняет поразрядное сложение r-раундового ключа Kr;
Количество раундов строго не определяется: алгоритм определяет минимальное и максимальное количество раундов для каждой разрешенной длины ключа (от 10 раундов для 96-битного ключа до 23 раундов для 192-битного). Отбеливание на входе выполняется перед первым раундом путем добавления подключа K0. В последнем раунде операция θ не выполняется.

KATAN & KTANTAN

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

Самый маленький шифр из всего семейства, KTANTAN32, может быть реализован в 462 GE, при достижении скорости шифрования 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 загружает блок данных в два внутренних регистра сдвига L1 и L2. Выполняет 254 раунда; каждый из которых использует нелинейные функции, которые формируют обратную связь регистров.

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

Использование регистров сдвига, которые очень легко могут быть реализованы аппаратно; функции обратной связи также очень просты, хотя и обеспечивают необходимую нелинейность;
Обработка небольших блоков данных: от 32 до 64 бит;
Размер внутреннего состояния невелик и его размер равен размеру блока (+ дополнительно LSFR для подсчета раундов);
Key schedule в KTANTAN предельно прост.

PRESENT

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

Добавление раундового ключа операцией XOR;
Использование диффузионного слоя (S-слой);
Использование слоя трансформации смешения (P-слой).

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

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

Hummingbird

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

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

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

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

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

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

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