Hash-based Signatures

Today's challenge

Digital signatures are massively used online, notably for authentication, integrity checking and non-repudiation. The digital signature algorithms most commonly used in practice — RSA, DSA and ECDSA — rely on hardness assumptions about number theoretic problems, namely composite integer factorisation and the computation of discrete logarithms. In 1994, Peter Shor [Sho94] showed that these number theoretic problems would become breakable in the presence of quantum computing. Quantum computers could solve them in polynomial time, compromising the security of the digital signature schemes used today. While quantum computers are not yet available, their development is occurring at a swift pace and therefore constitute a real threat over the next decades. Fortunately, post-quantum cryptography provides a variety of quantum-resistant alternatives to classical digital signature schemes [BBD09]. Hash-based signatures or Merkle signatures as they are also known, are one of the most promising of these alternatives.

Why go hash-based?

There are many reasons to use hash-based signature schemes and to prefer those over other alternatives. While the very early Merkle Signature Scheme lacks of practical performance and space requirements, today's hash-based schemes like XMSS are reasonably fast and yield small signatures. Also the security requirements are compelling. While the security of other post-quantum cryptographic schemes like lattice-based ones is still object to further research, hash-based signatures are well understood. Using a signature scheme always requires a hash function to reduce a message to a small representation of characters that can be signed easily. While other signature schemes rely on additional intractability assumptions to generate a signature, a hash-based solution only needs a secure hash function for the same procedure. Therefore the security of the scheme holds with the hash function used. If the latter one gets compromised, it can be replaced. The underlying Merkle scheme is not affected. Some hash-based schemes even reduce the need for a collision-resistant hash function to one that only needs to withstand attacks on the second-preimage. That given you will get to know about security issues early as attacks in general aim on the stronger security assumption. As an example practical attacks in means of the collision-resistance of the MD5 function are known, but we still do not know about virtual attacks on the second-preimage. With some schemes, other desirable features like forward security are available as well. A scheme being forward secure means that an attacker will not be able to get information about formerly used signature keys by getting hold of the current private key.

One-Time Signatures

Hash-based signatures are based on so-called one-time signatures (OTS). As the term implies, a single key pair must only be used once. Otherwise, an attacker is able to reveal more parts of the private key and spoof signatures. A popular example is the scheme proposed by Leslie Lamport and Whitfield Diffie in 1979 [Lam79]. As one can imagine, this is not very practical. Many key pairs are needed to sign lots of messages, and therefore some kind of key management is required. A solution to cope with this situation was proposed by Ralph Merkle in 1979 [Mer79]. He suggested the use of (binary) hash trees, which are now called Merkle trees. But first, more about one-time signatures: For this kind of signature one generates random data for each case of having a '0' or a '1' representing a single bit of the message. This is the private key. The public key represents the hashed version for each of the random data blocks. To sign a message, the private key data for each bit is revealed, depending on the single message bit being '0' or '1'. A verifier can calculate the hashes and compare them to the public key. Here one notices that generating a second signature would tell more about the private key and allow an attacker to forge further signatures. Therefore a single key pair must only be used once. To improve performance and reduce space requirements, Merkle proposed the Winternitz OTS, named after Robert Winternitz. The basic idea of the Winternitz OTS is to sign several bits at once.

Here you can see the Lamport-Diffie scheme (example message 001) following McGrew's visualisation (link to NIST):

Hash-based Signatures

To overcome the key management problem of one-time signature key pairs, Merkle proposed the use of hash trees. In the Merkel signature scheme (MSS), verification keys are hashed and build the leaves of the tree. Neighbouring children are concatenated and then hashed to build the parent node. The root of the tree represents the public key of the scheme. A signature is generated by applying the private key of an OTS scheme. The corresponding verification key is handed on to the receiver of the message along with the signature. The verifier also has to be told about neighbouring nodes on the path to the root of the MSS tree, which is referred to as the authentication path. Using that information, the receiver can verify the signature and use the verification key to build the leave and reach the root of the tree using the authentication path. The root is already known to the verifier as the public key, which he obtained earlier, for example via a certificate. For each new signature generated the next key pair must be used. As one can see, this scheme is stateful. For example, the index of the used key pair — respectively leaf — of the MSS tree must be stored. This is a whole new situation in the use of cryptographic schemes. Due to slow runtimes, as well as large key and signature sizes, this scheme was not used in practice since other schemes like RSA were known and easier to implement. But as the need for post-quantum cryptography has arisen, the interest in hash-based signatures led to renewed interest in those schemes and significant improvements occurred over the last years. Signature generation is much faster thanks to the use of pseudo-random number generators, the construction of large is trees is easier thanks to multi-tree proposals and many more contributions have been made. In 2011, Andreas Hülsing introduced XMSS [BH11], a hash-based signatures scheme based on minimal security assumptions [Hül13]. This scheme and its multi-tree variant XMSS^MT are the most advanced approaches for practical hash-based signatures.

A list of literature on hash-based signatures can be found on Andreas Hülsing's Website.

A summer school lecture on hash-based signatures by Johannes Buchmann and Andreas Hülsing can be found on Youtube provided by the Institute for Quantum Computing, University of Waterloo.

Here you can see an XMSS tree following Andreas Hülsing [Hül13]:

New Challenges

To introduce hash-based signature schemes to today's cryptographic infrastructure, a few drawbacks must be overcome. This does not mean there are barriers one cannot manage, but issues that just have not arose so far and have to be dealt with and thought about now. Particularly statefulness has to be handled. Private keys of e.g. RSA are stateless. They can easily be used. It's possible to have several copies, no matter whether you allow access for several process for example talking about a TLS-server handling hundreds of connections or whether you want to make backups of your key. Due to the statefulness of hash-based schemes, private keys become a critical resource. Also any kind of copy is a security threat as an attacker could get hold of an old key state and forge signatures. Another aspect are interfaces to cryptographic software like TLS libraries. Those are sometimes not prepared to deal with changing keys. Furthermore, issues emerging from the integration with a public key infrastructure (PKI) such as key distribution and revocation must be addressed.