Hash-based cryptography

Last updated

Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.

Contents

So far, hash-based cryptography is used to construct digital signatures schemes such as the Merkle signature scheme, zero knowledge and computationally integrity proofs, such as the zk-STARK [1] proof system and range proofs over issued credentials via the HashWires [2] 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 264 signatures safely. [3]

In 2022, NIST announced SPHINCS+ as one of three algorithms to be standardized for digital signatures. [4] NIST standardized stateful hash-based cryptography based on the eXtended Merkle Signature Scheme (XMSS) and Leighton–Micali Signatures (LMS), [5] 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. [6] [7] [8]

In 2024 NIST announced the Stateless Hash-Based Digital Signature Standard. [9]

History

Leslie Lamport invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme) [10] and SPHINCS [11] [12] 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). [13] A multi-tree variant of XMSS, XMSSMT, was described in 2013. [14]

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–Diffie scheme, the Winternitz scheme [15] and its improvements, such as the W-OTS+ scheme. [16] 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.

Combining many one-time key pairs into a hash-based signature scheme

The central idea of hash-based signature schemes is to combine a larger number of one-time key pairs into a single structure to obtain a practical way of signing more than once (yet a limited number of times). This is done using a Merkle tree structure, with possible variations. One public and one private key are constructed from the numerous public and private keys of the underlying one-time scheme. The global public key is the single node at the very top of the Merkle tree. Its value is an output of the selected hash function, so a typical public key size is 32 bytes. The validity of this global public key is related to the validity of a given one-time public key using a sequence of tree nodes. This sequence is called the authentication path. It is stored as part of the signature, and allows a verifier to reconstruct the node path between those two public keys.

The global private key is generally handled using a pseudo-random number generator. It is then sufficient to store a seed value. One-time secret keys are derived successively from the seed value using the generator. With this approach, the global private key is also very small, e.g. typically 32 bytes.

The problem of tree traversal is critical to signing performance. Increasingly efficient approaches have been introduced, dramatically speeding up signing time.

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 [17] 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

Hash-based signature schemes rely on security assumptions about the underlying hash function, but any hash function fulfilling these assumptions can be used. As a consequence, each adequate hash function yields a different corresponding hash-based signature scheme. Even if a given hash function becomes insecure, it is sufficient to replace it by a different, secure one to obtain a secure instantiation of the hash-based signature scheme under consideration. Some hash-based signature schemes (such as XMSS with pseudorandom key generation) are forward secure, meaning that previous signatures remain valid if a secret key is compromised.

The minimality of security assumptions is another characteristic of hash-based signature schemes. Generally, these schemes only require a secure (for instance in the sense of second preimage resistance) cryptographic hash function to guarantee the overall security of the scheme. This kind of assumption is necessary for any digital signature scheme; however, other signature schemes require additional security assumptions, which is not the case here.

Because of their reliance on an underlying one-time signature scheme, hash-based signature schemes can only sign a fixed number of messages securely. In the case of the Merkle and XMSS schemes, a maximum of messages can be signed securely, with the total Merkle tree height.

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 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 [18] 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, [16] 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). [19]

The stateful hash-based schemes XMSS and XMSSMT are specified in RFC 8391 (XMSS: eXtended Merkle Signature Scheme). [20] Leighton–Micali Hash-Based Signatures are specified in RFC 8554. [5] Practical improvements have been proposed in the literature that alleviate the concerns introduced by stateful schemes. [21] Hash functions appropriate for these schemes include SHA-2, SHA-3 and BLAKE.

Implementations

The XMSS, GMSS and SPHINCS schemes are available in the Java Bouncy Castle cryptographic APIs. [22] LMS [23] and XMSS schemes are available in the wolfSSL cryptographic APIs. [24] SPHINCS is implemented in the SUPERCOP benchmarking toolkit. [25] Optimised [26] and unoptimised [27] reference implementations of the XMSS RFC exist. The LMS scheme has been implemented in Python [28] and in C [29] following its Internet-Draft.

Related Research Articles

<span class="mw-page-title-main">Digital signature</span> Mathematical scheme for verifying the authenticity of digital documents

A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.

<span class="mw-page-title-main">Daniel J. Bernstein</span> American mathematician, cryptologist and computer scientist (born 1971)

Daniel Julius Bernstein is an American mathematician, cryptologist, and computer scientist. He was a visiting professor at CASA at Ruhr University Bochum until 2024, as well as a research professor of Computer Science at the University of Illinois at Chicago. Before this, he was a visiting professor in the department of mathematics and computer science at the Eindhoven University of Technology.

Articles related to cryptography include:

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, a Lamport signature or Lamport one-time signature scheme is a method for constructing a digital signature. Lamport signatures can be built from any cryptographically secure one-way function; usually a cryptographic hash function is used.

