Приветствую, Хабр! В моей предыдущей статье были описаны принятые в прошлом году стандарты США FIPS (Federal Information Processing Standard — Федеральный стандарт обработки информации — аналог стандартов ГОСТ Р в России) на постквантовые алгоритмы электронной подписи (FIPS 204 и FIPS 205) и инкапсуляции ключей (FIPS 203). Данные криптостандарты были приняты в результате тщательного анализа и отбора алгоритмов в рамках открытого конкурса, проводимого Институтом стандартов и технологий США NIST; данный конкурс также был описан в предыдущей статье.
Стандарты FIPS 203 [1] и FIPS 204 [2] описывают алгоритмы, основанные на применении структурированных алгебраических решеток, тогда как алгоритм, стандартизованный в FIPS 205 [3], базируется на стойкости нижележащих хеш‑функций; данный алгоритм называется Stateless Hash‑Based Digital Signature Algorithm (SLH‑DSA) — алгоритм электронной подписи на основе хеширования без сохранения состояния. Стоит сказать, что данные алгоритмы стали не первыми постквантовыми криптоалгоритмами, стандартизованными в США, — еще в 2020 году в США был издана «специальная публикация» (SP — Special Publication — аналог рекомендаций по стандартизации в России) NIST SP 800–208 [4], описывающая несколько алгоритмов электронной подписи с сохранением состояния, также основанных на хеш‑функциях.
Далее в статье — описание и схемы алгоритмов, описанных в NIST SP 800-208, а также небольшой анализ особенностей алгоритмов данного класса.
NIST SP 800–208 дополняет текущий стандарт на традиционные (не обладающие стойкостью к квантовому криптоанализу) алгоритмы электронной подписи (ЭП) FIPS 186 [5] несколькими постквантовыми алгоритмами, а именно:
LMS — Leighton‑Micali Signature (подпись Лейтона‑Микали);
XMSS — Extended Merkle Signature Scheme (расширенная схема подписи Меркля);
HSS — Hierarchical Signature System (иерархическая схема подписи);
XMSSMT — Multi‑tree Extended Merkle Signature Scheme (расширенная схема подписи Меркля на основе гипердерева).
Все эти алгоритмы, как было сказано выше, основаны на хеш‑функциях с сохранением состояния и обладают стойкостью к квантовым атакам. Алгоритмы LMS и XMSS концептуально похожи друг на друга тем, что они используют схожие внутренние преобразования:
схему одноразовой электронной подписи (под «одноразовой» подразумевается электронная подпись, в которой каждый секретный ключ может быть использован для подписания только один раз);
метод создания единого долговременного открытого ключа алгоритма из совокупности открытых ключей одноразовой ЭП.
Данные алгоритмы для вычисления открытого ключа используют одиночные деревья Меркля, что подробно описано далее, тогда как алгоритмы HSS и XMSSMT представляют собой варианты, соответственно, алгоритмов LMS и XMSS, основанные на гипердеревьях.
Рассмотрим вышеперечисленные алгоритмы далее.
Дисклеймер: приведенные далее описания процедур рассматриваемых алгоритмов значительно упрощены по сравнению с оригинальными описаниями, которые значительно более масштабны и не могут быть переданы в формате статьи на Хабре; их можно найти в документе [4] и соответствующих публикациях, ссылки на которые приведены далее. При этом упрощенные описания позволяют, на мой взгляд, передать основную суть преобразований; сокращения коснулись, в основном, конвертаций между различными представлениями данных и избыточных для цели данной статьи подробностей.
Алгоритм электронной подписи XMSS и его вариант XMSSMT
Концепция схем электронной подписи, используемая в XMSS, изначально была предложена Ральфом Мерклем еще в 1979 г. в работе [6]. Текущая версия XMSS была описана в 2011 г. в работе [7]; однако документ NIST SP 800-208 ссылается на более поздний вариант XMSS, описанный в [8] (2018 г.).
Криптостойкость XMSS основывается на стойкости нижележащих хеш-функций, в качестве которых в стандартных вариантах XMSS применяются различные варианты стандартных алгоритмов хеширования SHA-256 [9] и SHAKE256 [10].
Помимо хеш-функций, в качестве основного «строительного блока» XMSS использует модифицированную одноразовую электронную подпись Винтерница WOTS+ (Winternitz One Time Signature Plus) [11]; связка XMSS и WOTS+ также используется в алгоритме SLH-DSA из стандарта FIPS 205, рассмотренном в предыдущей статье.
Схема одноразовой электронной подписи WOTS+
Основным компонентом алгоритма WOTS+ является функция chain, которая формирует цепочку хеш-кодов с помощью нижележащей функции хеширования. Данная функция используется во всех процедурах алгоритма, включая генерацию ключей и вычисление/проверку ЭП.
Функция chain обрабатывает следующие входные параметры:
X – входное n-байтное значение (n – глобальный параметр алгоритмов XMSS/XMSSMT, определяющий размерность основных данных алгоритма и уровень его криптостойкости; в стандартных вариантах алгоритмов XMSS и XMSSMT n принимает значения 24 или 32);
i – стартовый индекс цепочки хешей;
s – количество итераций;
adrs – адрес входных данных (адрес в алгоритме XMSS представляет собой 32-байтную структуру, состоящую из набора полей, однозначно идентифицирующих местонахождение конкретного фрагмента данных в общей структуре данных алгоритма, а также содержащую некоторые дополнительные данные);
seed – псевдослучайное значение.
Данная функция циклически (до выполнения требуемого количества итераций) производит следующие действия (упрощенная схема приведена на рисунке):
Обновляет адрес adrs для текущего обрабатываемого фрагмента данных (в числе прочего, адрес зависит от номера итерации).
С помощью псевдослучайной функции prf на основе текущих значений seed и adrs вычисляет ключ хеширования key (данный ключ является одноразовым и уникальным для каждой итерации).
С помощью функции prf, также на основе текущих значений seed и adrs, вычисляет одноразовую битовую маску bm, которая будет накладываться на данные.
Вычисляет значение функции хеширования H на основе входного значения X или результата вычисления хеш-кода на предыдущей итерации (обозначим его как tmp) с помощью ключа и битовой маски:
tmp = H(key, tmp ⊕︀ bm).
Возвращаемым n-байтным значением функции chain (обозначим его Y) является результат хеширования на последней итерации.
В качестве функций H и prf в стандартных вариантах алгоритма используется одна и та же нижележащая функция хеширования, аргументы которой конкатенируются при их хешировании. В зависимости от конкретного набора параметров могут применяться хеш-функции SHA-256 или SHAKE256, а также их варианты с выходным значением, усеченным до 192 бит.
В случае нулевого количества итераций s функция chain возвращает входное значение X неизменным. Сумма значений i + s должна быть меньше максимального количества элементов данных (включая X и Y) в цепочке, которое обозначается как w и является параметром алгоритмов XMSS/XMSSMT (стандартное значение w = 16).
Секретный ключ sk алгоритма WOTS+ представляет собой массив из len (параметр алгоритмов XMSS/XMSSMT, вычисляемый на основе параметров n и w; в стандартных вариантах len равно 51 или 67) n-байтных значений, которые генерируются случайным или псевдослучайным образом (в стандартном варианте алгоритма фрагменты секретного ключа генерируются псевдослучайным образом из исходного секретного n-байтного значения – см. далее). Каждое значение sk должно быть использовано строго однократно.
Открытый ключ pk алгоритма WOTS+ представляет собой аналогичный массив, каждый элемент которого pk[i], i = 0, …, len-1, вычисляется из соответствующего ему элемента секретного ключа sk[i] путем применения функции chain для вычисления цепочки хеш-кодов с максимальным количеством итераций, которое равно w-1.
Электронная подпись WOTS+ sgn также состоит из len n-байтных фрагментов. Для ее вычисления выполняется следующая последовательность действий:
Хеш-код подписываемого сообщения M’ (здесь и далее исходное сообщение будем обозначать как M, а его хеш-код – как M’) разбивается на len фрагментов, каждый из которых содержит значения от 0 до w-1.
Каждый такой фрагмент M’[i], i = 0, …, len-1, определяет количество итераций для i-й цепочки хеш-кодов.
Каждый фрагмент секретного ключа sk[i], i = 0, …, len-1, обрабатывается функцией chain с количеством итераций M’[i], таким образом строится len цепочек хеширования (в общем случае – более коротких по сравнению с цепочками, которые строятся при генерации ключей).
Электронная подпись sgn составляется из фрагментов sgn[i], i = 0, …, len-1, каждый из которых определяется как выходное значение функции chain, т. е. как фрагмент данных, завершающий соответствующую (i-ю) цепочку хеш-кодов.
Таким образом, фрагменты ЭП представляют собой значения, входящие в определенных местах в полноразмерные цепочки хеш-кодов, построенные между фрагментами секретного и открытого ключей. Данный факт используется при проверке подписи, которая производится следующим образом:
Хеш-код M’ сообщения M, подпись которого проверяется, разбивается на len фрагментов, каждый из которых содержит значения от 0 до w-1.
По каждому такому фрагменту M’[i], i = 0, …, len-1, можно определить количество итераций для i-й цепочки хеш-кодов, необходимых для «достраивания» цепочки до максимальной длины, как w-1-M’[i].
Каждый фрагмент ЭП sgn[i], i = 0, …, len-1, обрабатывается функцией chain с количеством итераций w-1-M’[i], таким образом из фрагментов подписи достраиваются len цепочек хеширования.
В результате такого достраивания в конце каждой цепочки должен получиться фрагмент открытого ключа pk[i], i = 0, …, len-1; электронная подпись признается верной, если все фрагменты в конце достроенных цепочек идентичны соответствующим фрагментам открытого ключа pk, с помощью которого проверяется ЭП, и должна считаться неверной в случае, если хотя бы один из фрагментов не совпадает (вместо сравнения напрямую может использоваться сравнение результатов обработки pk, например, результатов их хеширования с помощью деревьев Меркля, как будет показано далее).
Необходимо отметить, что при проверке подписи необходимо использовать то же самое значение seed, которое использовалось при ее вычислении; следовательно, данное значение должно передаваться вместе с подписью. Аналогичное требование предъявляется к значениям adrs, но за их корректное использование отвечает алгоритм верхнего уровня (вданном случае — XMSS).
Алгоритм XMSS
Управление описанными выше сущностями алгоритма WOTS+ осуществляется со стороны алгоритма XMSS. Применяемые данным алгоритмом механизмы позволяют использовать каждый секретный ключ XMSS многократно (но с ограниченным количеством применений), несмотря на то, что в основе XMSS лежит алгоритм однократной подписи.
XMSS использует структуру данных в виде дерева Меркля, упрощенная схема построения которого описана далее. Максимально допустимое количество подписей на каждом секретном ключе XMSS определяется высотой дерева: дерево высоты h (не считая верхний или нижний уровень) позволяет подписать 2h сообщений. h — параметр алгоритмов XMSS/XMSSMT, в стандартных вариантах XMSS принимает значения 10, 16 или 20, в стандартных вариантах XMSSMT — значения 20, 40 или 60.
Каждый лист дерева содержит n-байтное значение, представляющее собой сжатый (алгоритм сжатия описан далее) открытый ключ уникальной одноразовой ключевой пары алгоритма WOTS+. Обозначим такой ключ как pkcj, а соответствующий ему (не подлежащий сжатию) секретный ключ WOTS+ – skj, j = 0, …, 2h-1 (ключевые пары WOTS+ имеют сквозную нумерацию во избежание повторного использования секретных ключей). Промежуточные узлы дерева содержат n-байтные значения, полученные путем хеширования определенным образом (см. далее) двух дочерних узлов или листьев, а корневой (верхний) элемент дерева в результате его построения содержит открытый ключ PK алгоритма XMSS.
Формирование промежуточного или корневого узла дерева осуществляется следующим образом:
На основе адреса формируемого узла и значения seed с помощью функции prf вычисляются значения трех переменных: ключа хеширования key и битовых масок bm0 и bm1.
Вычисляется значение узла (up) на основе значений дочерних узлов (left и right) и полученных на предыдущем шаге переменных:
up = H(key, (left ⊕︀ bm0) || (right ⊕︀ bm1)).
Сжатие открытого ключа pk алгоритма WOTS+ (размером n * len байт) в n-байтный ключ pkc выполняется аналогичным образом с тем исключением, что дерево может быть несбалансированным, поскольку значение len в общем случае не является степенью числа 2. Каждое значение pkcj, j = 0, …, 2h-1, вычисляется с помощью отдельного дерева.
В этом случае листья каждого из таких 2hдеревьев содержат n-байтные фрагменты pkj[i], i = 0, …, len-1, сжимаемого ключа pkj, а вычисления промежуточных или корневых узлов выполняются так же, как и для описанного выше дерева. В результате получается корневой элемент дерева, представляющий собой сжатый открытый ключ pkcj алгоритма WOTS+.
Генерация пары ключей алгоритма XMSS выполняется следующим образом:
Производится генерация 2h одноразовых секретных ключей алгоритма WOTS+, каждый из которых состоит из len фрагментов по n байт, сгенерированных случайным образом. В документе NIST SP 800-208 указывается с целью уменьшения размера секретного ключа XMSS не генерировать все фрагменты ключей случайно, а использовать вместо этого псевдослучайную функцию, выполняющую генерацию данных фрагментов на основе исходного случайного значения размера n байт (обозначим его SK_init), полученного с помощью качественного генератора случайных чисел.
Генерируются случайные n-байтные значения sk_prf (секретное) и seed (открытое), которые впоследствии используются для генерации псевдослучайных значений, в т. ч. в рассмотренном выше процессе хеширования.
Путем описанных выше действий, включающих формирование цепочек хеш-кодов для получения 2h открытых ключей WOTS+ (на основе секретных ключей WOTS+), их сжатие и вычисление корневого элемента дерева открытых ключей, получается значение открытого ключа PK.
Формируются описанные далее структуры секретного и открытого ключей.
Структура секретного ключа алгоритма XMSS содержит следующие данные:
индекс следующего используемого ключа WOTS+ idx, изначально равен нулю;
значения всех секретных ключей WOTS+ (не рекомендуется, но возможно) или исходное случайное число для их генерации (такой вариант рекомендуется в [8] и является обязательным согласно [4]);
значение sk_prf;
значение открытого ключа PK;
значение seed.
Концепция применения одноразовых ЭП предполагает, что в идеале секретный ключ не покидает криптографическое устройство, в котором он был сгенерирован, поэтому данная структура является условным понятием. Считается, что в противном случае невозможно гарантированно обеспечить однократное применение секретных ключей WOTS+.
Структура открытого ключа алгоритма XMSS содержит следующие данные:
идентификатор алгоритма и набора параметров OID;
значение открытого ключа PK;
значение seed.
Вычисление электронной подписи алгоритмом XMSS производится с помощью следующей последовательности действий:
Инкрементируется текущее значение индекса idx в структуре секретного ключа XMSS (данная операция выполняется намеренно до фактического использования одноразового секретного ключа WOTS+, а не после него, поскольку в последнем случае при, например, сбое записи инкрементированного индекса можно ошибочно использовать ключ повторно); в дальнейших вычислениях ЭП используется значение idx до инкрементирования.
На основе значения sk_prf генерируется n-байтное псевдослучайное значение r, которое рандомизирует результат вычисления ЭП.
Подписываемое сообщение M хешируется с получением хеш-кода M’ с использованием в качестве ключа хеширования конкатенации следующих данных:
· значения r;
· значения PK из структуры секретного ключа XMSS;
· значения idx.Для используемого листа дерева вычисления открытого ключа XMSS, определяемого значением idx, формируется путь аутентификации auth_path – набор значений листьев и узлов дерева, необходимых для его достраивания при наличии значения листа с номером idx.
Вычисляется электронная подпись sgn алгоритма WOTS+ (как было описано ранее) на основе следующих значений:
· секретного ключа sk = skidx алгоритма WOTS+;
· хеш-кода M’;
· значения seed из структуры секретного ключа XMSS;
· адреса текущего узла.
Структура ЭП алгоритма XMSS состоит из следующих данных:
индекса idx (до инкрементирования);
случайного значения r;
подписи sgn;
пути аутентификации auth_path.
Совокупный размер полей данной структуры определяется параметрами алгоритма XMSS и составляет 4 + n(1 +len + h) байт.
Проверка подписи сообщения M подразумевает выполнение следующей последовательности действий:
Аналогично процессу подписания, вычисляется хеш-код M’ на основе сообщения M и значений r, idx и PK, извлеченных из структуры ЭП (r и idx) и из структуры открытого ключа (PK).
С использованием адреса текущего узла, значения seed, извлеченного из структуры открытого ключа, и хеш-кода сообщения M’ на основе подписи sgn алгоритма WOTS+ вычисляется открытый ключ WOTS+ pk = pkidx, как было показано ранее.
Выполняется восстановление требуемой (верхней относительно листа с требуемым индексом и пути аутентификации) части дерева XMSS с помощью следующих данных:
· открытого ключа pk, его адреса в дереве XMSS, получаемого с помощью индекса idx;
· пути аутентификации auth_path, извлеченного из структуры ЭП;
· значения seed, извлеченного из структуры открытого ключа.Корневое значение построенного дерева сравнивается со значением PK из структуры открытого ключа XMSS. Если данные значения идентичны, то подпись верна, в противном случае подпись является неверной.
Таким образом, проверка ЭП состоит в воссоздании дерева XMSS и сравнении полученного варианта открытого ключа (корневого элемента построенного дерева) с имеющимся открытым ключом пользователя, чья подпись проверяется.
В документе [4] перечислено достаточно большое количество стандартных вариантов алгоритма и соответствующих им параметров; это же касается и рассмотренных далее алгоритмов XMSSMT, LMS и HSS. Я не буду дублировать таблицы вариантов и параметров алгоритмов в данной статье, их можно найти в первоисточнике [4]; типовые значения параметров для стандартных вариантов алгоритмов я привожу в их описании.
Основные особенности алгоритма XMSSMT
Как было сказано выше, алгоритм XMSSMT представляет собой вариант алгоритма XMSS, использующий гипердерево вместо единичного дерева. Гипердерево представляет собой многоуровневую иерархическую структуру деревьев; пример такой структуры приведен на рисунке для двух уровней.
Нижний уровень дерева, находящегося на более верхнем уровне, состоит из листьев, используемых для подписания алгоритмом WOTS+ корневых элементов нижележащих деревьев. Для подписания тем же алгоритмом непосредственно сообщений используются листья деревьев, находящихся на самом нижнем уровне.
В алгоритме XMSSMT параметр h трактуется как общая высота гипердерева (не считая уровней листьев), кроме него используется еще один параметр d, обозначающий количество уровней деревьев в гипердереве, тогда высота одного дерева определяется как h/d (все деревья гипердерева имеют одинаковую высоту). Значения параметра d в стандартных вариантах XMSSMT: 2, 3, 4, 6, 8 или 12 в зависимости от конкретного варианта алгоритма.
Структура гипердерева позволяет безопасно распределить генерацию ключей и их использование для подписания между несколькими криптографическими устройствами следующим образом на примере двухуровневого гипердерева:
каждое из устройств генерирует секретные ключи WOTS+ по количеству листьев дерева нижнего уровня (с соблюдением их сквозной нумерации), вычисляет соответствующие им открытые ключи и формирует свое дерево нижнего уровня (деревья нижнего уровня также нумеруются), получая в результате открытый ключ данного дерева — его корневой элемент;
еще одно криптографическое устройство (назовем его «центральным») генерирует дерево верхнего уровня, листья которого также соответствуют ключам WOTS+ (но они не включаются в сквозную нумерацию, а нумеруются отдельно), а корневой элемент является открытым ключом данного дерева; этот же ключ является открытым ключом сгенерированной таким образом ключевой пары в целом;
каждый открытый ключ дерева нижнего уровня подписывается соответствующим ему по номеру секретным ключом WOTS+ дерева верхнего уровня; центральное устройство после этого не используется при условии сохранения где-либо (с контролем целостности) всех подписей открытых ключей деревьев нижнего уровня.
Таким образом, каждое из криптографических устройств (кроме центрального) имеет набор секретных ключей WOTS+, который может использовать для подписания сообщений; секретные ключи при этом не покидают данное устройство. Подобная структура позволяет сохранить работоспособность ключевой пары в случае выхода из строя одного или части устройств, а также может быть полезна при балансировке нагрузки.
Недостатком же данной схемы является увеличенный размер ЭП и повышение ресурсоемкости процедуры проверки подписи по сравнению с алгоритмом XMSS. Помимо подписи самого сообщения и значений idx и r, ЭП алгоритма XMSSMT также должна включать в себя подпись открытого ключа дерева нижнего уровня (в общем случае — еще и подписи открытых ключей для деревьев всех промежуточных уровней, если уровней больше двух). При проверке ЭП сравнение существующего и вычисленного из подписи открытого ключа производится только на верхнем уровне гипердерева.
Я не привожу в данной статье подробное описание процедур алгоритма XMSSMT — они во многом аналогичны описанным выше процедурам генерации ключей, подписания и проверки ЭП алгоритма XMSS, но учитывают использование гипердерева вместо одиночного дерева, а также описанные выше изменения в структуре ЭП алгоритма XMSSMT.
Алгоритмы электронной подписи LMS и HSS
Алгоритмы LMS и HSS представляют собой альтернативу рассмотренным выше алгоритмам — соответственно, алгоритму XMSS и алгоритму XMSSMT. LMS основан на использовании одиночных деревьев, тогда как HSS использует гипердеревья. Оба алгоритма описаны в документе [12].
Данные алгоритмы основаны на использовании схемы одноразовой электронной подписи LM-OTS (Leighton-Micali One-Time Signature — одноразовая подпись Лейтона-Микали).
Основные отличия схемы LM-OTS от WOTS+
Схема LM-OTS, как и рассмотренная ранее схема WOTS+, является одним из вариантов одноразовой электронной подписи Винтерница.
Следовательно, данные схемы являются концептуально похожими друг на друга; перечислим те черты алгоритма LM-OTS, которые схожи с таковыми в алгоритме WOTS+:
секретные ключи данных алгоритмов генерируются случайным образом или псевдослучайно из исходного случайного числа (с целью уменьшения размера хранимых секретных данных; последний вариант является предпочтительным);
каждая пара ключей имеет уникальный номер q; максимальное количество ключей устанавливается алгоритмом верхнего уровня;
каждый секретный ключ skq разбивается на n-байтные фрагменты skq[i]; в LM-OTS количество фрагментов определяется параметром p, т. е. i = 0, …, p-1; в стандартных вариантах алгоритма p принимает различные значения от 26 до 265 в зависимости от конкретного варианта; n также является параметром алгоритма, в стандартных вариантах n равно 24 или 32;
каждый секретный ключ должен использоваться строго однократно, за однократное использование отвечает алгоритм верхнего уровня; несоблюдение этого требования может привести к возможности подделки злоумышленником подписи произвольных сообщений;
каждый открытый ключ pkq также представляет собой совокупность фрагментов pkq[i], i = 0, …, p-1;
фрагменты открытого ключа вычисляются из фрагментов секретного ключа путем построения цепочек хеш-кодов; в LM-OTS максимальное количество итераций в цепочке определяется параметром w как 2w-1; в стандартных вариантах w равно 1, 2, 4 или 8;
для хеширования в стандартизованных вариантах LM-OTS также применяются определенные варианты алгоритмов хеширования SHA-256 и SHAKE256;
хеш-код M’ подписываемого сообщения разбивается на p фрагментов (но в LM-OTS — по w бит, т. е. каждый фрагмент имеет значение из диапазона от 0 до 2w-1 включительно);
фрагмент подписи sgn[i], i = 0, …, p-1, определяется путем частичного построения цепочки хеш-кодов из соответствующего фрагмента секретного ключа, где число итераций определяется значением фрагмента хеш-кода M’: M’[i], i = 0, …, p-1;
для проверки подписи выполняется достраивание цепочек: каждый фрагмент подписи sgn[i], i = 0, …, p-1, многократно хешируется; в LM-OTS количество итераций хеширования определяется фрагментом хеш-кода M’[i] сообщения, подпись которого проверяется, как 2w-1-M’[i], i = 0, …, p-1;
если собранный из результирующих фрагментов достроенных цепочек открытый ключ полностью идентичен открытому ключу pkq, который используется для проверки подписи, то подпись признается верной, в противном случае подпись неверна.
Опишем также основные отличия между данными алгоритмами; в LM-OTS:
при построении цепочек не используются ключи key и битовые маски bm; соответственно, не используется их псевдослучайная генерация с помощью функции prf, значение seed также не требуется;
не используется явная структура адреса фрагмента данных adrs; однако, вместо нее при хешировании используются префиксы входных данных, однозначно соответствующие идентификатору ключа алгоритма верхнего уровня, а также номерам ключа LM-OTS, его обрабатываемого фрагмента и текущей итерации; последняя итерация хеширования отличается включением дополнительного префикса;
иначе вычисляется хеш-код подписываемого сообщения: во-первых, сообщение дополняется рядом префиксов, идентифицирующих ключ и рандомизирующих результат вычисления (рандомизатор включается в структуру подписи вместе с фрагментами sgn[i]); во-вторых, результирующий хеш-код конкатенируется с его же 16-байтной контрольной суммой, вычисленной по определенному алгоритму, описанному в [12].
Основные отличия алгоритмов LMS и HSS от, соответственно, XMSS и XMSSMT
Алгоритм LMS, как и XMSS, основан на использовании деревьев Меркля для вычисления единого открытого ключа из совокупности открытых ключей нижележащего одноразового алгоритма ЭП LM-OTS. У данных алгоритмов много общего, включая следующее:
оба алгоритма используют бинарные деревья для вычисления открытого ключа алгоритма верхнего уровня PK из совокупности открытых ключей алгоритма одноразовой ЭП;
упрощенно, листья дерева представляют собой открытые ключи алгоритма одноразовой ЭП, а узлы — результат хеширования конкатенации значений двух дочерних листьев или узлов;
общее количество одноразовых ключей pkq определяется высотой дерева h: q = 0, …, 2h-1; в стандартных вариантах алгоритма LMS h = 5, 10, 15, 20 или 25;
оба алгоритма включают в состав секретного ключа значение индекса (изначально обнуленное), указывающее на следующий применяемый одноразовый секретный ключ и инкрементируемое перед вычислением ЭП;
ЭП обоих алгоритмов вычисляются схожим образом; структура ЭП алгоритма LMS также содержит значение индекса секретного ключа, с помощью которого вычислялась ЭП, одноразовую подпись (вычисленную с помощью алгоритма LM-OTS), значение рандомизатора, примененное при ее вычислении, и путь аутентификации для восстановления дерева;
проверка ЭП алгоритма LMS также выполняется аналогичным алгоритму XMSS образом: сначала из значения ЭП алгоритма LM-OTS вычисляется значение открытого ключа данного алгоритма, затем с помощью полученного открытого ключа и имеющегося в структуре ЭП пути аутентификации достраивается дерево открытых ключей, после чего полученный в результате открытый ключ PK’ сравнивается с используемым для проверки подписи ключом PK алгоритма LMS; подпись признается верной только в случае, если данные ключи идентичны.
Существуют и значительные отличия между данными алгоритмами, включая следующие:
LMS при хешировании листьев или узлов не использует значения ключа key и битовых масок, а также функцию prf для их генерации; вместо адресов узлов используются префиксы, так же однозначно идентифицирующие узел;
в LMS не применяется дерево для сжатия открытых ключей одноразовой ЭП, вместо этого используется их хеширование (предварительно – конкатенация с префиксами, идентифицирующими конкретный лист) с помощью однократного для каждого листа вызова хеш-функции;
размер значения, ассоциированного с узлом дерева, является дополнительным параметром m алгоритма LMS; в общем случае, m ≠ n, но в стандартных вариантах алгоритмов LMS и HSS m также принимает значения 24 или 32.
Как было сказано выше, как и XMSSMT, алгоритм HSS основан на применении гипердерева, которое может содержать до 8 уровней деревьев.
Интересной особенностью алгоритма HSS является описанный в документе [12] порядок генерации секретных ключей LMS по мере необходимости непосредственно перед подписанием: в том случае, если текущий сгенерированный набор ключей LMS (соответствующий некоторой части деревьев гипердерева) уже был полностью использован для подписания сообщений, формируется следующая часть гипердерева (включая генерацию ключевых пар LMS), после чего эта часть используется для подписания сообщений до ее исчерпания.
Особенности алгоритмов на основе хеш-функций с сохранением состояния
Поскольку описанные в данной статье алгоритмы основаны на применении алгоритмов однократной ЭП, т. е. алгоритмов, в которых каждый секретный ключ может быть использован строго однократно во избежание потери криптостойкости, возникает необходимость хранения некоторого внутреннего состояния алгоритма. В рассмотренных выше алгоритмах состояние представляет собой индекс текущего листа дерева, соответствующего секретному ключу, который будет использоваться для вычисления ЭП в следующий раз (т. е. это первый из неиспользованных секретных ключей одноразового алгоритма ЭП).
Индекс должен гарантированно инкрементироваться перед вычислением очередной ЭП, что призвано противостоять повторному применению какого-либо из уже использованных ранее одноразовых секретных ключей – повторное применение одного и того же ключа для подписи различных сообщений может привести к последующей подделке злоумышленником ЭП произвольных сообщений. Причем инкрементирование производится именно перед вычислением ЭП, чтобы на корректное однократное применение ключей не повлиял какой-либо сбой устройства, которое вычисляет ЭП. В документе [12] даже предписывается в случае хранения индекса на жестком диске принудительно сбросить на диск все данные из кешей и только потом продолжить вычисление ЭП.
Необходимость хранения и обработки текущего состояния вносит коррективы в классический порядок применения алгоритмов ЭП без сохранения состояния, что возможно не во всех сценариях применения алгоритмов ЭП. Помимо этого, необходимо учитывать и тот факт, что секретные ключи алгоритмов верхнего уровня — XMSS, XMSSMT, LMS и HSS — также имеют ограниченное количество применений — по числу листьев используемого дерева. Следовательно, при реализации такого алгоритма необходимо выбирать конкретный из его вариантов (поскольку стандартные параметры конкретного варианта определяют, в числе прочего, количество листьев), предполагая заранее, какое максимальное количество подписей нужно будет вычислить до смены долговременной ключевой пары. В результате, можно предполагать, что сфера применения таких алгоритмов заметно сужена по сравнению с классическими алгоритмами ЭП.
Тем не менее, NIST пошел на стандартизацию сразу четырех алгоритмов, основанных на хеш-функциях с сохранением состояния, что было продиктовано следующими причинами:
отсутствия во время принятия документа NIST SP 800-208 (2020 г.) стандартов на другие постквантовые алгоритмы, которые были приняты значительно позже (в 2024 г.); конкурс NIST по выбору постквантовых алгоритмов для стандартизации в 2020 г. был еще в самом разгаре, а участвующие внем алгоритмы — в процессе интенсивного изучения;
стандартизованные в документе NIST SP 800–208 алгоритмы основываются на известных, стандартных и очень хорошо изученных ранее хеш‑функциях, обладающих криптографической стойкостью к нахождению прообразов.
Следовательно, рассмотренные алгоритмы потребовались как страховка на случай возникновения необходимости срочного перехода на них в случае прорыва в квантовых вычислениях и/или в системах с длительным сроком использования, измеряемым в несколько десятилетий [4]. Данные алгоритмы — это консервативный вариант, основанный на хорошо известных криптографических свойствах хеш-функций (в отличие от многих других подходов, применяемых в алгоритмах, которые анализировались в рамках конкурса NIST) и не требующий при этом гибридного применения вместе с классическими криптоалгоритмами.
При этом нельзя сказать, что рассмотренные алгоритмы не обладают некоторой гибкостью: выбирая определенный из стандартизованных вариантов, а также конкретный подход к хранению данных или их вычислению по мере необходимости, можно варьировать быстродействием алгоритма и размером его структурданных — конечно, в определенных пределах. Но при реализации любого из данных алгоритмов необходимо помнить об обязательно точном соблюдении рекомендаций NIST к его реализации, поскольку ошибочная в чем-либо реализация (например, в части строго однократного использования секретных ключей алгоритмов WOTS+ и LM-OTS, в части высокого качества генераторов случайных чисел, используемых для генерации секретных ключей и рандомизаторов, или в части строгого соблюдения уникальности адресов или префиксов при хешировании) может радикально снизить уровень криптостойкости реализуемого алгоритма.
Литература по теме
1. FIPS 203. Module-Lattice-Based Key-Encapsulation Mechanism Standard. August 13, 2024.
2. FIPS 204. Module-Lattice-Based Digital Signature Standard. August 13, 2024.
3. FIPS 205. Stateless Hash-Based Digital Signature Standard. August 13, 2024.
4. NIST SP 800-208. Recommendation for Stateful Hash-Based Signature Schemes. October 2020.
5. FIPS 186-5. Digital Signature Standard (DSS). February 3, 2023.
6. Merkle R. C. Secrecy, Authentication, and Public Key Systems. Stanford University Technical Report No. 1979-1. June 1979.
7. Buchmann J., Dahmen E., Hülsing A. XMSS – A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions. Second Version. November 26, 2011.
8. Huelsing A., Butin D., Gazdaq S., Rijneveld J., Mohaisen A. RFC 8391. XMSS: eXtended Merkle Signature Scheme. May 2018.
9. FIPS 180-4. Secure Hash Standard (SHS). August 2015.
10. FIPS 202. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. August 2015.
11. Hülsing A. W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes. 2017.
McGrew D., Curcio M., Fluhrer S. RFC 8554. Leighton-Micali Hash-Based Signatures. April 2019.
