From Lamport and Merkle to a Post Quantum World … Meet SPHINCS+
From Lamport and Merkle to a Post Quantum World … Meet SPHINCS+
And 43 years of research, in-between
The building of a more trusted digital world must involve the usage of digital signing, and where Alice uses her private key to sign for a message, and then Bob proves that she is the signer of the message. One method we can use for this is hash-based signatures.
I love doing research, and especially love when new methods borrow from previous ones, and where we end up applying a range of methods into an optimized solution. When researchers start with a problem, they often do not see what the final solution will be that they will solve. The work of hash-based signatures is a good example, and where researchers such as Lamport and Merkle were searching for solutions in creating digital signatures for public key methods, but their methods are now applied to post-quantum cryptography methods.
Lamport
In 1979, it was Leslie Lamport who defined a method for one-time signatures:
- 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.
Problem: 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 the 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.
Hash to Obtain Random Subset (HORS)
Hash to Obtain Random Subset (HORS) is a quantum robust hashed-based one-time signature. With this, we create a series of integers for our private keys and organise them into an indexable form. Then we hash them to a sequence of public key values. Next, we segment the hash of the message into a series of n-bit integer values. The signature is then achieved through a look-up of the value in the public key list. If we assume that we are going to segment the hash into 8-bit values and for a 128-bit hash (using MD5), the method is then:
- Create 256 random values. These are our private key values (priv0…priv255).
- Hash each of the private key values to produce a list of our public key values pub. These will be indexed.
- Hash the message (M) for a 128-bit hash (h), and which will produce 16 8-bit values (hi).
- Take each of the values (hi) and use as a look-up to the public key value.
If Bob creates the public key and the private key, then he creates the message, and then adds the hash-based signatures. He then shows Alice the message and the message, and his public key. Bob then shows that he has the associated private key for this public. He cannot use this key pair again, so will produce a new key pair for the next signature.
Figure 3 illustrates a simple example and a demonstrator is here.
Merkle trees
The root of hash-based methods is in 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 — such as in Figure 4— we take our data elements. We then hash them, and take pairs of these hashes to create a new hash, and build a table. At the top of the tree is the root element (in this case Root), and which is the hash of H1 and H2. H2 is then the hash of H5 and H6, and so on. We can then publish Root, but not reveal any of the other hashes. This root hash will prove that we know all of the other hashes.
If we want to reveal H7 as a private key, we would then publish the route from H7 up to the Root. As a core method, the Merkle Signature Scheme (MSS) has serious performance and memory issues, but enhanced methods such as XMSS [2] have a much less of a performance hit. In 2018, it was standardized within RFC 8391 [3]:
Problem: XMSS is stateful, and where we need to remember the private keys we have used to sign a message, and not reuse them. This was addressed by SPHINCS [4], and which used the main methods of XMSS, but eliminated the state.
SPHINCS+
Within SPHINCS+, we authenticate a large number of few-time signature (FTS) key pairs within a hypertree — and which is a tree of hash-based many-time signatures (MTS). With the hypertree we have d layers, and where a key pair at the top of layer d-1 signs N public keys in layer d-2, and which sign for N key pairs at layer d-3, and so on. We then get N.d authenticated FTS key pairs. To authenticate an FTS key pair, we build a path from the FTS key pair to the top of the MTS tree (Figure 5).
The public key is then the root hash. Along with this, we have a public seed value. For 128-bit private keys (16 bytes), the public key becomes twice this size and will a 256-bit value (32 bytes). The three main security levels are for Level 1 (128-bit), Level 3 (192-bit) and Level 5 (256-bit):
Method Public key Private key Signature size
--------------------------------------------------------------------
SPHINCS+ SHA-256 128-bit 32 64 17,088
SPHINCS+ SHA-256 192-bit 48 96 35,664
SPHINCS+ SHA-256 256-bit 64 128 49,856
These levels produce different signatures sizes, such as around 17KB for a 128-bit SPHINC+ signature. An example of a 128-bit signature is:
Private key (seed): 73b7aaecc201f3d2e66f2f1fc61c81f5
Private key: (prf) 0661f344ed690384644e603c04cced6a
Private key: (pkseed) f379c4994981f97ca1ebf3198ea67bab
Private key: (pkroot) e62fb13db8ccd136a8d6c7139d11144f
Public key (seed): f379c4994981f97ca1ebf3198ea67bab
Public key (root): e62fb13db8ccd136a8d6c7139d11144f
For a 256-bit signature, we can see that the public key has 32 bytes (64 hex characters) and that the private key has 64 bytes (128 hex characters).
Private key (seed): 9adabc4056cde6a8dbb3e3480b2e2a558d6d88a665cf5e253b4607f2b19dfdd7
Private key: (prf) 0996e238fd27837a8fe671f97b864f2e8d14b973a90b7f7b4dc5bbd223b6167e
Private key: (pkseed) 12bbac3b599a9dd13fa537a40738495516aa7ed8b2c4eecabe8a8e35e4e17dd1
Private key: (pkroot) 935b59896cf5997fcbb814b0a41341652a3da76771671d533ed3ac2c785a5f61
Public key (seed): 12bbac3b599a9dd13fa537a40738495516aa7ed8b2c4eecabe8a8e35e4e17dd1
Public key (root): 935b59896cf5997fcbb814b0a41341652a3da76771671d533ed3ac2c785a5f61
The public key thus contains the root node and a public seed, whereas the private key just has a single secret seed value.
SPHINCS to SPHINCS+
Figure 6 [6] provides an overview of a two-layer infrastructure. While the original paper on SPHINCS [4] provided the core foundation for the framework, it has been enhanced over the last few years to produce SPHINCS+. One of the major changes is to use FORS (Forest of Random Subsets) and which replaces a HORST key pair. It also included SPHINCS+-’robust’ and SPHINCS+-’simple’ methods. The simple methods are faster, but have weaker security levels than robust.
SPHINC+ also uses a tweakable hash function [7]. It involves a public seed PK.seed, along with context information — ADRS (Address Scheme):
Coding
The coding is [here]:
And a sample run (and which does not include the XMSS signatures and authentication values) [here]:
SPHINCS+ Parameters
N=32, W=16, Hprime=4, H=68, D=17, K=35, T=512, LogT=9, A=9
Private key (seed): 9adabc4056cde6a8dbb3e3480b2e2a558d6d88a665cf5e253b4607f2b19dfdd7
Private key: (prf) 0996e238fd27837a8fe671f97b864f2e8d14b973a90b7f7b4dc5bbd223b6167e
Private key: (pkseed) 12bbac3b599a9dd13fa537a40738495516aa7ed8b2c4eecabe8a8e35e4e17dd1
Private key: (pkroot) 935b59896cf5997fcbb814b0a41341652a3da76771671d533ed3ac2c785a5f61
Public key (seed): 12bbac3b599a9dd13fa537a40738495516aa7ed8b2c4eecabe8a8e35e4e17dd1
Public key (root): 935b59896cf5997fcbb814b0a41341652a3da76771671d533ed3ac2c785a5f61
Signature verified
Bad signature failed to verify
R = 2f25b2c95fe6b04bd4e0710a01acb21b628e5c0cba780b212f333c862af3e058 (Length=64)
Showing [SK, Auth]
[a3760b3f6f8ecaaab72e8b5eef56c743, 7c8c1d35ee8c1a0589cff5e5b457612a]
[852cccf416a8bf2f882b42717237700d, 20f4a3ed39d1b30a47fb61d5ec8a8d70]
[a0ef31f68a1fad061f2c06577df9e01d, b7d8c73f657c90ae507df84d36850f0f]
[2c573689413bc8e05ffa4f7bc9556105, 20744f7e4d68635385ff46b2e8d16688]
[a3b9cab0188c4163a2e0f7acb26b81d3, 2db32663b719daa84ad5f21e426cbbf0]
[8e77ac104a5a3b774b230553dfe1e331, 7b6b31cf7b7c116c52543259bfa5fff7]
[e94147b759f7165f3ff03d8d076e9407, 93f3f28535562a3aad8e953381fa48cb]
[851d2e4df7e1c291d6ec5a93e6b397e7, c69001039fe0aa4f0b9d69a5d8978a88]
[e70613f384856eb57172af910b3145ca, 9353d9c4d53a19a4d72f895f4ec0574e]
[005fb0d23f57d350ac9f69cc57d9f607, 7d01ce6168f63de05ed76786baac7850]
[8fae8f97a60bff88119ca2e17bb88287, 065f2ffed593d140a95a9063d24f3809]
[705aeed6212fb3a0d72a50d6409188f2, 10288c96b13a6d00edc7f14720b5d429]
[61aa53ca39281a544eed6fcbcb7206ab, b9c35527abaa9b2a7f0c3e03dc5b3a01]
[b92744d470a9924afe68b9d2cae77027, 7187dd96ebebe62e6cbf4cb40670b6b3]
[b7bb6a4dec857af6ad869b8ca72e5646, c7dd2c536df3dd9a07256b2117d28451]
[f34ba817f9203cfbec90bae346232a7e, f4e4193de6dcb7736f1e0b68b737c17c]
[8d5fc8190bb2791244cc1a2928f16bc2, 59275796eb7678cd531e636c770732fe]
[16710bfccda6063783cd963e5a9d6489, d5c99a2769098618683d1779500b0e47]
[78fae376579c6b8d17c2003b128c8c03, 92e22fa8ec1a54a199cc4930f5ad9655]
[6ad92ad591bb559b49d63ef75d0877ed, cf0423ff90c9b4dee4227fb66a7e81f7]
[d4fb998e291d947ac639cf65a2f760ac, 71d247e5044f4d4756faacec20e5b220]
[6c7cb13079831996b0bd8e22b3eb13e9, 53207c4d547465be2cc894742a296373]
[10e793a32b147a29a8a0feee90f29a61, 81cecf30c52f3e401dcba629eb972ad9]
[36757d5a249ac006a406b17cad6bf328, 0770c9986018b7342ad397fb49c80289]
[628bb40bf654a925f0c24c99ee5d0313, 9d5b5ad96ff29898a1d30a594d9e8759]
[a6e5ba28a4675f95ea8cda6004be01ef, 233cf8373a052c0652ac9b455fd46b64]
[8008f4d0c3063b56a71995b94b51625d, e3a25eff9efdb9f9621e9347f88315cb]
[f49f94ee62c2fc053222c802d94d2a94, 7ca039de91be7232e6871ec94cc9b71d]
[2b01a530e887d9e42153af24e6584aa7, 76b9db5140895fcc8f7353970b0dd523]
[084bc0f9a16d83afc7c01203d6ff9fe4, 4acd4e6d8aa2844d9446239af5e4b739]
[6a44131b8e131e18f1751f129358c589, 9a2f0cc8a44533350b7fed8e42ea404b]
[8f4edd2664078bd35229c55ee5e15d50, 0540df29838ff8a501f6b0980fd11828]
[a0ea6c6ab59376db20809c6339c1a519, 1ef5dee4c96f5069aa43977061443130]
[9f93c0281127f8c46a503019bbb935a1, 3f79e02a702a005c523d7de4839e19a5]
[b3bf784a43cbd0521a4b173f61383abc, 704b5f437897a56bbce5310eb65180ac]
Conclusions
It started in 1979, and 43 years later we see SPHINCS+ being approved by NIST as a future standard for digital signatures within PQC (Post Quantum Cryptography). SPHINCS+ [5] is a perfect example of a method which has adopted the best research methods as it has evolved, and squeezed out every last little bit of efficiency. So, here it is:
https://asecuritysite.com/pqc/sp
References
[1] Lamport, L. (1979). Constructing digital signatures from a one-way function (Vol. 238). Technical Report CSL-98, SRI International. [paper]
[2] Buchmann, J., Dahmen, E., & Hülsing, A. (2011, November). XMSS-a practical forward secure signature scheme based on minimal security assumptions. In International Workshop on Post-Quantum Cryptography (pp. 117–129). Springer, Berlin, Heidelberg.
[3] Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., & Mohaisen, A. (2018). XMSS: extended Merkle signature scheme (No. rfc8391).
[4] Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., … & Wilcox-O’Hearn, Z. (2015, April). SPHINCS: practical stateless hash-based signatures. In Annual international conference on the theory and applications of cryptographic techniques (pp. 368–397). Springer, Berlin, Heidelberg.
[5] Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., & Schwabe, P. (2019, November). The SPHINCS+ signature framework. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security (pp. 2129–2146).
[6] Castelnovi, L., Martinelli, A., & Prest, T. (2018, April). Grafting trees: a fault attack against the SPHINCS framework. In International Conference on Post-Quantum Cryptography (pp. 165–184). Springer, Cham.