Легковесная криптография — искусство компромисса. Как в анекдоте, где из трёх вариантов нужно выбрать любые два

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

Национальный институт стандартов и технологий (NIST) подошёл к последнему этапу выбора легковесной криптографии для RFID, датчиков, Интернета вещей и других устройств с ограниченными аппаратными ресурсами.

Кто победит на конкурсе? И не повторится ли история, когда в стандарты ISO попал генератор случайных чисел Dual_EC_DRBG с закладкой от спецслужб? Такой вопрос вполне естественно возникает в криптографическом сообществе, ведь АНБ тоже продвигает свои алгоритмы для легковесной криптографии.

Легковесная криптография

На Хабре несколько раз упоминали о легковесной криптографии. Суть в том, что стандартные алгоритмы шифрования не подходят для работы на устройствах с ограниченными ресурсами, такими как RFID-теги, сенсоры, устройства Интернета вещей и др. До сих пор в этой области не существует общепринятых стандартов.

После совещаний рабочей группы в 2015 и 2016 годах Институт NIST решил провести многоступенчатый конкурс алгоритмов, аналогично конкурсам AES и SHA3. Определили два профиля AEAD (аутентифицированное шифрование со связанными данными): один обычный профиль, а второй для самых ограниченных ресурсов. Возможно, победители по ним будут разные.

В августе 2018-го опубликовали требования безопасности к шифрам AEAD и функциям хеширования: минимум 2¹¹² вычислений для атаки (уникальный nonce), семейство алгоритмов должно включать один основной алгоритм с ключом ≥ 128 бит, nonce ≥ 96 бит и тегом ≥ 64 бит, ограничение на размер входных данных должно быть не менее 2⁵⁰−1 байт, у функции хеширования минимальный размер дайджеста (то есть хеш-суммы) 256 бит.

В феврале 2019-го завершили приём кандидатов: всего на конкурс поступило 56 кандидатов из 25 стран. Из них отобрали 32 семейства для второго раунда (89 AEAD, 19 хеш-функций). Некоторые конкурсанты представили только алгоритмы AEAD, а другие — и AEAD, и функцию хеширования.

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



Распределение кандидатов на конкурсе по режимам шифрования:



Все алгоритмы оценивались по безопасности, производительности в аппаратных и программных системах, а также наличию дополнительных функций. Партнёры провели тестирование «в продакшне» на множестве микроконтроллеров, на архитектурах ARM, AMD, Intel, PPC, RISC V и MIPS.

Для примера, вот пропускная способность всех алгоритмов (Throughput-over-Area, Кбит/с) при шифровании и расшифровке сообщений размером 1536 байт на FPGA с тактовой частотой 75 МГц (Xilinx Antix-7, Intel Cyclone 10 LP, Lattice Semiconductor ECP5).



Далее результаты тестов AEAD на минимальном размере шифруемого текста 16 байт и ассоциированных данных 16 байт на микроконтроллере Atmega328P. На диаграмме приводится соотношение скорости и размера кода.



Это лишь два из множества тестов, которые проводились в самых разных конфигурациях. В следующей таблице показана производительность всех алгоритмов на всех размерах шифруемого текста (по строкам: от 0 до 128 байт) и ассоциированных данных (по колонкам: от 0 до 128 байт). Результат приведён в виде дроби, где в числителе — итоговое время данного алгоритма, а в знаменателе — эталонное время AES-GCM. То есть цифра показывает, насколько данный шифр быстрее или медленнее AES-GCM.



По итогам почти двух лет оценки и тестирования эксперты выбрали десятку финалистов:

• ASCON: файл zip, спецификации, changelog, оф.сайт;
  
• Elephant: файл zip, спецификации, changelog, оф.сайт;
  
• GIFT-COFB: файл zip, спецификации, оф.сайт;
  
• Grain-128AEAD: файл zip, спецификации, changelog, оф.сайт;
  
• ISAP: файл zip, спецификации, changelog, оф.сайт;
  
• PHOTON-Beetle: файл zip, спецификации, оф.сайт;
  
• Romulus: файл zip, спецификации, оф.сайт;
  
• SPARKLE (Алекс Бирюков и др.): файл zip, спецификации, оф.сайт;
  
• TinyJambu: файл zip, спецификации, changelog;
  
• Xoodyak: файл zip, спецификации, оф.сайт.

Подробное описание каждого алгоритма см. в Отчёте по итогам второго раунда конкурса легковесной криптографии NIST (doi: 10.6028/NIST.IR.8369, опубликован в июле 2021 года).

Окончательное подведение итогов состоится на Пятом семинаре по легковесной криптографии, ориентировочно 9–11 мая 2022 года. Примерно летом 2022 года объявят победителей.

Кандидаты от АНБ

Интересно, что ещё перед началом этого конкурса NIST состоялась неудачная попытка АНБ продвинуть свои шифры в качестве стандартов. В частности, спецслужбы предлагали блочные шифры Simon и Speck для устройств интернета вещей на заседании Международной организации по стандартизации (ISO) в апреле 2018 года.

Окончательное голосование состоялось в китайском Ухане, где 16−20 апреля 2018 года проходило 26-е заседание рабочих групп ISO/IEC JTC 1/SC 27 по стандартам безопасности. Эксперты из нескольких стран, включая союзников США, проголосовали отрицательно по предложению американской делегации.

Финальному голосованию предшествовали споры в течение нескольких недель, но АНБ не предоставило необходимых технических подробностей по алгоритмам, обычных для подобных процессов. Как сообщалось, комитет был готов рассмотреть их шифры наравне с любыми другими, но АНБ по сути просто заявило «Верьте нам», на что комитет не согласился.

Прошлые попытки АНБ

Хотя в Simon и Speck не нашли конкретный бэкдор, но ситуация выглядела подозрительно. Вообще говоря, после истории c Dual_EC_DRBG любые предложения АНБ будут выглядеть подозрительно.

В 2013 году из документов Эдварда Сноудена стало точно известно о закладке АНБ в генераторе случайных чисел Dual_EC_DRBG (об уязвимости было известно с 2005 года). Тот алгоритм был сертифицирован институтом NIST и включён в стандарт ISO 18031. Впоследствии он нашёл широкое применение во множестве программных и аппаратных систем, от ОС Windows до продуктов RSA.

Поэтому на рассмотрении шифров Simon и Speck для легковесной криптографии некоторые делегаты выразили общее недоверие АНБ. Например, израильский делегат Орр Дункельман сказал: «Я не доверяю разработчикам. В АНБ довольно много людей, которые думают, что их работа — подрывать стандарты. Моя же работа — защищать стандарты».

Криптографам АНБ должно быть обидно: высококлассные специалисты разработали действительно эффективные шифры, а их отвергают из-за старых обид и подозрительности. Кто-то может сказать, что это карма.

Тем временем шифры Simon и Speck переданы в общественное достояние. Они высоко оцениваются независимыми экспертами за красивый дизайн и высокую производительность (обзор на Хабре). Вопрос о наличии бэкдора остаётся открытым.