## Hashed-based signatures## Introduction[Back] Many of the problems we see on the Internet relate to the lack of trust within transactions. The emails you receive and the Web sites that you visit often have very little trust built into them. For trust the email address of the sender, but anyone can fake that address. So increasingly we create a digital signature, and where we sign our messages. In this way, we can check for authentication, integrity and non-repudiation. With the Alice creates a key-pair: a public key and a private key. She then takes a hash of the message, and then encrypts this hash with her private key, and passes the message and the signature to Bob. Bob then reads the message and takes a hash of it. He then decrypts Alice's signature with her public and checks the hashes. If they match, he knows that she signed and that it has not been changed along the way: Currently, we often use RSA, DSA and ECDSA to sign our messages. These are based on the difficulty of finding out the factors of a number and on the processing of discrete logarithms. At the current time these methods are computationally hard problems, but with quantum computers, they become much easier. This was shown by Peter Shor who illustrated that it was possible to crack them in polynomial time. Of all the methods that are being proposed, the hash-based methods look as if they have a good chance of success of creating quantum robust signatures. methods and code-based methods are being researched, but the usage of hashing methods is already well and could provide the best alternative to the existing methods. Hashing methods, too, often bring other advantages, such as forward secure, which means that a key which is cracked will not reveal all the previous keys. ## Merkle treesThe root of hash-based methods isin Merkle trees, and which are a way of hashing is used in many applications, including with Bitcoin, Ethereum, Git distribution systems, No SQL, and in many P2P applications. With a Merkle tree we take our data elements, and then hash them, and take pairs of these hashes to create a new hash, and so we build a table. At the top of the tree is the root element (in this case Hash1234): In this way, we can use the tree to see if we have matching data on systems.On a P2P network, we can transfer a file by splitting it into data segments and then distributing these segments across the network. A trusted source will have the complete Merkle tree for rebuilding the file, and a client can thus rebuild from the Merkle tree and determine the parts of the file which are still missing. Once transferred the root hash (and all the other hashes) will then match. In its core method, the Merkle Signature Scheme (MSS) has serious performance and memory issues, but enhanced methods such as XMSS create with much less of a performance hit. ## One-time signatures (Lamport)The core method used in hash-based signatures is that of the one-time signature, and where we create a new key pair for every method we need to create. If the keys were reused, an attacker could start to learn the private key, and thus spoof messages. One of the first methods was produced by Leslie Lamport and Whitfield Diffie, in 1979, and is defined as: - We create two data sets with 256 random 256-bit numbers (Set A and Set B). These are the private key (512 values).
- we take the hash of each of the random numbers. This will give 512 hashes and will be the public key.
- We then hash the message using and then test each bit of the hash (0 ... 255). If it is a 0, we use the ith number in Set A, else we use the ith number from Set B.
- The signature is then 256 random numbers (taken from either Set A or Set B) and the public key is the 512 hashes (of Set A and Set B).
The public and private keys are then each 16KB in size. A demo of the method is here. Figure 1: Lamport method The major problem with the method is that a key pair for every message. also in 1979, found a solution with Merkle trees. ## One-time signature (W-OTS)To improve performance method (and which reduced key sizes), Merkle proposed Winternitz OTS (named after Robert Winternitz). With this method was possible to sign many bits at the same time. The method is: - We create 32 256-bit random numbers. These 32 values will be our private key.
- We then hash each of these values 256 times. These 32 values will be our public key.
- We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 ... N32).
- Next we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
- To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result for each operation should equal the public key value.
This is illustrated below in Figure 2. A demo of the method is here. Figure 2: W-OTS ## Hash-based SignaturesThe methods such as W-OTS and Lamport only provide for a one-time signature. In order to sign many messages, we can use the Merkel signature scheme (MSS). With this we take a hash of the keys and build these as the leaves of the tree. The root of the tree is then the public key - the verification key. We then just use the private key of the W-OTS method to create the signature. The sender also sends the authentication path, which is the neighbouring nodes within the path and which leads to the root of the tree. The recipient can then rebuild the tree using the verification key (which can be received a digital certificate) and the authentication path. For the next message we move onto another key pair and where the index of the key part is revealed. In the following example we have our root as the public key, and then want to sign with Key3. We then show the authentication path which takes us to the root (as defined in the bold arrows): ## ConclusionsHashed-based methods look to be a strong contender for weaning us off RSA, DSA and ECDSA, but we will have to look at the stateful generation of keys. For this we will have to generate a bank of key pairs (2, 4, 8, 16, etc) and then create the public key from the root of the Merkle tree. We must then remember the keys we have used previously, and only use an unused one. Once we use our new key pair, we then show our working-out as to how the private key is integrated into our tree. It is a bit like a teacher marking a question correctly, and asking for the working out that go you to the answer. |