Криптография на основе хеша

Криптография на основе хеша - это общий термин для построения криптографических примитивов на основе безопасность хэш-функций. Это представляет интерес как тип постквантовой криптографии.

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

В 2019 году Национальный институт стандартов и технологий США объявил о своем намерении обнародовать стандарты для криптографии на основе хэшей с отслеживанием состояния на основе (XMSS) и (LMS), которые применимы в различные обстоятельства.

• 1 История
• 2 Схемы одноразовой подписи
• 3 Объединение множества одноразовых пар ключей в схему подписи на основе хэша
• 4 Свойства схем подписи на основе хеша
• 5 Примеры схем подписи на основе хешей
• 6 Реализации
• 7 Ссылки
• 8 Внешние ссылки

Лесли Лэмпорт изобрел подписи на основе хешей в 1979 году. XMSS ( eXtended Merkle Signature Scheme) и схемы подписи на основе хешей SPHINCS были введены в 2011 и 2015 годах соответственно. XMSS был разработан группой исследователей под руководством Йоханнеса Бухмана и основан как на оригинальной схеме Меркла, так и на Обобщенной схеме подписи Меркла 2007 года (GMSS). Вариант XMSS с несколькими деревьями, XMSS, был описан в 2013 году.

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

Обычно используемые схемы одноразовой подписи включают схему Лампорта-Диффи, схему Винтерница и ее усовершенствования, такие как схема W-OTS. В отличие от оригинальной схемы Лэмпорта-Диффи, схема Винтерница и ее варианты могут подписывать сразу несколько битов. Количество битов, которые нужно подписать за один раз, определяется значением: параметром Winternitz. Наличие этого параметра обеспечивает компромисс между размером и скоростью. Большие значения параметра Winternitz приводят к коротким подписям и ключам за счет более медленной подписи и проверки. На практике типичное значение для этого параметра - 16.

В случае подписей на основе хэша без сохранения состояния используются схемы малоразмерной подписи. Такие схемы позволяют постепенно снижать безопасность в случае использования кратковременного ключа более одного раза. HORST - это пример схемы кратной подписи.

Основная идея схем подписи на основе хешей состоит в объединении большего количества одноразовых пар ключей в одну структура, чтобы получить практический способ подписания более одного раза (но ограниченное количество раз). Это делается с использованием древовидной структуры Меркла с возможными вариациями. Один открытый и один закрытый ключи состоят из множества открытых и закрытых ключей базовой одноразовой схемы. Глобальный открытый ключ - это единственный узел на самом верху дерева Меркла. Его значение является результатом выбранной хеш-функции, поэтому типичный размер открытого ключа составляет 32 байта. Действительность этого глобального открытого ключа связана с действительностью данного одноразового открытого ключа с использованием последовательности узлов дерева. Эта последовательность называется путем аутентификации. Он хранится как часть подписи и позволяет проверяющему восстановить путь узла между этими двумя открытыми ключами.

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

Проблема обхода дерева критична для производительности подписи. Были внедрены все более эффективные подходы, значительно сокращающие время подписания.

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

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

Схемы подписи на основе хеширования основаны на предположениях безопасности относительно базовой хэш-функции, но может использоваться любая хеш-функция, удовлетворяющая этим предположениям. Как следствие, каждая адекватная хэш-функция дает другую соответствующую схему подписи на основе хеш-функции. Даже если данная хеш-функция становится небезопасной, достаточно заменить ее другой, защищенной, чтобы получить безопасный экземпляр рассматриваемой схемы подписи на основе хеширования. Некоторые схемы подписи на основе хешей (например, XMSS с генерацией псевдослучайного ключа) являются безопасными, что означает, что предыдущие подписи остаются действительными, если секретный ключ скомпрометирован.

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

Поскольку они полагаются на основную схему одноразовой подписи, схемы подписи на основе хэша могут безопасно подписывать только фиксированное количество сообщений. В случае схем Меркла и XMSS максимум $2\; h\; \{\backslash \; displaystyle\; 2\; ^\; \{h\}\}$сообщений может быть безопасно подписано с помощью $h\; \{\backslash \; displaystyle\; h\}$общая высота дерева Меркла.

