SPHINCS+

SPHINCS+ — это постквантовая криптографическая схема электронной подписи, основанная на хеш-функциях. Она относится к классу безключевых (stateless) схем, то есть не требует поддержания состояния (счётчика) между операциями подписания, что отличает её от многих других хеш-ориентированных схем, таких как XMSS и LMS. SPHINCS+ является одним из финалистов конкурса постквантовой криптографии, организованного Национальным институтом стандартов и технологий США (NIST), и была стандартизирована в 2024 году.

История

Разработка SPHINCS+ началась как ответ на необходимость создания криптографических алгоритмов, устойчивых к атакам с использованием квантовых компьютеров. В 2015 году группа исследователей, включая Дэниела Бернштейна, Андреаса Хюльсунга, Танжерда Ланге, Рубена Нидерхагена и других, представила оригинальную схему SPHINCS. Она была основана на идее использования хеш-деревьев Меркла и однократных подписей (OTS) для создания безключевой системы.

В 2017 году SPHINCS была подана на конкурс NIST по постквантовой криптографии. В ходе конкурса схема была значительно усовершенствована, что привело к появлению версии SPHINCS+. Основные улучшения включали оптимизацию размера подписи, повышение скорости верификации и повышение безопасности за счёт использования более эффективных хеш-функций (например, SHA-256 и SHAKE-256) и методов сжатия.

В 2022 году NIST объявил SPHINCS+ одним из четырёх финалистов для стандартизации в категории схем подписи. В 2024 году алгоритм был официально стандартизирован в документе FIPS 205 (Stateless Hash-Based Digital Signature Standard). SPHINCS+ стал первой безключевой хеш-ориентированной схемой, принятой в качестве федерального стандарта США.

Принцип работы

SPHINCS+ основана на комбинации нескольких криптографических примитивов:

• Однократные подписи (OTS): Каждый ключ подписи (пара «закрытый ключ — открытый ключ») используется только один раз. Для этого применяются схемы, такие как WOTS+ (Winternitz One-Time Signature Plus), которые позволяют подписывать сообщение, разбитое на блоки, с помощью хеш-функций.
• Хеш-деревья Меркла: Для объединения множества однократных открытых ключей в один корневой открытый ключ используется дерево Меркла. Это позволяет верифицировать подпись, не раскрывая все однократные ключи.
• Гипердеревья: SPHINCS+ использует многоуровневую структуру деревьев (гипердеревья), что позволяет уменьшить размер подписи по сравнению с простым деревом Меркла. Каждый уровень состоит из нескольких деревьев, и подпись включает пути от листа до корня каждого уровня.
• Псевдослучайная генерация ключей: Для обеспечения безключевости (stateless) каждый раз при подписании генерируется новый псевдослучайный набор однократных ключей на основе исходного закрытого ключа. Это исключает необходимость запоминать, какие ключи уже использовались.

Процесс подписания сообщения включает следующие шаги:

1. Генерация псевдослучайного индекса для выбора однократного ключа.
2. Создание подписи с помощью OTS-схемы (WOTS+).
3. Построение пути аутентификации через гипердерево, который подтверждает, что данный однократный ключ принадлежит корневому открытому ключу.

Верификация подписи заключается в проверке OTS-подписи и восстановлении корневого хеша с использованием предоставленного пути аутентификации.

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

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

SPHINCS+ предлагает несколько наборов параметров, обеспечивающих различные уровни безопасности и производительности. Основные параметры включают:

• Закрытый ключ: 64 байта (для всех уровней безопасности).
• Открытый ключ: 32 байта (для 128-битного уровня безопасности) или 64 байта (для 256-битного уровня).
• Подпись: Размер подписи варьируется от 7,8 КБ (для 128-битного уровня) до 49,6 КБ (для 256-битного уровня). Это значительно больше, чем у традиционных схем, таких как RSA (256 байт) или ECDSA (64 байта), но является компромиссом для обеспечения безопасности против квантовых атак.

Уровни безопасности

NIST определил три уровня безопасности для SPHINCS+:

• SPHINCS+-128s: 128-битный уровень безопасности (постквантовая безопасность, эквивалентная AES-128). Размер подписи — около 7,8 КБ.
• SPHINCS+-128f: 128-битный уровень безопасности, оптимизированный для скорости подписания. Размер подписи — около 17,2 КБ.
• SPHINCS+-256s: 256-битный уровень безопасности (эквивалент AES-256). Размер подписи — около 49,6 КБ.

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

