Hash-based cryptography: Difference between revisions

Revision as of 03:52, 18 April 2020

Revision as of 05:33, 24 June 2020

Line 1:

'''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 limited to [[digital signature]]s schemes such as the [[Merkle signature scheme]]. Hash-based signature schemes combine a one-time signature scheme 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. [[Lamport signature]]s are an example of a one-time signature scheme that can be combined with a Merkle tree structure.

In 2019, the US [[National Institute of Standards and Technology]] announced its intention to promulgate standards for stateful hash-based cryptography based on the [[eXtended Merkle Signature Scheme]] (XMSS) and [[Leighton-Micali Signatures]] (LMS), which are applicable in different circumstances.<ref>{{Cite web|url=https://csrc.nist.gov/news/2019/stateful-hbs-request-for-public-comments|title=Request for Public Comments on Stateful HBS {{!}} CSRC|last=Computer Security Division|first=Information Technology Laboratory|date=2019-02-01|website=CSRC {{!}} NIST|language=EN-US|access-date=2019-02-04}}</ref>

==History==

[[Leslie Lamport]] invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme)<ref name="BuchmannDahmen2011">{{cite journal|last1=Buchmann|first1=Johannes|last2=Dahmen|first2=Erik|last3=Hülsing|first3=Andreas|title=XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions|journal=Lecture Notes in Computer Science|volume=7071|pages=117–129|issue=Post-Quantum Cryptography. PQCrypto 2011|year=2011|issn=0302-9743|doi=10.1007/978-3-642-25405-5_8|citeseerx=10.1.1.400.6086}}</ref> and SPHINCS<ref>{{Cite book|issue=Advances in Cryptology -- EUROCRYPT 2015|last=Bernstein|first=Daniel J.|last2=Hopwood|first2=Daira|last3=Hülsing|first3=Andreas|last4=Lange|first4=Tanja|author4-link=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=SPHINCS: practical stateless hash-based signatures|year=2015|publisher=Springer Berlin Heidelberg|isbn=9783662467992|editor-last=Oswald|editor-first=Elisabeth|journal=Lecture Notes in Computer Science|volume=9056|pages=368–397|language=en|doi=10.1007/978-3-662-46800-5_15|editor-last2=Fischlin|editor-first2=Marc|citeseerx = 10.1.1.690.6403}}</ref><ref>{{cite 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>{{cite journal|last1=Buchmann|first1=Johannes|last2=Dahmen|first2=Erik|last3=Klintsevich|first3=Elena|last4=Okeya|first4=Katsuyuki|last5=Vuillaume|first5=Camille|title=Merkle Signatures with Virtually Unlimited Signature Capacity|journal=Lecture Notes in Computer Science|date=2007|volume=4521|issue=Applied Cryptography and Network Security|pages=31–45|doi=10.1007/978-3-540-72738-5_3|language=en}}</ref>. A multi-tree variant of XMSS, XMSS^''MT'', was described in 2013.<ref>{{cite book|last1=Hülsing|first1=Andreas|last2=Rausch|first2=Lea|last3=Buchmann|first3=Johannes|title=Optimal Parameters for XMSSMT|journal=Lecture Notes in Computer Science|date=2013|volume=8128|issue=Security Engineering and Intelligence Informatics|pagepages=194–208|doi=10.1007/978-3-642-40588-4_14|language=en|isbn=978-3-642-40587-7}}</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>{{cite journal|last1=Dods|first1=C.|last2=Smart|first2=N. P.|last3=Stam|first3=M.|title=Hash Based Digital Signature Schemes|issue=Cryptography and Coding|journal=Lecture Notes in Computer Science|volume=3796|date=2005|pages=96–115|doi=10.1007/11586821_8|language=en}}</ref> and its improvements, such as the W-OTS⁺ scheme.<ref name="wotsplus">{{cite book|last1=Hülsing|first1=Andreas|title=W-OTS+ — Shorter Signatures for Hash-Based Signature Schemes|journal=Lecture Notes in Computer Science|date=2013|volume=7918|issue=Progress in Cryptology – AFRICACRYPT 2013|pages=173–188|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 24:

Some hash-based signature schemes use multiple layers of tree, offering faster signing at the price of larger signatures. In such schemes, only the lowest layer of trees is used to sign messages, while all other trees sign root values of lower trees.

The Naor-Yung work<ref>M. Naor, M. Yung. "Universal One-Way Hash Functions and their Cryptographic Applications". STOC 1989. [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/uowhf.pdf] </ref> shows the pattern by which to transfer a limited time signature of the Merkle type family into an unlimited (regular) signature scheme.

==Properties of hash-based signature schemes==

Line 34:

==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>{{cite 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|title=Blockchained Post-Quantum Signatures|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, LMS signatures, while 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>{{cite book|last1=Reyzin|first1=Leonid|last2=Reyzin|first2=Natan|title=Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying|journal=Lecture Notes in Computer Science|date=2002|volume=2384|issue=Information Security and Privacy|pagepages=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>{{cite web|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|publisher=IETF|language=en}}</ref>.

Leighton-Micali Hash-Based Signatures are specified in [[Request for Comments|RFC]] 8554.<ref>{{cite web|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|publisher=IETF|language=en}}</ref> Practical improvements have been proposed in the literature that alleviate the concerns introduced by stateful schemes.<ref>{{cite journal|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=State Management for Hash-Based Signatures|journal=Lecture Notes in Computer Science|date=2016|volume=10074|issue=Security Standardisation Research|pages=244–260|doi=10.1007/978-3-319-49100-4_11|url=https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf|language=en}}</ref> Hash functions appropriate for these schemes include [[SHA-2]], [[SHA-3]] and [[BLAKE (hash function)|BLAKE]].

==Implementations==

Unlike other popular [[Blockchain|blockchain networks]] and [[Cryptocurrency|cryptocurrencies]] that use already [[NIST]] standardized Elliptic Curve Digital Signature Algorithms ([[Elliptic Curve Digital Signature Algorithm|ECDSA]]),<ref>{{Cite journal|last=Wang|first=Licheng|last2=Shen|first2=Xiaoying|last3=Li|first3=Jing|last4=Shao|first4=Jun|last5=Yang|first5=Yixian|date=2019-02-01|title=Cryptographic primitives in blockchains|url=http://www.sciencedirect.com/science/article/pii/S108480451830362X|journal=Journal of Network and Computer Applications|volume=127|pages=43–58|doi=10.1016/j.jnca.2018.11.003|issn=1084-8045|doi-access=free}}</ref>, The Quantum Resistant Ledger (QRL) is the first [[Open-source software|open source]] network to implement eXtended Merkle Signature Scheme.<ref>{{cite web|url=https://theqrl.org/|title=The Quantum Resistant Ledger|date=2019-08-24|website=theqrl.org|language=en}}</ref>. In contrast to traditional ECDSA signatures, this stateful signature scheme is provably resistant to a sufficiently powerful quantum computer running [[Shor's algorithm|Shor’s algorithm]].<ref>{{cite web|title=NIST Stateful Hash-Based Signatures|url=https://csrc.nist.gov/CSRC/media/Projects/Stateful-Hash-Based-Signatures/documents/stateful-HBS-public-comments-June2018-rfi.pdf|website=NIST|language=en|date=2019-02-04}}</ref><ref>{{Cite web|url=https://csrc.nist.gov/Projects/Stateful-Hash-Based-Signatures|title=Hash-Based Signatures {{!}} CSRC|last=Computer Security Division|first=Information Technology Laboratory|date=2018-12-20|website=CSRC {{!}} NIST|language=EN-US|access-date=2019-09-06}}</ref>

The XMSS, GMSS and SPHINCS schemes are available in the Java [[Bouncy Castle (cryptography)|Bouncy Castle]] cryptographic APIs.<ref>{{cite web|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|date=2018-12-18}}</ref> SPHINCS is implemented in the SUPERCOP benchmarking toolkit.<ref>{{cite web|title=SUPERCOP|url=http://bench.cr.yp.to/supercop.html|access-date=2017-05-31|archive-url=https://web.archive.org/web/20150215055126/http://bench.cr.yp.to/supercop.html|archive-date=2015-02-15|url-status=dead}}</ref> Optimised<ref>{{cite web|title=Code|url=https://huelsing.wordpress.com/code/|website=Andreas Hülsing}}</ref> and unoptimised<ref>{{cite 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>{{cite web|last1=David|first1=McGrew|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>{{cite web|last1=David|first1=McGrew|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.

Line 61:

{{Cryptography navbox}}

[[Category:Hash-based cryptography| ]]

[[Category:Post-quantum cryptography]]

[[Category:Public-key cryptography]]