Hash-based cryptography: Difference between revisions

Revision as of 16:45, 8 June 2024

Latest revision as of 05:01, 24 August 2025

(12 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Concept in cryptography}}

'''Hash-based cryptography''' is the generic term for constructions of [[cryptographic primitive]]s based on the security of [[hash function]]s. It is of interest as a type of [[post-quantum cryptography]].

So far, hash-based cryptography is used to construct [[digital signature]]s schemes such as the [[Merkle signature scheme]], zero knowledge and computationally integrity proofs, such as the zk-STARK<ref name="bensasson2018">Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018. [https://eprint.iacr.org/2018/046 Scalable, transparent, and post-quantum secure computational integrity].</ref> proof system and range proofs over issued credentials via the HashWires<ref name="kchalkias2021">{{Cite journal |last1=Chalkias |first1=Konstantinos |last2=Cohen |first2=Shir |last3=Lewi |first3=Kevin |last4=Moezinia |first4=Fredric |last5=Romailler |first5=Yolan |year=2021 |title=HashWires: Hyperefficient Credential-Based Range Proofs |url=https://eprint.iacr.org/2021/297 |journal=Privacy Enhancing Technologies Symposium (PETS) 2021}}</ref> protocol. Hash-based signature schemes combine a one-time signature scheme, such as a [[Lamport signature]], with a [[Merkle tree]] structure. Since a one-time signature scheme key can only sign a single message securely, it is practical to combine many such keys within a single, larger structure. A Merkle tree structure is used to this end. In this hierarchical data structure, a hash function and concatenation are used repeatedly to compute tree nodes.

</ref> proof system and range proofs over issued credentials via the HashWires<ref name="kchalkias2021">{{cite journal |last1=Chalkias |first1=Konstantinos |last2=Cohen |first2=Shir |last3=Lewi |first3=Kevin |last4=Moezinia |first4=Fredric |last5=Romailler |first5=Yolan |year=2021 |title=HashWires: Hyperefficient Credential-Based Range Proofs |url=https://eprint.iacr.org/2021/297 |journal=Privacy Enhancing Technologies Symposium (PETS) 2021}}</ref> protocol. Hash-based signature schemes combine a one-time signature scheme, such as a [[Lamport signature]], with a [[Merkle tree]] structure. Since a one-time signature scheme key can only sign a single message securely, it is practical to combine many such keys within a single, larger structure. A Merkle tree structure is used to this end. In this hierarchical data structure, a hash function and concatenation are used repeatedly to compute tree nodes.

One consideration with hash-based signature schemes is that they can only sign a limited number of messages securely, because of their use of one-time signature schemes. The US [[National Institute of Standards and Technology]] (NIST), specified that algorithms in its [[post-quantum cryptography]] competition support a minimum of 2{{Superscript|64}} signatures safely.<ref>{{Cite web |title=Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process |url=https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf |website=NIST CSRC}}</ref>

In 2022, NIST announced [[SPHINCS+]] as one of three algorithms to be standardized for digital signatures.<ref>{{Cite web |date=2022-07-05 |title=NIST announces four quantum-resistant algorithms |url=https://venturebeat.com/2022/07/05/nist-post-quantum-cryptography-standard/ |access-date=2022-07-10 |website=VentureBeat |language=en-US}}</ref> NIST standardized stateful hash-based cryptography based on the [[eXtended Merkle Signature Scheme]] (XMSS) and [[Leighton–Micali Signatures]] (LMS),<ref name="rfc8554" /> which are applicable in different circumstances, in 2020, but noted that the requirement to maintain state when using them makes them more difficult to implement in a way that avoids misuse.<ref>{{Cite web |urllast=Computer Security Division |first=Information Technology Laboratory |date=https://csrc.nist.gov/news/2019/stateful-hbs02-request-for-public-comments01 |title=Request for Public Comments on Stateful HBS {{!}} CSRC|last=Computer Security Division|firsturl=Informationhttps://csrc.nist.gov/news/2019/stateful-hbs-request-for-public-comments Technology Laboratory|access-date=2019-02-0104 |website=CSRC {{!}} NIST |language=EN-US|access-date=2019-02-04}}</ref><ref>{{Cite journal |last1=Alagic |first1=Gorjan |last2=Apon |first2=Daniel |last3=Cooper |first3=David |last4=Dang |first4=Quynh |last5=Dang |first5=Thinh |last6=Kelsey |first6=John |last7=Lichtinger |first7=Jacob |last8=Miller |first8=Carl |last9=Moody |first9=Dustin |last10=Peralta |first10=Rene |last11=Perlner |first11=Ray |date=2022-07-05 |title=Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process |doi=10.6028/NIST.IR.8413-upd1 |url=https://csrc.nist.gov/publications/detail/nistir/8413/final |journal=NIST Ir 8413 |language=en |doi=10.6028/NIST.IR.8413-upd1|doi-access=free }}</ref><ref>{{Cite journal |last1=Cooper |first1=David |last2=Apon |first2=Daniel |last3=Dang |first3=Quynh |last4=Davidson |first4=Michael |last5=Dworkin |first5=Morris |last6=Miller |first6=Carl |date=2020-10-29 |title=Recommendation for Stateful Hash-Based Signature Schemes |doi=10.6028/NIST.SP.800-208 |url=https://csrc.nist.gov/publications/detail/sp/800-208/final |journal=NIST Special Publication 800-208 |language=en |doi=10.6028/NIST.SP.800-208}}</ref>

In 2022, NIST announced [[SPHINCS+]] as one of three algorithms to be standardized for digital signatures.<ref>{{Cite web |date=2022-07-05 |title=NIST announces four quantum-resistant algorithms |url=https://venturebeat.com/2022/07/05/nist-post-quantum-cryptography-standard/ |access-date=2022-07-10 |website=VentureBeat |language=en-US}}</ref> and in 2024 NIST announced the Stateless Hash-Based Digital Signature Standard (SLH-DSA)<ref>{{Cite journal |date=August 2024 |title=Stateless Hash-Based Digital Signature Standard |url=https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.pdf |website=[[NIST.gov]] |doi=10.6028/NIST.FIPS.205}}</ref> based on SPHINCS+.

== History ==

[[Leslie Lamport]] invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme)<ref name="BuchmannDahmen2011">{{citeCite book |last1=Buchmann |first1=Johannes |title=Post-Quantum Cryptography |last2=Dahmen |first2=Erik |last3=Hülsing |first3=Andreas |year=2011 |isbn=978-3-642-25404-8 |series=Lecture Notes in Computer Science |volume=7071 |pages=117–129 |chapter=XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions |citeseerx=10.1.1.400.6086 |doi=10.1007/978-3-642-25405-5_8 |issn=0302-9743}}</ref> and SPHINCS<ref>{{Cite book |last1=Bernstein |first1=Daniel J. |title=Advances in Cryptology -- EUROCRYPT 2015 |last2=Hopwood |first2=Daira |last3=Hülsing |first3=Andreas |last4=Lange |first4=Tanja |author4author-linklink4=Tanja Lange |last5=Niederhagen |first5=Ruben |last6=Papachristodoulou |first6=Louiza |last7=Schneider |first7=Michael |last8=Schwabe |first8=Peter |last9=Wilcox-O’Hearn |first9=Zooko|title=Advances in Cryptology -- EUROCRYPT 2015 |chapterpublisher=SPHINCS:Springer PracticalBerlin Stateless Hash-Based SignaturesHeidelberg |year=2015|publisher=Springer Berlin Heidelberg|isbn=9783662467992 |editor-last=Oswald |editor-first=Elisabeth |editor-link= Elisabeth Oswald |series=Lecture Notes in Computer Science |volume=9056 |pages=368–397 |language=en |chapter=SPHINCS: Practical Stateless Hash-Based Signatures |citeseerx=10.1.1.690.6403 |doi=10.1007/978-3-662-46800-5_15 |editor-last2=Fischlin |editor-first2=Marc|citeseerx = 10.1.1.690.6403}}</ref><ref>{{citeCite web |title=SPHINCS: Introduction |url=http://sphincs.cr.yp.to/}}</ref> hash-based signature schemes were introduced in 2011 and 2015, respectively. XMSS was developed by a team of researchers under the direction of [[Johannes Buchmann]] and is based both on Merkle's seminal scheme and on the 2007 Generalized Merkle Signature Scheme (GMSS).<ref>{{citeCite book |last1=Buchmann |first1=Johannes |title=Applied Cryptography and Network Security |last2=Dahmen |first2=Erik |last3=Klintsevich |first3=Elena |last4=Okeya |first4=Katsuyuki |last5=Vuillaume |first5=Camille |titledate=Applied Cryptography and Network Security2007 |chapterisbn=Merkle Signatures with Virtually Unlimited Signature Capacity978-3-540-72737-8 |series=Lecture Notes in Computer Science |date=2007|volume=4521 |pages=31–45 |language=en |chapter=Merkle Signatures with Virtually Unlimited Signature Capacity |doi=10.1007/978-3-540-72738-5_3|isbn=978-3-540-72737-8 |language=en|doi-access=free}}</ref> A multi-tree variant of XMSS, XMSS^''MT'', was described in 2013.<ref>{{citeCite book |last1=Hülsing |first1=Andreas |title=Security Engineering and Intelligence Informatics |last2=Rausch |first2=Lea |last3=Buchmann |first3=Johannes |titledate=Security Engineering and Intelligence Informatics2013 |chapterisbn=Optimal Parameters for XMSS MT978-3-642-40587-7 |series=Lecture Notes in Computer Science |date=2013|volume=8128 |pages=194–208 |language=en |chapter=Optimal Parameters for XMSS MT |doi=10.1007/978-3-642-40588-4_14|languagechapter-url=en|isbn=978https://hal.inria.fr/hal-3-642-40587-701506577 }}</ref>

== One-time signature schemes ==

Hash-based signature schemes use one-time signature schemes as their building block. A given one-time signing key can only be used to sign a single message securely. Indeed, signatures reveal part of the signing key. The security of (hash-based) one-time signature schemes relies exclusively on the security of an underlying hash function.

Commonly used one-time signature schemes include the [[Lamport signatures|Lamport–Diffie scheme]], the Winternitz scheme<ref>{{citeCite book |last1=Dods |first1=C. |title=Cryptography and Coding |last2=Smart |first2=N. P. |last3=Stam |first3=M. |titledate=Cryptography and Coding2005 |chapterisbn=Hash Based Digital Signature Schemes978-3-540-30276-6 |series=Lecture Notes in Computer Science |volume=3796|date=2005 |pages=96–115 |language=en |chapter=Hash Based Digital Signature Schemes |doi=10.1007/11586821_8|isbn=978-3-540-30276-6 |language=en}}</ref> and its improvements, such as the W-OTS⁺ scheme.<ref name="wotsplus">{{citeCite book |last1last=Hülsing |first1first=Andreas |title=Progress in Cryptology – AFRICACRYPT 2013 |chapterdate=W-OTS+2013 – Shorter Signatures for Hash|isbn=978-Based Signature Schemes3-642-38552-0 |series=Lecture Notes in Computer Science |date=2013|volume=7918 |pages=173–188 |chapter=W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes |doi=10.1007/978-3-642-38553-7_10|isbn=978-3-642-38552-0}}</ref> Unlike the seminal Lamport–Diffie scheme, the Winternitz scheme and variants can sign many bits at once. The number of bits to be signed at once is determined by a value: the Winternitz parameter. The existence of this parameter provides a trade-off between size and speed. Large values of the Winternitz parameter yield short signatures and keys, at the price of slower signing and verifying. In practice, a typical value for this parameter is 16.

In the case of stateless hash-based signatures, few-time signature schemes are used. Such schemes allow security to decrease gradually in case a few-time key is used more than once. HORST is an example of a few-time signature scheme.

Line 37 ⟶ 39:

== Examples of hash-based signature schemes ==

Since Merkle's initial scheme, numerous hash-based signature schemes with performance improvements have been introduced. Recent ones include the XMSS, the Leighton–Micali (LMS), the SPHINCS and the BPQS schemes. Most hash-based signature schemes are [[State (computer science)|stateful]], meaning that signing requires updating the secret key, unlike conventional digital signature schemes. For stateful hash-based signature schemes, signing requires keeping state of the used one-time keys and making sure they are never reused. The XMSS, LMS and BPQS<ref>{{citeCite journal |last1=Chalkias |first1=Konstantinos |last2=Brown |first2=James |last3=Hearn |first3=Mike |last4=Lillehagen |first4=Tommy |last5=Nitto |first5=Igor |last6=Schroeter |first6=Thomas |year=2018 |title=Blockchained Post-Quantum Signatures |url=https://eprint.iacr.org/2018/658.pdf |journal=Proceedings of the IEEE International Conference on Blockchain (Cybermatics-2018) |pages=1196–1203|year=2018|url=https://eprint.iacr.org/2018/658.pdf}}</ref> schemes are stateful, while the SPHINCS scheme is stateless. SPHINCS signatures are larger than XMSS and LMS signatures. BPQS has been designed specifically for blockchain systems. Additionally to the WOTS+ one-time signature scheme,<ref name="wotsplus" /> SPHINCS also uses a few-time (hash-based) signature scheme called HORST. HORST is an improvement of an older few-time signature scheme, HORS (Hash to Obtain Random Subset).<ref>{{citeCite book |last1=Reyzin |first1=Leonid |title=Information Security and Privacy |last2=Reyzin |first2=Natan |titledate=Information2002 Security|isbn=978-3-540-43861-8 and|series=Lecture PrivacyNotes in Computer Science |volume=2384 |pages=144–153 |language=en |chapter=Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying |seriesciteseerx=Lecture Notes in Computer Science10.1.1.24.7320 |date=2002|volume=2384|pages=144–153|doi=10.1007/3-540-45450-0_11|language=en|isbn=978-3-540-43861-8|citeseerx=10.1.1.24.7320}}</ref>

The stateful hash-based schemes XMSS and XMSS^''MT'' are specified in [[Request for Comments|RFC]] 8391 (XMSS: eXtended Merkle Signature Scheme).<ref>{{citeCite journal |last1=Hülsing |first1=Andreas |last2=Butin |first2=Denis |last3=Gazdag |first3=Stefan |last4=Rijneveld |first4=Joost |last5=Mohaisen |first5=Aziz |date=May 2018 |title=RFC 8391 – XMSS: eXtended Merkle Signature Scheme |url=https://tools.ietf.org/html/rfc8391 |websitelanguage=tools.ietf.org|date=May 2018en |publisher=IETF |languagewebsite=entools.ietf.org}}</ref> Leighton–Micali Hash-Based Signatures are specified in [[Request for Comments|RFC]] 8554.<ref name="rfc8554">{{citeCite journal |last1=McGrew |first1=David |last2=Curcio |first2=Michael |last3=Fluhrer |first3=Scott |date=April 2019 |title=RFC 8554 – Leighton–Micali Hash-Based Signatures |url=https://tools.ietf.org/html/rfc8554 |websitelanguage=tools.ietf.org|date=April 2019en |publisher=IETF |languagewebsite=entools.ietf.org}}</ref> Practical improvements have been proposed in the literature that alleviate the concerns introduced by stateful schemes.<ref>{{citeCite book |last1=McGrew |first1=David |title=Security Standardisation Research |last2=Kampanakis |first2=Panos |last3=Fluhrer |first3=Scott |last4=Gazdag |first4=Stefan-Lukas |last5=Butin |first5=Denis |last6=Buchmann |first6=Johannes |titledate=Security Standardisation Research2016 |chapterisbn=State Management for Hash978-Based Signatures3-319-49099-1 |series=Lecture Notes in Computer Science |date=2016|volume=10074 |pages=244–260 |language=en |chapter=State Management for Hash-Based Signatures |doi=10.1007/978-3-319-49100-4_11|isbn=978-3-319-49099-1 |s2cid=809073 |chapter-url=https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf |archive-url=https://web.archive.org/web/20170818214629/https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf|url-status=dead |archive-date=2017-08-18 |languageurl-status=endead |s2cid=809073}}</ref> Hash functions appropriate for these schemes include [[SHA-2]], [[SHA-3]] and [[BLAKE (hash function)|BLAKE]].

The stateless hash-based scheme SLH-DSA is specified in [https://doi.org/10.6028/NIST.FIPS.205 FIPS-205].

The stateful hash-based schemes XMSS and XMSS^''MT'' are specified in [[Request for Comments|RFC]] 8391 (XMSS: eXtended Merkle Signature Scheme).<ref>{{cite journal|last1=Hülsing|first1=Andreas|last2=Butin|first2=Denis|last3=Gazdag|first3=Stefan|last4=Rijneveld|first4=Joost|last5=Mohaisen|first5=Aziz|title=RFC 8391 – XMSS: eXtended Merkle Signature Scheme|url=https://tools.ietf.org/html/rfc8391|website=tools.ietf.org|date=May 2018 |publisher=IETF|language=en}}</ref> Leighton–Micali Hash-Based Signatures are specified in [[Request for Comments|RFC]] 8554.<ref>{{cite journal|last1=McGrew|first1=David|last2=Curcio|first2=Michael|last3=Fluhrer|first3=Scott|title=RFC 8554 – Leighton–Micali Hash-Based Signatures|url=https://tools.ietf.org/html/rfc8554|website=tools.ietf.org|date=April 2019 |publisher=IETF|language=en}}</ref> Practical improvements have been proposed in the literature that alleviate the concerns introduced by stateful schemes.<ref>{{cite book|last1=McGrew|first1=David|last2=Kampanakis|first2=Panos|last3=Fluhrer|first3=Scott|last4=Gazdag|first4=Stefan-Lukas|last5=Butin|first5=Denis|last6=Buchmann|first6=Johannes|title=Security Standardisation Research |chapter=State Management for Hash-Based Signatures |series=Lecture Notes in Computer Science |date=2016|volume=10074|pages=244–260|doi=10.1007/978-3-319-49100-4_11|isbn=978-3-319-49099-1 |s2cid=809073 |chapter-url=https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf|archive-url=https://web.archive.org/web/20170818214629/https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf|url-status=dead|archive-date=2017-08-18|language=en}}</ref> Hash functions appropriate for these schemes include [[SHA-2]], [[SHA-3]] and [[BLAKE (hash function)|BLAKE]].

== Implementations ==

The XMSS, GMSS and SPHINCS schemes are available in the Java [[Bouncy Castle (cryptography)|Bouncy Castle]] cryptographic APIs.<ref>{{citeCite web |date=2018-12-18 |title=bcgit/bc-java |url=https://github.com/bcgit/bc-java/tree/master/core/src/main/java/org/bouncycastle/pqc/crypto |website=GitHub |language=en}}</ref> LMS<ref>{{Cite web |date=20182024-1206-18 |title=wolfCrypt implementations of LMS/HSS and XMSS/XMSS^MT signatures: build options and benchmarks (Intel x86) |url=https://www.wolfssl.com/wolfcrypt-implementations-of-lms-hss-and-xmss-xmssmt-signatures-build-options-and-benchmarks-intel-x86/ |website=wolfSSL |language=en}}</ref> and XMSS schemeschemes isare available in the [[wolfSSL]] cryptographic APIs.<ref>{{citeCite web |date=2023-11-22 |title=wolfSSL/wolfssl |url=https://github.com/wolfSSL/wolfssl/blob/master/wolfssl/wolfcrypt/lms.h |website=GitHub |language=en|date=2023-11-22}}</ref> SPHINCS is implemented in the SUPERCOP benchmarking toolkit.<ref>{{citeCite web |title=SUPERCOP |url=http://bench.cr.yp.to/supercop.html |accessurl-datestatus=2017-05-31dead |archive-url=https://web.archive.org/web/20150215055126/http://bench.cr.yp.to/supercop.html |archive-date=2015-02-15 |urlaccess-statusdate=dead2017-05-31}}</ref> Optimised<ref>{{citeCite web |title=Code |url=https://huelsing.wordpress.com/code/ |url-status=dead |archive-url=https://web.archive.org/web/20170822224019/https://huelsing.wordpress.com/code/ |archive-date=2017-08-22 |access-date=2017-05-31 |website=Andreas Hülsing}}</ref> and unoptimised<ref>{{citeCite web |title=squareUP > Publications |url=http://www.pqsignatures.org/index/publications.html#code |website=www.pqsignatures.org |language=en-gb}}</ref> reference implementations of the XMSS RFC exist. The LMS scheme has been implemented in Python<ref>{{citeCite web |last1last=David |first1first=McGrew |date=2018-05-29 |title=The hash-sigs package: an implementation of the Leighton–Micali Hierarchical Signature System (HSS). |url=https://github.com/davidmcgrew/hash-sigs/ |website=GitHub |language=en|date=2018-05-29}}</ref> and in C<ref>{{citeCite web |last1last=David |first1first=McGrew |date=2018-11-22 |title=A full-featured implementation of the LMS and HSS Hash Based Signature Schemes from draft-mcgrew-hash-sigs-07. |url=https://github.com/cisco/hash-sigs |website=GitHub |language=en|date=2018-11-22}}</ref> following its Internet-Draft.

== References ==

Line 48 ⟶ 52:

* T. Lange. "Hash-Based Signatures". Encyclopedia of Cryptography and Security, Springer U.S., 2011. [https://link.springer.com/referenceworkentry/10.1007%2F978-1-4419-5906-5_413]

* F. T. Leighton, S. Micali. "Large provably fast and secure digital signature schemes based one secure hash functions". US Patent 5,432,852, [https://patents.google.com/patent/US5432852] 1995.

* G. Becker. "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis", seminar 'Post Quantum Cryptology' at the Ruhr-University Bochum, Germany, 2008. [https://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf] {{Webarchive|url=https://web.archive.org/web/20170830030943/http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |date=2017-08-30 }}

* E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L. C. Coronado Garcia. "CMSS — An Improved Merkle Signature Scheme". Progress in Cryptology – Indocrypt 2006. [https://eprint.iacr.org/2006/320.pdf]

* R. Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. [http://www.merkle.com/papers/Thesis1979.pdf] {{Webarchive|url=https://web.archive.org/web/20180814211110/http://www.merkle.com/papers/Thesis1979.pdf |date=2018-08-14 }}

* S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal Merkle Tree Representation and Traversal". RSA-CT 03. [https://link.springer.com/chapter/10.1007/3-540-36563-X_21]

* P. Kampanakis, S. Fluhrer. "LMS vs XMSS: A comparison of the Stateful Hash-Based Signature Proposed Standards". Cryptology ePrint Archive, Report 2017/349. [http://eprint.iacr.org/2017/349.pdf]

* D. Naor, A. Shenhav, A. Wool. "One-Time Signatures Revisited: Practical Fast Signatures Using Fractal Merkle Tree Traversal". IEEE 24th Convention of Electrical and Electronics Engineers in Israel, 2006. [https://www.eng.tau.ac.il/~yash/Naor_Shenhav_Wool.pdf] {{Webarchive|url=https://web.archive.org/web/20180205043107/http://www.eng.tau.ac.il/~yash/Naor_Shenhav_Wool.pdf |date=2018-02-05 }}

== External links ==