Скорость работы SPHINCS+ зависит от параметров. Версия «-f» (fast) обеспечивает более быстрое подписание за счёт увеличения размера подписи, в то время как версия «-s» (small) минимизирует размер подписи, но требует больше времени на вычисления. В среднем, подписание сообщения на современном процессоре (например, Intel Core i7) занимает от 1 до 10 миллисекунд для версии «-f» и от 10 до 100 миллисекунд для версии «-s». Верификация обычно быстрее подписания и занимает от 0,5 до 5 миллисекунд.

Применение

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

• Цифровые подписи для документов и программного обеспечения: Обеспечение подлинности и целостности данных на десятилетия вперёд.
• Блокчейн и криптовалюты: Некоторые проекты, такие как IOTA, рассматривают SPHINCS+ для защиты от квантовых атак на транзакции.
• Инфраструктура открытых ключей (PKI): Замена традиционных схем (RSA, ECDSA) в сертификатах и TLS-соединениях.
• Военные и правительственные системы: Требования к долгосрочной секретности данных, особенно в контексте «собери сейчас, расшифруй позже» (harvest now, decrypt later).

Однако из-за большого размера подписи (в 10–100 раз больше, чем у традиционных схем) SPHINCS+ менее пригодна для приложений с ограниченной пропускной способностью, таких как IoT-устройства или мобильные сети с низкой скоростью передачи данных.

Критика и ограничения

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

Также отмечается, что SPHINCS+ является более сложной в реализации по сравнению с традиционными схемами, что увеличивает риск ошибок при внедрении. Однако, в отличие от схем, основанных на решётках (например, CRYSTALS-Dilithium), SPHINCS+ не требует сложных математических операций, таких как умножение матриц, что упрощает аппаратную реализацию.

Сравнение с другими постквантовыми схемами

SPHINCS+ часто сравнивают с другими финалистами конкурса NIST:

• CRYSTALS-Dilithium: Схема на основе решёток, обеспечивающая меньший размер подписи (2–4 КБ) и более высокую скорость. Однако её безопасность основана на предположении о сложности задач на решётках, которые могут быть уязвимы к будущим криптоаналитическим атакам.
• FALCON: Ещё одна схема на основе решёток с очень маленьким размером подписи (около 0,7 КБ), но сложной реализацией из-за использования чисел с плавающей точкой.
• XMSS и LMS: Хеш-ориентированные схемы с состоянием (stateful), которые требуют отслеживания использованных ключей. Они имеют меньший размер подписи (2–4 КБ), но менее удобны в использовании из-за необходимости поддержания состояния.

SPHINCS+ считается наиболее консервативным выбором с точки зрения безопасности, так как её стойкость основана только на свойствах хеш-функций, которые хорошо изучены.

Интересные факты

• SPHINCS+ является единственной безключевой хеш-ориентированной схемой, стандартизированной NIST. Все остальные стандартизированные схемы (Dilithium, FALCON) основаны на решётках.
• Название «SPHINCS» является аббревиатурой от «Stateless Practical Hash-based Incredibly Nice Cryptographic Signature» (Безключевая практичная хеш-ориентированная невероятно хорошая криптографическая подпись). Плюс в названии SPHINCS+ указывает на улучшенную версию.
• В 2023 году исследователи из Университета Радбауда в Нидерландах продемонстрировали успешную реализацию SPHINCS+ на микроконтроллере ARM Cortex-M4, что подтверждает возможность её использования в устройствах с ограниченными ресурсами.

Источники

• NIST FIPS 205: Stateless Hash-Based Digital Signature Standard (2024).
• Bernstein, D. J., Hülsing, A., Lange, T., et al. «SPHINCS: Practical Stateless Hash-Based Signatures» (2015).
• Hülsing, A., et al. «SPHINCS+ Submission to the NIST Post-Quantum Cryptography Standardization Project» (2020).
• National Institute of Standards and Technology. «Post-Quantum Cryptography: Selected Algorithms 2022» (2022).
• Документация и спецификации SPHINCS+ на официальном сайте проекта (sphincs.org).