XMSS

XMSS (eXtended Merkle Signature Scheme) — это постквантовая криптографическая схема цифровой подписи, основанная на хеш-функциях. Она относится к классу одноразовых подписей Меркла и обеспечивает защиту от атак с использованием квантовых компьютеров, поскольку её стойкость зависит только от криптографической стойкости используемой хеш-функции, а не от сложности решения задач факторизации или дискретного логарифмирования, которые уязвимы для квантовых алгоритмов (например, алгоритма Шора). XMSS была стандартизирована в 2018 году как RFC 8391 и является одной из рекомендуемых схем Национальным институтом стандартов и технологий США (NIST) для постквантовой криптографии.

История

Разработка XMSS началась в 2011 году группой исследователей под руководством Йоханнеса Бухмана (Johannes Buchmann) и Эрика Даменга (Erik Dahmen) из Технического университета Дармштадта. Схема была представлена как улучшение классической схемы подписи Меркла (Merkle Signature Scheme), предложенной Ральфом Мерклом в 1979 году. Основной целью было создание практичной и эффективной постквантовой подписи, устойчивой к атакам с использованием квантовых компьютеров.

В 2018 году XMSS была опубликована как RFC 8391 (Internet Engineering Task Force, IETF), что сделало её одной из первых постквантовых схем, получивших официальную стандартизацию. В 2022 году NIST включил XMSS в финальный список рекомендованных алгоритмов для постквантовой криптографии, наряду с LMS (Leighton-Micali Signature) и SPHINCS+.

Общие принципы работы

XMSS основана на идее дерева Меркла, где каждый лист дерева представляет собой одноразовую подпись (например, на основе схемы Уинтерница или WOTS+). Корень дерева служит открытым ключом, а подпись сообщения включает в себя одноразовую подпись и путь Меркла (набор хешей, доказывающих принадлежность листа к корню). Основные компоненты:

• Одноразовая подпись (WOTS+) — схема подписи Уинтерница с улучшенной защитой от коллизий. Каждый ключ может использоваться только для подписи одного сообщения, после чего подписывающий должен перейти к следующему листу.
• Дерево Меркла — бинарное дерево, где каждый узел является хешем от двух дочерних узлов. Корень дерева — открытый ключ. Подпись включает в себя путь от листа к корню (около log2(N) узлов, где N — количество листьев).
• Индекс состояния — подписывающий хранит текущий индекс листа, который ещё не был использован. После подписи индекс увеличивается, и старый лист становится недействительным.

Ключевые отличия от классической схемы Меркла

• Использование WOTS+ вместо WOTS (Winternitz One-Time Signature) для повышения эффективности и защиты от атак на основе коллизий.
• Введение «маскировки» (masking) — добавление случайных масок к хешам для предотвращения атак, основанных на структуре дерева.
• Поддержка множественных деревьев (multi-tree) — XMSS может быть расширена до XMSS^MT (Multi-Tree XMSS), где несколько деревьев объединяются в иерархию, что позволяет увеличить количество подписей без роста размера подписи.

Характеристики

Размеры ключей и подписей

• Открытый ключ: фиксированный размер, обычно 64 байта (для хеш-функции SHA-256).
• Секретный ключ: включает в себя все одноразовые ключи (или их seed), а также текущий индекс. Размер зависит от количества листьев (N) и может быть большим (например, 2^20 листьев — около 2 МБ для seed-представления).
• Подпись: состоит из одноразовой подписи (WOTS+) и пути Меркла. Размер подписи для одного дерева с 2^20 листьями составляет около 2,5 КБ (для SHA-256). Для XMSS^MT размер подписи может быть меньше за счёт иерархии.

Производительность

• Генерация ключей: требует построения всего дерева Меркла, что для N=2^20 занимает около 1-2 секунд на современном процессоре (зависит от хеш-функции).
• Подписание: быстрое — около 0,1-0,5 мс, так как требуется только одноразовая подпись и вычисление пути.
• Верификация: также быстрая — около 0,1-0,5 мс, так как проверяется одноразовая подпись и путь Меркла.