Начиная с первоначальной схемы Меркла, были введены многочисленные схемы подписи на основе хешей с улучшенной производительностью. Последние включают схемы XMSS, Leighton-Micali (LMS), SPHINCS и BPQS. Большинство схем подписи на основе хешей - это с отслеживанием состояния, что означает, что для подписания требуется обновление секретного ключа, в отличие от обычных схем цифровой подписи. Для схем подписи на основе хешей с отслеживанием состояния подпись требует сохранения состояния используемых одноразовых ключей и обеспечения того, чтобы они никогда не использовались повторно. Схемы XMSS, LMS и BPQS сохраняют состояние, а схема SPHINCS не имеет состояния. Подписи SPHINCS больше, чем подписи XMSS, LMS, а BPQS был разработан специально для систем блокчейн. В дополнение к схеме одноразовой подписи WOTS, SPHINCS также использует схему однократной подписи (на основе хэша), называемую HORST. HORST является усовершенствованием более старой схемы кратковременной подписи HORS (Hash to Obtain Random Subset).

Схемы XMSS и XMSS с отслеживанием состояния на основе хэшей указаны в RFC 8391 (XMSS : Расширенная схема подписи Меркла). Подписи на основе хэша Лейтон-Микали указаны в RFC 8554. В литературе были предложены практические усовершенствования, которые снимают проблемы, связанные со схемами с отслеживанием состояния. Хеш-функции, подходящие для этих схем, включают SHA-2, SHA-3 и BLAKE.

В отличие от других популярных сетей блокчейнов и криптовалюты, которые используют уже стандартизованные алгоритмы цифровой подписи на эллиптических кривых (ECDSA ), уже NIST, Quantum Resistant Ledger (QRL) является первым открытым source сеть для реализации расширенной схемы подписи Меркла. В отличие от традиционных подписей ECDSA, эта схема подписи с отслеживанием состояния доказуемо устойчива к достаточно мощному квантовому компьютеру, на котором выполняется алгоритм Шора.

Схемы XMSS, GMSS и SPHINCS доступны в криптографической версии Java Bouncy Castle. API. SPHINCS реализован в наборе инструментов тестирования SUPERCOP. Существуют оптимизированные и неоптимизированные эталонные реализации XMSS RFC. Схема LMS была реализована на Python и на C после ее Интернет-проекта.

• T. Ланге. «Подписи на основе хеша». Энциклопедия криптографии и безопасности, Springer US, 2011. [2]
• F. Т. Лейтон, С. Микали. «Крупные доказуемо быстрые и безопасные схемы цифровой подписи, основанные на одной безопасной хэш-функции». Патент США 5 432 852, [3 ] 1995.
• G. Беккер. «Схемы подписи Меркла, деревья Меркла и их криптоанализ», семинар «Пост квантовая криптология» в Рурском университете Бохума, Германия, 2008. [4]
• Э. Дахмен, М. Дринг, Э. Клинцевич, Дж. Бухманн, Л.С. Коронадо Гарсия. «CMSS - Улучшенная схема подписи Меркла». Progress in Cryptology - Indocrypt 2006. [5]
• Р. Меркл. «Системы секретности, аутентификации и открытого ключа / Сертифицированная цифровая подпись». Кандидат наук. диссертация, кафедра электротехники, Стэнфордский университет, 1979. [6]
• S. Микали, М. Якобссон, Т. Лейтон, М. Шидло. «Фрактальное представление дерева Меркла и его обход». RSA-CT 03. [7]
• стр. Кампанакис, С. Флюрер. «LMS против XMSS: сравнение предложенных стандартов подписи на основе хеширования с отслеживанием состояния». Cryptology ePrint Archive, Отчет 2017/349. [8]
• Д. Наор, А. Шенхав, А. Шерсть. «Повторение об одноразовых подписях: практические быстрые подписи с использованием фрактального обхода дерева Меркла». 24-я конференция инженеров по электротехнике и радиоэлектронике IEEE в Израиле, 2006 г. [9]

• [10] Прокомментированный список литературы о схемах подписи на основе хешей.
• [11 ] Другой список ссылок (без комментариев).