A hash chain is the successive application of a cryptographic hash function to a piece of data. In computer security, a hash chain is a method used to produce many one-time keys from a single key or password. For non-repudiation, a hash function can be applied successively to additional pieces of data in order to record the chronology of data's existence.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions support important standards of post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

In hash-based cryptography, the Merkle signature scheme is a digital signature scheme based on Merkle trees and one-time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 1970s and is an alternative to traditional digital signatures such as the Digital Signature Algorithm or RSA. NIST has approved specific variants of the Merkle signature scheme in 2020.

The following outline is provided as an overview of and topical guide to cryptography:

Linked timestamping is a type of trusted timestamping where issued time-stamps are related to each other.

Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms that are currently thought to be secure against a cryptanalytic attack by a quantum computer. Most widely-used public-key algorithms rely on the difficulty of one of three mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.

A hash calendar is a data structure that is used to measure the passage of time by adding hash values to an append-only database with one hash value per elapsed second. It can be thought of special kind of Merkle or hash tree, with the property that at any given moment, the tree contains a leaf node for each second since 1970‑01‑01 00:00:00 UTC.

In cryptography, server-based signatures are digital signatures in which a publicly available server participates in the signature creation process. This is in contrast to conventional digital signatures that are based on public-key cryptography and public-key infrastructure. With that, they assume that signers use their personal trusted computing bases for generating signatures without any communication with servers.

BLISS is a digital signature scheme proposed by Léo Ducas, Alain Durmus, Tancrède Lepoint and Vadim Lyubashevsky in their 2013 paper "Lattice Signature and Bimodal Gaussians".

Post-Quantum Cryptography Standardization is a program and competition by NIST to update their standards to include post-quantum cryptography. It was announced at PQCrypto 2016. 23 signature schemes and 59 encryption/KEM schemes were submitted by the initial submission deadline at the end of 2017 of which 69 total were deemed complete and proper and participated in the first round. Seven of these, of which 3 are signature schemes, have advanced to the third round, which was announced on July 22, 2020.

ATHENE, formerly Center for Research in Security and Privacy (CRISP), is the national research center for IT security and privacy in Germany and the largest research center for IT security in Europe. The research center is located in Darmstadt and deals with key issues of IT security in the digitization of government, business and society.

In post-quantum cryptography, NewHope is a key-agreement protocol by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist quantum computer attacks.

<span class="mw-page-title-main">Johannes Buchmann</span> German mathematician (born 1953)

Johannes Alfred Buchmann is a German computer scientist, mathematician and professor emeritus at the department of computer science of the Technische Universität Darmstadt.

<span class="mw-page-title-main">Commercial National Security Algorithm Suite</span> Set of cryptographic algorithms by the NSA

The Commercial National Security Algorithm Suite (CNSA) is a set of cryptographic algorithms promulgated by the National Security Agency as a replacement for NSA Suite B Cryptography algorithms. It serves as the cryptographic base to protect US National Security Systems information up to the top secret level, while the NSA plans for a transition to quantum-resistant cryptography.

