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

Возможно, всё не так страшно, но бережёного бог бережёт, поэтому чем раньше начнут внедряться постквантовые системы, тем вероятнее шанс избежать неприятных последствий этого технологического рывка. Сегодня существует несколько подходов к реализации такой защиты. Хотя, пожалуй, самый реалистичный в ближайшем будущем подход будет основываться на криптографии на основе хэшей. Примером такой системы является схема с открытым ключом в виде хэш-дерева Меркла, разработанная ещё в 1979 году и основанная на идеях Лэмпорта и Диффи.

Проблематика безопасности и надёжности современных электронных устройств — очень широка и затрагивает множество различных теоретических и практических аспектов. Однако есть один тонкий и общий для большинства устройств момент, на котором я хотел бы сосредоточить внимание в данной статье — процесс их загрузки. Разные устройства могут быть «заряжены» отлично защищёнными программными компонентами, алгоритмами и протоколами, но никакая система не будет безопасна, если она будет вскрыта до процесса загрузки этого самого защищённого программного обеспечения. Поэтому безопасная загрузка — это один из краеугольных камней электронных систем, ликвидация которого способна привести к фундаментальным проблемам безопасности. Поэтому внедрение постквантовой защиты на этом уровне имеет первостепенное значение.

Процесс загрузки играет важную роль в обеспечении безопасности и надёжности. Первичная исполняемая часть программного обеспечения хранится в постоянной памяти и выполнение загрузочного кода является первым шагом, который гарантирует, что с самого запуска выполняется исключительно надёжное и подлинное программное обеспечение. Важность этой роли в сочетании с практической сложностью обновления требует крайне надёжных решений разработчиков и тщательно проверенного программного обеспечения. Особенно это относится к используемым криптографическим примитивам, но далеко не ограничивается ими. Большинство современных реализаций работают на распространенных асимметричных алгоритмах, таких как RSA или ECC. А как я уже упоминал, эти алгоритмы находятся в зоне риска в связи с развитием квантовых компьютеров.

Для подготовки к нейтрализации этой угрозы в 2016 году Национальным институтом стандартов и технологий США (NIST) был запущен процесс стандартизации квантово-устойчивых криптографических алгоритмов. На определённом этапе NIST выбрал для стандартизации схему подписи на основе хэша без сохранения состояния (hash-based signature, HBS) SPHINCS+. Это единственный выбранный алгоритм, не полагающийся на безопасность криптографии на решётках. Схемы без сохранения состояния можно использовать так же, как и обычные алгоритмы цифровой подписи, основанные на RSA и ECC. Напротив, схемы с отслеживанием состояния требуют от подписавшего отслеживать уже используемые ключи, поскольку на пару ключей может быть сгенерировано лишь ограниченное количество подписей. Любое невыполнение этого требования серьёзно снижает безопасность. Преимуществом схем с отслеживанием состояния, по сравнению со схемами без сохранения состояния, является меньший размер подписи и скорость выполнения.

