Прикладная криптография для Arduino: шифр Speck, сравнение с шифром “Магма”

В криптографической библиотеке для Arduino используется российский шифр “Магма” (ГОСТ 34.12-2015). Я сравнил свою реализацию “Магмы” из библиотеки с другим “малым” шифром – Speck, который был предложен в 2013 году специалистами АНБ. Чтобы сравнение было точнее, я также реализовал Speck, использовав inline-ассемблер (ссылка на исходный код – в конце записки).

Прежде всего – краткое описание шифра Speck. Это новый блочный шифр, специально разработанный для программной реализации в микроконтроллерах, то есть, вычислителях с сильно ограниченными ресурсами. Как и многие другие современные шифры (а также и “Магма”), Speck построен на базе простой “раундовой” функции, которая последовательно вызывается с разными ключами, проводя преобразование блока данных. В Speck эта же функция используется для разворачивания основного ключа в последовательность ключей раундов. Это первое существенное отличие от “Магмы”, в котором разворачивание ключа сводится к копированию (см. описание “Магмы”). Спецификация Speck вводит несколько вариантов шифра, имеющих разную разрядность блока и ключа. Я использовал наиболее близкий к “Магме” вариант: 64-битный блок и 128-битный ключ (256-битного, по ключу, варианта Speck для 64-битного блока – нет, поэтому сравнить шифры на одной длине ключа нельзя). От варианта к варианту в Speck различаются количество раундов и часть параметров раундовой функции (разрядность логических сдвигов).

На картинке ниже – подробная схема раунда Speck (шифрование).

Входной блок разбивается на две части. Это, опять же, одно из распространённых и хорошо проверенных решений в схемах шифров. Левая часть (A1 на схеме) циклически сдвигается вправо на 8 разрядов, суммируется с правой частью (A0) по модулю 232 (то есть, как два 32-разрядных числа “естественным образом”, без переноса и знака; операция обозначена символом ⊞). На следующем шаге выполняется сложение по модулю 2 (XOR, ⊕) с раундовым ключом. После чего результат обработки полублока суммируется (опять же, XOR) со вторым полублоком, который перед этим циклически сдвигается на три разряда влево.

В шифре “Магма” используется схема Фейстеля, в которой полублоки, после применения раундовых преобразований, переставляются. Раунд шифра Speck также можно привести к схеме Фейстеля, разделив на два этапа. Первый этап включает преобразования левой части, за которыми следует перестановка полублоков. Схема:

Второй этап – состоит в применении сдвига и XOR к результату первого этапа. Схема:

То есть, с некоторой долей условности можно сказать, что Speck построен из двух, применяемых последовательно, конструкций Фейстеля.

Раунды выполняются циклически. Для используемого варианта шифра число повторений равняется 27. Таким образом, требуется 27 раундовых ключей, каждый разрядностью 32 бита. Схема их получения из исходного, 128-битного, ключа состоит в последовательном применении той же раундовой функции к ключу, предварительно разбитому на слова, разрядность которых совпадает с разрядностью полублока. То есть, 128-битный ключ (16 байтов) даёт нам четыре слова по 32 бита. Эти слова служат левым и правым полублоком в раундовой функции. Ключом (Ki на схеме) при этом является номер раунда. Другими словами: первый раундовый ключ – это младшие 32 бита исходного, основного ключа (используются прямо). Второй раундовый ключ – младшие 32-бита результата применения раундовой функции к младшим 64 битам основного ключа (очевидно, что сюда, в качестве правого полублока, входит первый раундовый ключ); и так далее, подробнее можно посмотреть в исходном коде.

Переходим к сравнению шифров. Ассемблерная реализация позволяет посчитать примерное число тактов, необходимых для выполнения преобразований шифра. Для Speck подсчёт дал 1951 такт – столько занимает полная реализация, с обращением к памяти, где хранятся раундовые ключи и блок открытого текста, с выгрузкой результата. Сюда не входит код получения последовательности раундовых ключей (развёртывания ключа). 1951 такт, в пересчёте на байт данных (блок состоит из 8 байтов), даёт: 1951/8 = 244 такта на байт (приблизительно). В исходной работе, со спецификацией Speck, авторы приводят результат от 118 до 160 тактов для аналогичного 8-разрядного микроконтроллера, но здесь не учитываются операции по загрузке/выгрузке блоков, так что результаты довольно близки (кроме того, мой вариант можно оптимизировать).