Ограничения

• Одноразовость листьев: каждый лист может быть использован только один раз. После исчерпания всех листьев необходимо генерировать новое дерево (или новую иерархию в XMSS^MT).
• Размер секретного ключа: для больших деревьев секретный ключ может быть большим, что требует хранения или эффективного восстановления из seed.
• Зависимость от хеш-функции: стойкость XMSS полностью определяется стойкостью используемой хеш-функции (например, SHA-256, SHA-512, SHAKE256). При компрометации хеш-функции вся схема становится небезопасной.

Применение

XMSS в основном используется в системах, где требуется долговременная безопасность и защита от квантовых атак, а также где количество подписей ограничено. Основные области применения:

• Криптовалюты и блокчейн: XMSS используется в некоторых проектах для подписи транзакций, так как её стойкость не зависит от квантовых уязвимостей (например, в проекте IOTA).
• Цифровые сертификаты и PKI: XMSS может быть использована для подписи сертификатов в постквантовой инфраструктуре открытых ключей (PKI).
• Встроенные системы и IoT: благодаря низким требованиям к вычислительным ресурсам при подписании и верификации, XMSS подходит для устройств с ограниченной производительностью (например, датчики, умные карты).
• Долговременное архивирование: XMSS позволяет подписывать документы, которые должны оставаться верифицируемыми в течение десятилетий, даже при появлении квантовых компьютеров.

Примеры использования

• IOTA: в криптовалюте IOTA используется XMSS для подписи транзакций, что обеспечивает постквантовую безопасность.
• Google: в 2019 году Google экспериментировала с XMSS в рамках проекта по постквантовой криптографии в Chrome.
• NIST: XMSS включена в рекомендации NIST для постквантовой криптографии (2022 год).

Безопасность

Квантовая устойчивость

XMSS устойчива к атакам с использованием квантовых компьютеров, поскольку её стойкость основана на хеш-функциях, которые считаются устойчивыми к квантовым атакам (алгоритм Гровера для поиска коллизий требует O(2^(n/2)) операций, где n — размер хеша). В отличие от RSA и ECDSA, которые уязвимы для алгоритма Шора, XMSS не требует факторизации или дискретного логарифмирования.

Атаки на основе коллизий

XMSS использует маскировку (masking) для предотвращения атак, основанных на коллизиях хеш-функций. Это делает её более безопасной, чем классическая схема Меркла, которая может быть уязвима для атак с использованием коллизий, если хеш-функция не является идеальной.

Ограничения безопасности

• Одноразовость: если один и тот же лист используется для подписи двух разных сообщений, злоумышленник может восстановить секретный ключ и подделать подписи. Поэтому подписывающий должен строго контролировать индекс состояния.
• Атаки на состояние: если злоумышленник может повлиять на индекс состояния (например, через сбой в системе), это может привести к повторному использованию листа.

Критика

Основная критика XMSS связана с её ограниченностью по количеству подписей и размером секретного ключа. Для приложений, требующих большого числа подписей (например, миллионы), XMSS требует либо очень больших деревьев (что увеличивает размер подписи), либо иерархических структур (XMSS^MT), что усложняет реализацию. Кроме того, XMSS не поддерживает «отзыв» подписей — после использования листа он не может быть повторно применён, что требует тщательного управления ключами.

Также отмечается, что XMSS менее эффективна, чем некоторые другие постквантовые схемы, такие как SPHINCS+ (которая является статической и не требует состояния), но при этом XMSS проще в реализации и имеет меньший размер подписи для фиксированного количества сообщений.

Источники

• RFC 8391: XMSS: eXtended Merkle Signature Scheme (2018)
• NIST Post-Quantum Cryptography Standardization (2022)
• Buchmann, J., Dahmen, E., Hülsing, A. (2011). XMSS – A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions
• Bernstein, D. J., et al. (2015). SPHINCS: Practical Stateless Hash-Based Signatures
• IOTA Foundation: XMSS in IOTA (2018)