Для двух схем HBS с отслеживанием состояния, подписи на основе хэширования Лейтона-Микали (Leighton-Micali Hash-Based Signatures, LMS) и схемы расширенной подписи Меркла (eXtended Merkle Signature Scheme, XMSS) доступны RFC IETF (1, 2). На основании этих документов NIST опубликовал рекомендацию по использованию HBS с отслеживанием состояния ещё 2020 году. В 2022 году ANSSI (Agence nationale de la sécurité des systèmes d'information) опубликовал рекомендации по развертыванию HBS, а BSI (British Standards Institution) — по HBS с отслеживанием состояния. Главная особенность таких схем заключается в том, что их надёжность зависит только от свойств базовых хэш-функций.

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

С относительно небольшими расходами возможна быстрая замена аппаратных ускорителей хэширования. В одном из просмотренных мной исследований разработчики интегрировали аппаратный ускоритель в OpenTitan. OpenTitan — контроллер безопасности с открытым исходным кодом, основанный на 32-разрядном процессоре архитектуры RISC-V. Для сравнения был исследован процесс безопасной загрузки OpenTitan с существующими проверками подписи с аппаратным ускорением на базе RSA и ECC.

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

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

Итак, рассмотрим несколько вариантов схем.

Подписи на основе хэша — это схемы цифровой подписи, в которых хэш-функции используются в качестве основного криптографического примитива. То, как и какие из этих криптографических примитивов комбинируются, позволяет построить либо так называемую схему HBS с сохранением состояния, либо без сохранения состояния. Использование алгоритма HBS с отслеживанием состояния отличается для подписывающей стороны по сравнению с обычными асимметричными криптографическими алгоритмами. По сути, количество подписей, которые можно безопасно сгенерировать, ограничено общим количеством доступных пар ключей. Каждая пара ключей может быть использована только один раз, и любое повторное использование приведет к нарушению уровня безопасности. Таким образом, подписывающая сторона должна отслеживать уже используемые пары ключей, эффективно сохраняя состояние и обновляя его после каждой генерации подписи.

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

Одноразовые подписи

Основой современных алгоритмов HBS являются схемы одноразовой подписи (OTS). LMS, XMSS и SPHINCS+ используют вариант Винтерница (Winternitz OTS, WOTS). Основная идея состоит в том, чтобы иметь определённое количество цепочек функций, то есть многократно применять функцию F к предыдущему результату. Для удобства предполагаем, что функция F состоит только из одного вызова криптографической хэш-функции с предыдущим выходом в качестве единственного входа. Таким образом, в дальнейшем просто используем термин хэш-цепочка для этой конкретной конструкции. Принцип работы таких схем ОТС изображен на рисунке.

ачальная точка хэш-цепочки — случайное значение, соответствующее одному секретному ключу OTS (красный). Промежуточным значением хэш-цепочки является синяя подпись OTS. Конечная точка хэш-цепочки — открытый ключ OTS (белый). К этим конечным точкам применяется функция K для генерации сжатого открытого ключа OTS (жёлтый). Для функции сжатия K LMS и SPHINCS+ используют настраиваемую хэш-функцию, а XMSS — так называемое L-дерево. Операции подписи и верификации по своей сути схожи. Чтобы подписать или верифицировать сообщение, его дайджест разбивается на части по log2(w) бит, и каждая часть интерпретируется как значение a. Для подписи «красный» → «синий» и верификации «синий» → «жёлтый» продвигается каждая цепочка хэшей.

Для подписи он продвигается на a, а для верификации на w-1-a. В случае проверки подпись действительна, если открытый ключ-кандидат идентичен открытому ключу. Длина цепочки функций и битовый размер фрагмента определяются параметром Винтерница w и log2(w), соответственно. В примере на рисунке сообщение разделено на фрагменты по 2 бита, что соответствует параметру Винтерница w, равному 4. Метод WOTS был предложен Робертом Винтерницем из Стэнфорда. Он использует относительно небольшие размеры ключей и подписей и считается квантово-устойчивым. В целом он генерирует случайные закрытые ключи размером 32×256 бит. Затем мы получаем их несколько раз, что определяется параметром w.

Многоразовые подписи

В отличие от схемы OTS, схема многоразовой подписи (few-time signature. FTS) позволяет повторно использовать пару ключей несколько раз. Схема FTS используется только в схеме HBS без сохранения состояния SPHINCS+. В результате общая высота дерева SPHINCS+ может быть значительно снижена, что делает его относительно легко применимым на практике. В контексте SPHINCS+ схема леса случайных подмножеств (forest of random subsets, FORS) используется для подписи дайджестов сообщений. FORS состоит из k деревьев Меркла, каждое из которых имеет высоту a. Чтобы сгенерировать открытый ключ FORS, все k корневые узлы дерева Меркла сжимаются. Одно дерево аутентифицирует t = 2a секретных ключа FORS.

Таким образом, листья — это хэши секретных ключей. Для создания подписи дайджест сообщения разбивается на k a-битных фрагментов, как показано на рисунке. Каждый фрагмент интерпретируется как целое число, которое используется в качестве индекса для выбора секретного ключа в качестве узла подписи. Это делается для всех k деревьев и фрагментов. Выбранные узлы объединяются вместе с соответствующими узлами пути аутентификации. Для верификации подписи используется такой же подход, как и при проверке подписи WOTS. Для сравнения одно и то же сообщение подписано в примерах OTS и FORS, изображенных на рисунках 1 и 2 соответственно.

Схема подписи Меркла

В схемах OTS или FTS одна пара ключей может использоваться для подписи один или несколько раз, соответственно. Чтобы преодолеть это ограничение, используется схема подписи Меркла (Merkle signature scheme, MSS), изображенная на рисунке ниже. Она применяет дерево Меркла для аутентификации нескольких открытых ключей OTS. Каждый листовой узел в дереве Меркла соответствует одному хэшированному открытому ключу OTS. Корневой узел дерева соответствует открытому ключу MSS, который используется для аутентификации открытых ключей OTS. Дерево Меркла с высотой h аутентифицирует 2h пар ключей OTS.

Подпись MSS состоит из подписи OTS, описанной выше, и в контексте HBS является в своём роде путём аутентификации. Начиная с нижней части рисунка, открытый ключ OTS вычисляется из подписи. Затем узлы пути аутентификации используются для генерации кандидата открытого ключа для соответствующей подписи. Подпись действительна, если кандидат открытого ключа идентичен известному открытому ключу. С MSS OTS может быть расширен до многократной подписи MTS. Такая конструкция HBS применима к реальным случаям использования, но по-прежнему непрактична для большого количества пар ключей, т. е. требуемых подписей.

Высота дерева h ограничена временем генерации и подписания ключей. Для преодоления этого ограничения вводят обобщённую схему подписи Меркла (generalized Merkle signature scheme, GMSS). Её основная идея заключается в построении так называемого дерева сертификации с несколькими MSS. Вместо того, чтобы иметь одну MSS с большим деревом Меркла, она разделена на d подписей, каждая из которых является меньшим деревом Меркла.

SPHINCS+ 

В отличие от XMSS и LMS, параметры SPHINCS+ описываются определенным набором комбинаций. Доступный список параметров можно разделить на два варианта: «маленький» и «быстрый», которые обозначаются буквами s и f соответственно. «Маленький» вариант обладает низкой скоростью генерации и подписания ключей, однако обеспечивает меньший размер подписи и более быструю проверку, что более актуально для безопасной загрузки. Соответствующий размер подписи и открытого ключа для выбранного набора параметров также указан в таблице. «Простая» и «трудоёмкая» схемы, которые можно использовать в SPHINCS+, влияют только на доказательство безопасности и время выполнения, и не влияют на размер подписи или открытого ключа. Далее они обозначаются как SPX+-s и SPX+-r.

Практическая применимость схем HBS предполагает гибкую совместную разработку аппаратного и программного обеспечения для повышения производительности верификации подписи. Методология проектирования требует разделения алгоритмических операций на три класса: формирование цепи хэшей, путей аутентификации и неклассифицированные операции.

Неклассифицированная часть операций в среднем занимает менее 10%, следовательно, эта часть менее важна для аппаратного ускорения. В то же время вычисление цепочки хэшей отвечает за более чем 80% общей задержки во время проверки. Поэтому это наиболее интересная часть для ускорения. Путь аутентификации занимает до 15% производительности SPHINCS+, что делает его возможной второй целью модификации.

Как правило, хэширование доминирует по времени выполнения алгоритмов HBS. Таким образом, любое ускорение при вычислении хэша оказывает существенное влияние на общую производительность. Аппаратные ядра SHA-2/3 встречаются во многих микроконтроллерах, поскольку часто используются. Использование такого ускорителя смещает узкое место с вычислений на связь с ускорителем. На целевой платформе OpenTitan сжатие SHA-256 занимает 65 тактов, в то время как запись данных и чтение дайджеста увеличивают задержку примерно до 1400 тактов. Для переваривания большого количества данных это не имеет значения, так как передача чередуется с вычислением, а функция сжатия выполняется несколько раз. Однако для одного шага в цепочке хэширования от 55 (LMS) до не более 96 байтов (XMSS) перевариваются одновременно. Поэтому универсальный ускоритель хэширования не идеален для использования в хэш-цепочках.

Ускорение, которое может быть достигнуто с помощью универсальных хэш-ядер, ограничено из-за высоких накладных расходов на связь. Из-за древовидной и цепной структур в схемах HBS доступ к структурам данных осуществляется поэтапно. Выделенные аппаратные компоненты могут управлять этим потоком данных и, следовательно, уменьшать взаимодействие с главным процессором. Поэтому использование аппаратных ускорителей, поддерживающих вычисление хэш-цепочки, корня дерева или и того, и другого вполне целесообразно.

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

Использование комбинации аппаратного и программного обеспечения позволяет уменьшить размер сигнатуры, не влияя на производительность. Например, можно выбрать параметр Винтерница w = 256 вместо w = 16, чтобы сократить размер подписи OTS вдвое без значительного снижения производительности. На рисунке ниже показана схема ядра.

Исходный ускоритель OpenTitan SHA-256 состоит из бэкенда SHA-256, к которому можно получить доступ либо прозрачно, либо через верхний уровень HMAC для вычисления SHA-256 или MAC, соответственно. Повторно используя логику SHA-256, можно минимизировать дополнительные затраты на производство. Во время синтеза в конструкцию может быть включен один из шести модулей HBS: LMS, XMSS, SPX+-s, SPX+-r, (SPX+-s + LMS), (SPX+-r + XMSS). Теоретически, эти модули могут быть приспособлены для любых хэш-ядер с небольшими изменениями.

В этой схеме изменения в исходном хэш-ускорителе включают цепной регистр, который подключен к регистру начального состояния SHA-256, дополнительную логику управления для переключения между режимами работы и путь обратной связи в модуль HBS. Ядра HBS реализуют соответствующее поведение с помощью простых автоматов состояний. Этот дизайн может быть напрямую интегрирован в любой чип, поддерживающий интерфейс TileLink Uncached Lightweight (TL-UL).

Сегодня исследования по внедрению постквантовых алгоритмов активно продолжаются, но уже сейчас можно сказать, что такой переход с использованием схем HBS вполне осуществим. Гибкая конфигурация аппаратного и программного обеспечения для поддержки как схем с сохранением состояния, так и схем без сохранения состояния позволяет снизить накладные расходы на оборудование. При этом дискуссия о выборе между HBS без сохранения состояния и с сохранением состояния безразлична к базовому оборудованию и конкретные реализации зависят только от особенностей конкретных устройств. Например, чисто программные реализации по большей части не подходят для встраиваемых устройств, в то же время аппаратная реализация всегда дороже, с точки зрения накладных расходов и затрат, к тому же применимость чисто аппаратных реализаций в IoT-устройствах вряд ли осуществима в полном объёме. Учитывая, что IoT-устройства в данном контексте как раз и будут тем самым «больным человеком Европы». Поэтому комбинированный подход на данном этапе более предпочтителен.

Проблема перехода на постквантовые алгоритмы затронула и российское общество. В России создана отдельная рабочая группа по постквантовым механизмам Технического комитета по стандартизации «Криптографическая защита информации» (ТК26). Непонятно, насколько работа группы эффективна, учитывая особенности национальной разработки в санкционный период, однако какие-то наработки всё же есть, например, вот эта работа.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.