References

  1. ↑ Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018. Scalable, transparent, and post-quantum secure computational integrity.
  2. ↑ Chalkias, Konstantinos; Cohen, Shir; Lewi, Kevin; Moezinia, Fredric; Romailler, Yolan (2021). "HashWires: Hyperefficient Credential-Based Range Proofs". Privacy Enhancing Technologies Symposium (PETS) 2021.
  3. ↑ "Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process" (PDF). NIST CSRC.
  4. ↑ "NIST announces four quantum-resistant algorithms". VentureBeat. 2022-07-05. Retrieved 2022-07-10.
  5. 1 2 McGrew, David; Curcio, Michael; Fluhrer, Scott (April 2019). "RFC 8554 – Leighton–Micali Hash-Based Signatures". tools.ietf.org. IETF.
  6. ↑ Computer Security Division, Information Technology Laboratory (2019-02-01). "Request for Public Comments on Stateful HBS | CSRC". CSRC | NIST. Retrieved 2019-02-04.
  7. ↑ Alagic, Gorjan; Apon, Daniel; Cooper, David; Dang, Quynh; Dang, Thinh; Kelsey, John; Lichtinger, Jacob; Miller, Carl; Moody, Dustin; Peralta, Rene; Perlner, Ray (2022-07-05). "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process". NIST IR 8413. doi:10.6028/NIST.IR.8413-upd1.
  8. ↑ Cooper, David; Apon, Daniel; Dang, Quynh; Davidson, Michael; Dworkin, Morris; Miller, Carl (2020-10-29). "Recommendation for Stateful Hash-Based Signature Schemes". NIST Special publication 800-208. doi:10.6028/NIST.SP.800-208.
  9. ↑ "Stateless Hash-Based Digital Signature Standard" (PDF). NIST.gov . August 2024. doi:10.6028/NIST.FIPS.205.
  10. ↑ Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). "XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions". Post-Quantum Cryptography. Lecture Notes in Computer Science. Vol. 7071. pp. 117–129. CiteSeerX   10.1.1.400.6086 . doi:10.1007/978-3-642-25405-5_8. ISBN   978-3-642-25404-8. ISSN   0302-9743.
  11. ↑ Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter; Wilcox-O’Hearn, Zooko (2015). "SPHINCS: Practical Stateless Hash-Based Signatures". In Oswald, Elisabeth; Fischlin, Marc (eds.). Advances in Cryptology -- EUROCRYPT 2015. Lecture Notes in Computer Science. Vol. 9056. Springer Berlin Heidelberg. pp. 368–397. CiteSeerX   10.1.1.690.6403 . doi:10.1007/978-3-662-46800-5_15. ISBN   9783662467992.
  12. ↑ "SPHINCS:Introduction".
  13. ↑ Buchmann, Johannes; Dahmen, Erik; Klintsevich, Elena; Okeya, Katsuyuki; Vuillaume, Camille (2007). "Merkle Signatures with Virtually Unlimited Signature Capacity". Applied Cryptography and Network Security. Lecture Notes in Computer Science. Vol. 4521. pp. 31–45. doi: 10.1007/978-3-540-72738-5_3 . ISBN   978-3-540-72737-8.
  14. ↑ Hülsing, Andreas; Rausch, Lea; Buchmann, Johannes (2013). "Optimal Parameters for XMSS MT". Security Engineering and Intelligence Informatics. Lecture Notes in Computer Science. Vol. 8128. pp. 194–208. doi:10.1007/978-3-642-40588-4_14. ISBN   978-3-642-40587-7.
  15. ↑ Dods, C.; Smart, N. P.; Stam, M. (2005). "Hash Based Digital Signature Schemes". Cryptography and Coding. Lecture Notes in Computer Science. Vol. 3796. pp. 96–115. doi:10.1007/11586821_8. ISBN   978-3-540-30276-6.
  16. 1 2 Hülsing, Andreas (2013). "W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes". Progress in Cryptology – AFRICACRYPT 2013. Lecture Notes in Computer Science. Vol. 7918. pp. 173–188. doi:10.1007/978-3-642-38553-7_10. ISBN   978-3-642-38552-0.
  17. ↑ M. Naor, M. Yung. "Universal One-Way Hash Functions and their Cryptographic Applications". STOC 1989. .
  18. ↑ Chalkias, Konstantinos; Brown, James; Hearn, Mike; Lillehagen, Tommy; Nitto, Igor; Schroeter, Thomas (2018). "Blockchained Post-Quantum Signatures" (PDF). Proceedings of the IEEE International Conference on Blockchain (Cybermatics-2018): 1196–1203.
  19. ↑ Reyzin, Leonid; Reyzin, Natan (2002). "Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying". Information Security and Privacy. Lecture Notes in Computer Science. Vol. 2384. pp. 144–153. CiteSeerX   10.1.1.24.7320 . doi:10.1007/3-540-45450-0_11. ISBN   978-3-540-43861-8.
  20. ↑ Hülsing, Andreas; Butin, Denis; Gazdag, Stefan; Rijneveld, Joost; Mohaisen, Aziz (May 2018). "RFC 8391 – XMSS: eXtended Merkle Signature Scheme". tools.ietf.org. IETF.
  21. ↑ McGrew, David; Kampanakis, Panos; Fluhrer, Scott; Gazdag, Stefan-Lukas; Butin, Denis; Buchmann, Johannes (2016). "State Management for Hash-Based Signatures" (PDF). Security Standardisation Research. Lecture Notes in Computer Science. Vol. 10074. pp. 244–260. doi:10.1007/978-3-319-49100-4_11. ISBN   978-3-319-49099-1. S2CID   809073. Archived from the original (PDF) on 2017-08-18.
  22. ↑ "bcgit/bc-java". GitHub. 2018-12-18.
  23. ↑ "wolfCrypt implementations of LMS/HSS and XMSS/XMSS^MT signatures: build options and benchmarks (Intel x86)". wolfSSL. 2024-06-18.
  24. ↑ "wolfSSL/wolfssl". GitHub. 2023-11-22.
  25. ↑ "SUPERCOP". Archived from the original on 2015-02-15. Retrieved 2017-05-31.
  26. ↑ "Code". Andreas Hülsing. Archived from the original on 2017-08-22. Retrieved 2017-05-31.
  27. ↑ "squareUP > Publications". www.pqsignatures.org.
  28. ↑ David, McGrew (2018-05-29). "The hash-sigs package: an implementation of the Leighton–Micali Hierarchical Signature System (HSS)". GitHub.
  29. ↑ David, McGrew (2018-11-22). "A full-featured implementation of the LMS and HSS Hash Based Signature Schemes from draft-mcgrew-hash-sigs-07". GitHub.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.