Hash-based cryptography: Difference between revisions

Revision as of 04:48, 6 November 2022

Revision as of 04:02, 3 January 2023

Line 6:

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), 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|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><ref>{{Cite journal |lastlast1=Alagic |firstfirst1=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 |url=https://csrc.nist.gov/publications/detail/nistir/8413/final |language=en}}</ref><ref>{{Cite journal |lastlast1=Cooper |firstfirst1=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 |url=https://csrc.nist.gov/publications/detail/sp/800-208/final |language=en}}</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|lastlast1=Bernstein|firstfirst1=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|editor-link= Elisabeth Oswald |series=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|pages=194–208|doi=10.1007/978-3-642-40588-4_14|language=en|isbn=978-3-642-40587-7}}</ref>

==One-time signature schemes==

Line 41:

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|s2cid=809073 |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==