Реализация “Магмы” из библиотеки для Arduino показывает следующие результаты: 9092 такта полный код, соответственно, 1136 (приблизительно) тактов на байт (отмечу, что показатели близки к реализациям AES). Существенный вклад в это число вносит реализация подстановок, где много обращений к памяти с достаточно сложными преобразованиями указателей. Этот код можно оптимизировать, вплоть до того, что сами подстановки разместить в регистрах (для 16 полубайтовых подстановок, закрывающих одну позицию во входном полублоке, достаточно восьми байтовых регистров; однако вся таблица подстановок в регистрах типичного микроконтроллера вряд ли поместится – для неё нужно 64 регистра). Правда, вычисление номера регистра и обращение к нему потребует дополнительных усилий, объём кода заметно возрастёт, а для “Магмы” он и так не маленький. Тем не менее, вряд ли выигрыш по тактам составит более двух раз. Из-за подстановок – “Магма” медленнее, чем Speck, тут ничего нельзя поделать.

Другим параметром, по которому можно сравнить шифры, является объём требуемой памяти данных. Для Speck нужно 108 байтов для раундовых ключей. Реализация “Магмы” требует 128 байтов (здесь больше раундов – 32). При этом, если требуется экономия памяти, “Магма” позволяет прямо использовать в качестве раундовых ключей слова из состава основного ключа. Со Speck такой фокус не пройдёт, потому что здесь сложная функция разворачивания ключа. Однако оптимизация всё равно возможна: раундовые ключи можно вычислять в процессе выполнения раундов шифра. Впрочем, такой вариант приведёт к тому, что минимум в два раза возрастёт число тактов, поэтому Speck приблизится к “Магме”. Для хранения таблицы подстановок “Магма” требует ещё 8*8=64 байта.

Реализация “Магмы” существенно превышает показатели Speck по объёму кода. И тот, и другой шифр вполне укладываются в разумные рамки, но код шифра Speck – очень компактный. Побайтового сравнения объёмов я не привожу.

Итак, “Магма” уступает Speck по показателям, относящимся к программной реализации. Неудивительно: “Магма” очень старый шифр, разработанный ещё в 70-х годах прошлого века. Как ни странно, в этом состоит его преимущество, если говорить об оценках стойкости. Этот шифр до сих пор входит в рекомендации ГОСТ и для него пока не опубликовано криптоанализа, существенно снижающего стойкость, хотя сломать шифр пытались многократно. Speck – новый шифр, выполненный в современных традициях, задуманный специально для микроконтроллеров, этим обусловлены его преимущества. Для данного шифра также пока не опубликовано криптоанализа, существенно снижающего стойкость (известные работы – предлагают академические атаки, не пригодные для практических сценариев), но нужно учитывать малое распространение и новизну шифра. Отмечу также, что Speck далеко не единственный новый шифр, ориентированный на “Интернет вещей”, однако является одним из самых простых, быстрых и компактных. Тем не менее, преимущество в скорости и возможность экономии нескольких десятков байтов – не всегда являются решающими факторами, в том числе, для устройств с малой вычислительной мощностью. Например, в случае передачи раз в час команд от устройства к устройству, разница в несколько миллисекунд, требующихся для получения криптограммы, не играет роли. (С другой стороны, каждый такт – это расход энергии элемента питания, что может оказаться существенным для устройств с экстремально низким энергопотреблением.)

В ГОСТ на средства криптографической защиты информации уже есть весьма современный шифр “Кузнечик”, сходный с AES. Однако и “Кузнечик”, и AES – не очень хорошо подходят для микроконтроллеров, так как быстрая реализация этих шифров требует довольно большого объёма памяти, который доступен далеко не для всех платформ, кроме того, часто требуются короткие криптограммы (64 бита). Вполне возможно, что в обозримом будущем в стандартах появится новый российский шифр, ориентированный именно на маломощные вычислители.

Приложение: исходный код реализации Speck для Arduino (только зашифрование), также содержит дополнительные функции для шифрования тестового вектора и проверки правильности работы.

Адрес записки: https://dxdt.ru/2017/03/06/8289/

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Комментарии читателей блога: 2

  • 1. 7th March 2017, 01:31 // Читатель Z.T. написал:

    А как насчет ChaCha (+ poly1305) с пониженным количеством раундов? Или NORX? Думаю будет компактный код, но я ~ничего не знаю про Atmel AVR.

  • 2. 7th March 2017, 12:42 // Александр Венедюхин:

    > А как насчет ChaCha (+ poly1305) с пониженным количеством раундов? Или NORX?

    Нужно будет проверить, но выглядит так, что они будут потреблять заметно больше тактов (особенно NORX, который, как я понимаю, ориентирован на 64-битные процессоры и требует дополнительную память для работы). Восьмибитная природа AVR-ов – гарантирует большой прирост в операциях, так как даже простейшие операции над 32-битным значением требуют по 4-7 тактов (байты размещаются отдельно по регистрам и пр.); обращения к памяти – обычно, по два такта на байт, да ещё 4-6 тактов для каждой последовательности уходит на преобразование регистров-указателей.

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