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

Hash-based cryptography

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

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

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

История

Лесли Лэмпорт изобрел подписи на основе хешей в 1979 году. XMSS (Расширенная схема подписи Меркла)[2] и СФИНКОВ[3][4] Схемы подписи на основе хэша были введены в 2011 и 2015 годах соответственно. XMSS был разработан группой исследователей под руководством Йоханнес Бухманн и основан как на оригинальной схеме Меркла, так и на Общей схеме подписи Меркла 2007 года (GMSS).[5] Многодеревьевый вариант XMSS, XMSSMT, был описан в 2013 году.[6]

Схемы одноразовой подписи

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

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

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

Объединение множества одноразовых пар ключей в схему подписи на основе хэша

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

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

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

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

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

Свойства схем подписи на основе хешей

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

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

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

Примеры схем подписи на основе хешей

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

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

Реализации

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

Схемы XMSS, GMSS и SPHINCS доступны в Java Надувной Замок криптографические API.[19] SPHINCS реализован в наборе инструментов тестирования SUPERCOP.[20] Оптимизировано[21] и неоптимизированный[22] существуют эталонные реализации XMSS RFC. Схема LMS реализована на Python[23] а в C[24] следуя его Интернет-проекту.

Рекомендации

  1. ^ Отдел компьютерной безопасности, Лаборатория информационных технологий (2019-02-01). «Запрос на общественное обсуждение HBS | CSRC с отслеживанием состояния». CSRC | NIST. Получено 2019-02-04.
  2. ^ Бухманн, Йоханнес; Дахмен, Эрик; Хюлсинг, Андреас (2011). «XMSS - Практическая схема прямой безопасной подписи, основанная на минимальных предположениях безопасности». Конспект лекций по информатике. 7071 (Постквантовая криптография. PQCrypto 2011): 117–129. CiteSeerX 10.1.1.400.6086. Дои:10.1007/978-3-642-25405-5_8. ISSN 0302-9743.
  3. ^ Бернштейн, Даниэль Дж .; Хопвуд, Дайра; Хюлсинг, Андреас; Ланге, Таня; Нидерхаген, Рубен; Папахристодулу, Луиза; Шнайдер, Майкл; Швабе, Питер; Уилкокс-О’Хирн, Зуко (2015). Освальд, Элизабет; Фишлин, Марк (ред.). SPHINCS: практические подписи на основе хешей без сохранения состояния. Конспект лекций по информатике. 9056. Springer Berlin Heidelberg. С. 368–397. CiteSeerX 10.1.1.690.6403. Дои:10.1007/978-3-662-46800-5_15. ISBN 9783662467992.
  4. ^ «СФИНКЫ: Введение».
  5. ^ Бухманн, Йоханнес; Дахмен, Эрик; Клинцевич, Елена; Окея, Кацуюки; Вийом, Камилла (2007). «Подписи Меркла с практически неограниченным количеством подписей». Конспект лекций по информатике. 4521 (Прикладная криптография и сетевая безопасность): 31–45. Дои:10.1007/978-3-540-72738-5_3.
  6. ^ Хюлсинг, Андреас; Рауш, Леа; Бухманн, Йоханнес (2013). Оптимальные параметры для XMSSMT. Конспект лекций по информатике. 8128. С. 194–208. Дои:10.1007/978-3-642-40588-4_14. ISBN 978-3-642-40587-7.
  7. ^ Dods, C .; Smart, N.P .; Стам, М. (2005). «Схемы цифровой подписи на основе хеша». Конспект лекций по информатике. 3796 (Криптография и кодирование): 96–115. Дои:10.1007/11586821_8.
  8. ^ а б Хюлсинг, Андреас (2013). W-OTS + - более короткие подписи для схем подписи на основе хеша. Конспект лекций по информатике. 7918. С. 173–188. Дои:10.1007/978-3-642-38553-7_10. ISBN 978-3-642-38552-0.
  9. ^ М. Наор, М. Юнг. «Универсальные односторонние хеш-функции и их криптографические приложения». STOC 1989. [1]
  10. ^ Халкиас, Константинос; Браун, Джеймс; Хирн, Майк; Лиллехаген, Томми; Нитто, Игорь; Шрётер, Томас (2018). "Блокчейн-постквантовые подписи" (PDF). Материалы Международной конференции IEEE по блокчейну (Cybermatics-2018): 1196–1203.
  11. ^ Рейзин, Леонид; Рейзин, Натан (2002). Лучше, чем BiBa: короткие одноразовые подписи с быстрой подписью и проверкой. Конспект лекций по информатике. 2384. С. 144–153. CiteSeerX 10.1.1.24.7320. Дои:10.1007/3-540-45450-0_11. ISBN 978-3-540-43861-8.
  12. ^ Хюлсинг, Андреас; Бутин, Денис; Газдаг, Стефан; Rijneveld, Joost; Мохайсен, Азиз. «RFC 8391 - XMSS: расширенная схема подписи Меркла». tools.ietf.org. IETF.
  13. ^ МакГрю, Дэвид; Курчо, Майкл; Флюрер, Скотт. "RFC 8554 - подписи Лейтон-Микали на основе хэша". tools.ietf.org. IETF.
  14. ^ МакГрю, Дэвид; Кампанакис, Панос; Флюрер, Скотт; Газдаг, Стефан-Лукас; Бутин, Денис; Бухманн, Йоханнес (2016). «Управление состоянием для подписей на основе хеша» (PDF). Конспект лекций по информатике. 10074 (Исследование стандартизации безопасности): 244–260. Дои:10.1007/978-3-319-49100-4_11.
  15. ^ Ван, Личэн; Шэнь, Сяоин; Ли, Цзин; Шао, Цзюнь; Ян, Исянь (01.02.2019). «Криптографические примитивы в блокчейнах». Журнал сетевых и компьютерных приложений. 127: 43–58. Дои:10.1016 / j.jnca.2018.11.003. ISSN 1084-8045.
  16. ^ «Квантово-устойчивый реестр». theqrl.org. 2019-08-24.
  17. ^ «Подписи на основе хеша с отслеживанием состояния NIST» (PDF). NIST. 2019-02-04.
  18. ^ Отдел компьютерной безопасности, Лаборатория информационных технологий (2018-12-20). «Подписи на основе хеша | CSRC». CSRC | NIST. Получено 2019-09-06.
  19. ^ "bcgit / bc-java". GitHub. 2018-12-18.
  20. ^ «СУПЕРКОП». Архивировано из оригинал на 2015-02-15. Получено 2017-05-31.
  21. ^ "Код". Андреас Хюлсинг.
  22. ^ "squareUP> Публикации". www.pqsignatures.org.
  23. ^ Дэвид, МакГрю (2018-05-29). «Пакет hash-sigs: реализация системы иерархической подписи Лейтон-Микали (HSS)». GitHub.
  24. ^ Дэвид, МакГрю (22.11.2018). «Полнофункциональная реализация схем подписи на основе хэша LMS и HSS из draft-mcgrew-hash-sigs-07». GitHub.
  • Т. Ланге. «Подписи на основе хеша». Энциклопедия криптографии и безопасности, Springer, США, 2011. [2]
  • Ф. Т. Лейтон, С. Микали. «Крупные доказуемо быстрые и безопасные схемы цифровой подписи, основанные на одной безопасной хэш-функции». Патент США 5,432,852, [3] 1995.
  • Г. Беккер. «Схемы подписи Меркла, деревья Меркла и их криптоанализ», семинар «Пост квантовая криптология» в Рурском университете Бохума, Германия, 2008 г. [4]
  • Э. Дахмен, М. Дринг, Э. Клинцевич, Дж. Бухманн, Л.С. Коронадо Гарсия. «CMSS - Улучшенная схема подписи Меркла». Прогресс в криптологии - Indocrypt 2006. [5]
  • Р. Меркл. «Системы секретности, аутентификации и открытого ключа / Сертифицированная цифровая подпись». Кандидат наук. диссертация на кафедре электротехники Стэнфордского университета, 1979 г. [6]
  • С. Микали, М. Якобссон, Т. Лейтон, М. Шидло. «Фрактальное представление дерева Меркла и его обход». RSA-CT 03. [7]
  • П. Кампанакис, С. Флюрер. «LMS против XMSS: сравнение предложенных стандартов подписи на основе хеширования с отслеживанием состояния». Cryptology ePrint Archive, Отчет 2017/349. [8]
  • Д. Наор, А. Шенгав, А. Вул. «Повторение об одноразовых подписях: практические быстрые подписи с использованием фрактального обхода дерева Меркла». 24-я конвенция инженеров по электротехнике и радиоэлектронике в Израиле, IEEE, 2006 г. [9]

внешняя ссылка

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