Meet The Standard of the Future … SPHINCS+
Meet The Signature Standard of the Future … SPHINCS+
Daniel J Bernstein (djb) has contributed so much to cryptography, and in building a more trusted world. His research has created ChaCha20, Salsa20, Curve 25519, twisted elliptic curves, AES timing attacks, and so much more. But of his contributions is now ready to make an impact within a Post Quantum Cryptography (PQC) world: the SPHINCS+ signature framework [here][1]:
And so last week, it was one of the three PQC methods that are defined for digital signatures (alongside Dilithium and Falcon).
So while most hash-based methods suffer from having to remember the private keys which have signed previous messages, SPHINCS+ is a stateless hash-based signature scheme. It was proposed by Bernstein et al. in 2015 [paper].
SPHINCS+ key and signature sizes
Overall, SPHINCS+ produces a small public key (32 bytes, 48 bytes or 64 bytes), and a small private key (64 bytes, 96 bytes or 128 bytes). The signature size is larger with 17,088 bytes for a 128-bit signature [here]:
In terms of performance, it does not perform as well as Dilithium, but it has reasonable levels of performance for key generation, key signing and key verification:
Hash-based trees
It uses WOTS and FORS for hash-based trees and uses a number of parameters:
- n — length of hash in WOTS / FORS (Forest Of Random Subsets) (in bits)
- m — length of message hash (in bits)
- h — height of the hyper-tree
- d — layers of the hyper-tree
- w — Winternitz parameter used for WOTS signature
- t—leaves in the FORS tree (2^t is no. of secret-key elements)
- k — number of trees in FORS signature
In the example we use: n=256, m=512, h=2, d=1, w=4, t=8, k=64.
The hashing method used in some of the operations is BLAKE, and ChaCha is used to generate a random number.
Winternitz one time signature scheme (W-OTS)
W-OTS uses relatively small key and signatures sizes, and is thought to be quantum robust. It generates 32×256 bit random private keys. We then have these a number of times, and is defined by a parameter (w). If we use w=8, we hash the private keys by (2w). This creates 32×256 bits public keys. The signature is the created by taking eight bits at a time, and then the 8-bit binary int (n) is subtracted from 256 and the private key is the hashed 256-n times. The signature is then 32 hashes which are derived from random private keys. To verify the signature, the recipient parses the hash of the signature (using 8 bits at a time, and extracting the 8 bit int, n).
The method is:
- Initially 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).
- For the signature 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:
A sample run which just shows the first few private key and the first public keys:
Hashing number: 256
==== Private key (keep secret) =====
Priv[0]: bd344c6110628aa38c9b5ca6458bed7b78425b2e82efa0624a578031562f82ee
Priv[1]: 20670af5b1663fa9fad49fab6a692ae5989cff77439f98d2288f173b17a8d99f
Priv[2]: 625aa290fd1f88c930451ff743d5d9ef90e7064368fb23a18c9fd048474818f2
Priv[3]: ee0e1363cbd5f61017ba27bfe91ec53969d28d143ed59a99efb020941bc4990f
Priv[4]: ce94d7282ee3f7b05b99768695ff224b5994900c6182dfb89d596d8b7b405ec6
Priv[5]: d0c59651e951b0bb8d5a2d7b93f6739c9ce4a0c0c0f63bfce23b331b947eb285
==== Public key (show everyone)=====
Pub[0]: 45fdac6339e80cadd1331cce026cd0364ea84146a36f6f3f2449b66fb55a217a
Pub[1]: 184cf92f22072fef078fa4a93ec2044f07ac8b12e326509474209312cace8a5a
Pub[2]: a47548d4537bd284e7d7f935f41570866d9c6a72c463bb2a2b10c8c7907621f0
Pub[3]: 60395e575522cacb70d866211c64e8a74e562c79d1fffce224d1013d088bf66f
Pub[4]: 8be7b53d5b56e698b8798f2a707fba7b8e417554fd489d74cc40fe8574d7589e
Pub[5]: 9fac35971dae3a5c77ae7b5c720a72f90ee53852668c96c78e095cbb52af20a1
==== Message to sign ===============
Message: The quick brown fox jumps over the lazy dog
SHA-256: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]: 45cb53c5c33af9b20426fd0233fd63d92bf0c2ded367163e6f2f93588a33c6d8
Sign[1]: e8c35987101f2d11d7056a2fe78069d3ed73aee315ebef8c2d40e04973301c26
Sign[2]: 59220d80b7c958957b28511f4081341cc4a00a0d6d5e1d05351be7dec3ca8aaa
Sign[3]: 72a906d719be18e1592314bf6f6c521a325a9de2b5b9e9e13117bf01b0157f5c
The signature test is True
A demonstration of the method is given here.
Implementation
The following is an implementation of SPHINCS+ [here]:
A sample run of SPHINCS+ SHA256-256f-Robust shows that the public key size is 32 bytes, the secret key is 64 bytes [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] (only showing the first eight bytes)
Size of SK is 16 bytes, Size of Auth is 288 bytes
[a3760b3f6f8ecaaab72e8b5eef56c743, 7c8c1d35ee8c1a0589cff5e5b457612a]
[852cccf416a8bf2f882b42717237700d, 20f4a3ed39d1b30a47fb61d5ec8a8d70]
...
[b3bf784a43cbd0521a4b173f61383abc, 704b5f437897a56bbce5310eb65180ac]
With SPHINCS+ SHA256–256f-robust, , we have K=35 (the number of revealed secret-key elements per HORST signature), and so we end up with 35 [SK, Auth] values. Each of these has a secret key of 16 bytes , and 288 bytes for each authentication for each key. We thus have 10,640 bytes for this. We also have the WOTS signature and authentication values, and will end up with a signature of around 49KB:
SPHINCS+-SHA256-256f-robust
claimed-nist-level 5
claimed-security EUF-CMA
length-public-key 64
length-secret-key 128
length-signature 49856
This is security level 5, and which is equivalent to AES 256-bit security levels. A lower level of security is for SPHINCS+ SHA256–128s-simple. This has Level 1 security (equivalent to 128-bit AES) and which creates a 7.8KB signature:
SPHINCS+-SHA256-128s-simple
claimed-nist-level 1
claimed-security EUF-CMA
length-public-key 32
length-secret-key 64
length-signature 7856
Here is the demo:
https://asecuritysite.com/pqc/sp
If you are interested, there’s more PQC here:
Reference
[1] 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) [paper].