Криптография на основе хеша
Криптография на основе хэша — это общий термин для конструкций криптографических примитивов, основанных на безопасности хеш-функций . Она представляет интерес как разновидность постквантовой криптографии .
До сих пор криптография на основе хэша используется для создания схем цифровых подписей, таких как схема подписи Меркла , нулевого разглашения и доказательств вычислительной целостности, таких как zk-STARK. [1] система доказательств и проверка диапазона по выданным учетным данным через HashWires [2] протокол. Схемы подписи на основе хэша сочетают в себе схему одноразовой подписи, такую как подпись Лэмпорта , с древовидной структурой Меркла . Поскольку ключ схемы одноразовой подписи может безопасно подписать только одно сообщение, практично объединить множество таких ключей в одну более крупную структуру. Для этого используется древовидная структура Меркла. В этой иерархической структуре данных хеш-функция и конкатенация используются неоднократно для вычисления узлов дерева.
Одним из соображений схем подписи на основе хэша является то, что они могут безопасно подписывать только ограниченное количество сообщений из-за использования схем одноразовой подписи. США Национальный институт стандартов и технологий (NIST) уточнил, что алгоритмы его конкурса постквантовой криптографии поддерживают как минимум 2 64 подписи безопасно. [3]
В 2022 году NIST объявил SPHINCS+ одним из трех алгоритмов, которые будут стандартизированы для цифровых подписей. [4] В 2020 году NIST стандартизировал криптографию на основе хэша с сохранением состояния на основе расширенной схемы подписей Меркла (XMSS) и подписей Лейтона-Микали (LMS), которые применимы в различных обстоятельствах, но отметил, что требование сохранять состояние при их использовании делает их более трудно реализовать таким образом, чтобы избежать неправильного использования. [5] [6] [7]
История [ править ]
Лесли Лэмпорт изобрел подписи на основе хеша в 1979 году. XMSS (расширенная схема подписи Меркла). [8] и СФИНКИ [9] [10] схемы подписи на основе хэша были введены в 2011 и 2015 годах соответственно. XMSS был разработан группой исследователей под руководством Йоханнеса Бухмана и основан как на оригинальной схеме Меркла, так и на Обобщенной схеме подписи Меркла 2007 года (GMSS). [11] Многодеревьевой вариант XMSS, XMSS. МТ , был описан в 2013 году. [12]
Схемы одноразовой подписи [ править ]
Схемы подписи на основе хэша используют схемы одноразовой подписи в качестве строительного блока. Данный одноразовый ключ подписи можно использовать только для безопасной подписи одного сообщения. Действительно, подписи раскрывают часть ключа подписи. Безопасность схем одноразовой подписи (на основе хэша) зависит исключительно от безопасности базовой хэш-функции.
Обычно используемые схемы одноразовой подписи включают схему Лэмпорта – Диффи , схему Винтерница. [13] и его улучшения, такие как W-OTS + схема. [14] В отличие от оригинальной схемы Лэмпорта – Диффи, схема Винтерница и ее варианты могут подписывать множество битов одновременно. Количество битов, которые должны быть подписаны одновременно, определяется значением: параметром Винтерница. Существование этого параметра обеспечивает компромисс между размером и скоростью. Большие значения параметра Винтерница приводят к коротким подписям и ключам за счет более медленного подписания и проверки. На практике типичное значение этого параметра составляет 16.
В случае подписей на основе хэша без сохранения состояния используются схемы маловременной подписи. Такие схемы позволяют постепенно снижать безопасность в случае многократного использования многоразового ключа. HORST является примером схемы с небольшим размером.
множества пар одноразовых ключей в схему подписи на хеша Объединение основе
Основная идея схем подписи на основе хэша заключается в объединении большего количества пар одноразовых ключей в единую структуру для получения практичного способа подписания более одного раза (но ограниченное количество раз). Это делается с использованием древовидной структуры Меркла с возможными вариациями. Один открытый и один закрытый ключ создаются из множества открытых и закрытых ключей базовой одноразовой схемы. Глобальный открытый ключ — это единственный узел на самой вершине дерева Меркла. Его значение является результатом выбранной хэш-функции, поэтому типичный размер открытого ключа составляет 32 байта. Действительность этого глобального открытого ключа связана с действительностью данного одноразового открытого ключа с использованием последовательности узлов дерева. Эта последовательность называется путем аутентификации. Он хранится как часть подписи и позволяет проверяющему восстановить путь узла между этими двумя открытыми ключами.
Глобальный закрытый ключ обычно обрабатывается с помощью генератора псевдослучайных чисел. Тогда достаточно сохранить начальное значение. Одноразовые секретные ключи последовательно извлекаются из начального значения с помощью генератора. При таком подходе глобальный закрытый ключ также очень мал, например, обычно 32 байта.
Проблема обхода дерева имеет решающее значение для производительности подписи. Внедряются все более эффективные подходы, значительно ускоряющие время подписания.
Некоторые схемы подписи на основе хэша используют несколько уровней дерева, обеспечивая более быструю подпись за счет более крупных подписей. В таких схемах для подписи сообщений используется только самый нижний уровень деревьев, тогда как все остальные деревья подписывают корневые значения нижних деревьев.
Работа Наора-Юнга [15] показывает шаблон, по которому можно перевести ограниченный тактовый размер семейства типов Меркла в неограниченную (регулярную) тактовую схему.
Свойства схем подписи на основе хэша [ править ]
Схемы подписи на основе хэша основаны на предположениях безопасности относительно базовой хеш-функции, но можно использовать любую хеш-функцию, удовлетворяющую этим предположениям. Как следствие, каждая адекватная хеш-функция дает другую соответствующую схему подписи на основе хеш-функции. Даже если данная хэш-функция становится небезопасной, достаточно заменить ее другой, безопасной, чтобы получить безопасную реализацию рассматриваемой схемы подписи на основе хеш-функции. Некоторые схемы подписи на основе хэша (например, XMSS с генерацией псевдослучайного ключа) являются защищенными вперед, что означает, что предыдущие подписи остаются действительными, если секретный ключ скомпрометирован.
Минимальность предположений о безопасности — еще одна характеристика схем подписи на основе хэша. Как правило, для этих схем требуется только безопасная (например, в смысле устойчивости второго прообраза ) криптографическая хэш-функция, чтобы гарантировать общую безопасность схемы. Такое предположение необходимо для любой схемы цифровой подписи; однако другие схемы подписи требуют дополнительных предположений о безопасности , чего здесь нет.
Поскольку схемы подписи на основе хэша полагаются на базовую схему одноразовой подписи, они могут безопасно подписывать только фиксированное количество сообщений. В случае схем Меркла и XMSS максимум сообщения могут быть безопасно подписаны с помощью общая высота дерева Меркла.
Примеры схем подписи на основе хэша [ править ]
Со времени первоначальной схемы Меркла было введено множество схем подписи на основе хэша с улучшенной производительностью. Среди последних — схемы XMSS, Лейтона-Микали (LMS), SPHINCS и BPQS. Большинство схем подписи на основе хэша имеют состояние , что означает, что для подписания требуется обновление секретного ключа, в отличие от обычных схем цифровой подписи. Для схем подписи на основе хэша с сохранением состояния подписывание требует сохранения состояния используемых одноразовых ключей и обеспечения того, чтобы они никогда не использовались повторно. XMSS, LMS и BPQS [16] схемы сохраняют состояние, а схема SPHINCS не имеет состояния. Подписи SPHINCS больше, чем подписи XMSS и LMS. BPQS был разработан специально для блокчейн-систем. В дополнение к схеме одноразовой подписи WOTS+, [14] SPHINCS также использует схему подписи с несколькими временами (на основе хэша), называемую HORST. HORST — это улучшение старой схемы с небольшими сигнатурами, HORS (хэш для получения случайного подмножества). [17]
Схемы на основе хэша с сохранением состояния XMSS и XMSS. МТ указаны в RFC 8391 (XMSS: расширенная схема подписи Меркла). [18] Подписи Лейтона-Микали на основе хеша указаны в RFC 8554. [19] В литературе были предложены практические улучшения, которые облегчают проблемы, связанные со схемами с состоянием. [20] Хэш-функции, подходящие для этих схем, включают SHA-2 , SHA-3 и BLAKE .
Реализации [ править ]
Схемы XMSS, GMSS и SPHINCS доступны в криптографических API Java Bouncy Castle . [21] Схема XMSS доступна в криптографических API wolfSSL. [22] SPHINCS реализован в наборе инструментов для сравнительного анализа SUPERCOP. [23] Оптимизированный [24] и неоптимизированный [25] существуют эталонные реализации XMSS RFC. Схема LMS реализована на Python. [26] и в С [27] после его Интернет-проекта.
Ссылки [ править ]
- ^ Бен-Сассон, Эли и Бентов, Иддо и Хореш, Йинон и Рябзев, Майкл, 2018. Масштабируемая, прозрачная и постквантовая безопасная вычислительная целостность .
- ^ Халкия, Константинос; Коэн, Шир; Леви, Кевин; Моезиния, Фредрик; Ромайллер, Йолан (2021). «HashWires: сверхэффективное подтверждение диапазона на основе учетных данных» . Симпозиум по технологиям повышения конфиденциальности (PETS) 2021 .
- ^ «Требования к подаче и критерии оценки процесса стандартизации постквантовой криптографии» (PDF) . НИСТ ЦКРС .
- ^ «NIST объявляет о четырех квантово-устойчивых алгоритмах» . ВенчурБит . 05.07.2022 . Проверено 10 июля 2022 г.
- ^ Отдел компьютерной безопасности, Лаборатория информационных технологий (01.02.2019). «Запрос на общественные комментарии по поводу HBS с отслеживанием состояния | CSRC» . ЦКРС | НИСТ . Проверено 4 февраля 2019 г.
- ^ Алагич, Горжан; Апон, Дэниел; Купер, Дэвид; Данг, Куинь; Данг, Тхинь; Келси, Джон; Лихтингер, Джейкоб; Миллер, Карл; Муди, Дастин; Перальта, Рене; Перлнер, Рэй (5 июля 2022 г.). «Отчет о состоянии третьего раунда процесса стандартизации пост-квантовой криптографии NIST» . doi : 10.6028/NIST.IR.8413-upd1 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Купер, Дэвид; Апон, Дэниел; Данг, Куинь; Дэвидсон, Майкл; Дворкин, Моррис; Миллер, Карл (29 октября 2020 г.). «Рекомендации по схемам подписи на основе хеша с сохранением состояния» . doi : 10.6028/NIST.SP.800-208 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Бухманн, Йоханнес; Дамен, Эрик; Хюльсинг, Андреас (2011). «XMSS - практическая схема прямой безопасной подписи, основанная на минимальных предположениях о безопасности». Постквантовая криптография . Конспекты лекций по информатике. Том. 7071. стр. 117–129. CiteSeerX 10.1.1.400.6086 . дои : 10.1007/978-3-642-25405-5_8 . ISBN 978-3-642-25404-8 . ISSN 0302-9743 .
- ^ Бернштейн, Дэниел Дж.; Хопвуд, Дайра; Хюльсинг, Андреас; Ланге, Таня ; Нидерхаген, Рубен; Папахристодулу, Луиза; Шнайдер, Майкл; Швабе, Питер; Уилкокс-О'Хирн, Зуко (2015). «SPHINCS: Практические подписи на основе хэша без сохранения состояния». В Освальде, Элизабет ; Фишлин, Марк (ред.). Достижения в криптологии -- EUROCRYPT 2015 . Конспекты лекций по информатике. Том 9056. Springer Berlin Heidelberg. стр. 368–397. CiteSeerX 10.1.1.690.6403 . дои : 10.1007/978-3-662-46800-5_15 . ISBN 9783662467992 .
- ^ «СФИНКИ: Введение» .
- ^ Бухманн, Йоханнес; Дамен, Эрик; Клинцевич, Елена; Окейя, Кацуюки; Вийом, Камилла (2007). «Подписи Меркла с практически неограниченной емкостью подписей». Прикладная криптография и сетевая безопасность . Конспекты лекций по информатике. Том. 4521. стр. 31–45. дои : 10.1007/978-3-540-72738-5_3 . ISBN 978-3-540-72737-8 .
- ^ Хюльсинг, Андреас; Рауш, Леа; Бухманн, Йоханнес (2013). «Оптимальные параметры для XMSS MT». Инженерия безопасности и разведывательная информатика . Конспекты лекций по информатике. Том. 8128. стр. 194–208. дои : 10.1007/978-3-642-40588-4_14 . ISBN 978-3-642-40587-7 .
- ^ Додс, К.; Смарт, НП; Стам, М. (2005). «Схемы цифровой подписи на основе хэша». Криптография и кодирование . Конспекты лекций по информатике. Том. 3796. стр. 96–115. дои : 10.1007/11586821_8 . ISBN 978-3-540-30276-6 .
- ^ Перейти обратно: а б Хюльсинг, Андреас (2013). «W-OTS + - более короткие подписи для схем подписи на основе хэша». Прогресс в криптологии – AFRICACRYPT 2013 . Конспекты лекций по информатике. Том. 7918. стр. 173–188. дои : 10.1007/978-3-642-38553-7_10 . ISBN 978-3-642-38552-0 .
- ^ М. Наор, М. Юнг. «Универсальные односторонние хеш-функции и их криптографические приложения». СТОК 1989. [1] .
- ^ Халкия, Константинос; Браун, Джеймс; Хирн, Майк; Лиллехаген, Томми; Нитто, Игорь; Шретер, Томас (2018). «Постквантовые сигнатуры с использованием блокчейна» (PDF) . Материалы Международной конференции IEEE по блокчейну (Киберматика-2018) : 1196–1203.
- ^ Рейзин, Леонид; Рейзин, Натан (2002). «Лучше, чем BiBa: короткие одноразовые подписи с быстрой подписью и проверкой». Информационная безопасность и конфиденциальность . Конспекты лекций по информатике. Том. 2384. стр. 144–153. CiteSeerX 10.1.1.24.7320 . дои : 10.1007/3-540-45450-0_11 . ISBN 978-3-540-43861-8 .
- ^ Хюльсинг, Андреас; Бутин, Денис; Газдаг, Стефан; Райневельд, Йост; Мохайсен, Азиз (май 2018 г.). «RFC 8391 – XMSS: расширенная схема подписи Меркла» . www.tools.ietf.org . IETF.
- ^ МакГрю, Дэвид; Курсио, Майкл; Флюрер, Скотт (апрель 2019 г.). «RFC 8554 - Подписи Лейтона-Микали на основе хеша» . www.tools.ietf.org . IETF.
- ^ МакГрю, Дэвид; Кампанакис, Панос; Флюрер, Скотт; Газдаг, Стефан-Лукас; Бутин, Денис; Бухманн, Йоханнес (2016). «Государственное управление подписями на основе хэша» (PDF) . Исследования по стандартизации безопасности . Конспекты лекций по информатике. Том. 10074. стр. 244–260. дои : 10.1007/978-3-319-49100-4_11 . ISBN 978-3-319-49099-1 . S2CID 809073 . Архивировано из оригинала (PDF) 18 августа 2017 г.
- ^ "bcgit/bc-java" . Гитхаб . 2018-12-18.
- ^ "волкSSL/волфссл" . Гитхаб . 2023-11-22.
- ^ «СУПЕРКОП» . Архивировано из оригинала 15 февраля 2015 г. Проверено 31 мая 2017 г.
- ^ «Кодекс» . Андреас Хюльсинг .
- ^ "squareUP > Публикации" . www.pqsignatures.org .
- ^ Дэвид, МакГрю (29 мая 2018 г.). «Пакет hash-sigs: реализация иерархической системы подписей Лейтона – Микали (HSS)» . Гитхаб .
- ^ Дэвид, МакГрю (22 ноября 2018 г.). «Полнофункциональная реализация схем подписи на основе хэша LMS и HSS из проекта-mcgrew-hash-sigs-07» . Гитхаб .
- Т. Ланге. «Подписи на основе хеша». Энциклопедия криптографии и безопасности, Springer US, 2011. [2]
- Ф.Т. Лейтон, С. Микали. «Большие доказуемо быстрые и безопасные схемы цифровой подписи, основанные на одной безопасной хэш-функции». Патент США 5432852, [3], 1995 г.
- Г. Беккер. «Схемы подписей Меркла, деревья Меркла и их криптоанализ», семинар «Постквантовая криптология» в Рурском университете в Бохуме, Германия, 2008 г. [4]
- Э. Дамен, М. Дринг, Э. Клинцевич, Дж. Бухман, Л. С. Коронадо Гарсия. «CMSS — улучшенная схема подписи Меркла». Прогресс в криптологии – Indocrypt 2006. [5]
- Р. Меркл. «Системы секретности, аутентификации и открытых ключей / Сертифицированная цифровая подпись». доктор философии диссертация, кафедра электротехники, Стэнфордский университет, 1979. [6] Архивировано 14 августа 2018 г. в Wayback Machine.
- С. Микали, М. Якобссон, Т. Лейтон, М. Шидло. «Представление и обход фрактального дерева Меркла». РСА-КТ 03. [7]
- П. Кампанакис, С. Флюрер. «LMS против XMSS: сравнение предлагаемых стандартов подписей на основе хэша с отслеживанием состояния». Архив криптологии ePrint, отчет 2017/349. [8]
- Д. Наор, А. Шенхав, А. Вул. «Возвращение к одноразовым подписям: практические быстрые подписи с использованием фрактального обхода дерева Меркла». 24-й съезд инженеров по электротехнике и электронике IEEE в Израиле, 2006 г. [9]
