A Long Goodbye to RSA and ECDSA, and Quick Hello to SLH-DSA
Small Keys, But Larger Signatures, and no Haraka hashes
There are two NIST-approved PQC (Post Quantum Cryptography) alternatives for digital signatures. One uses the “darling” lattice method (Dilithium), and the other uses good old hash-based signatures (SPHINCS+). Some, though, worry that the Learning With Error (LWE) approach of lattice methods might be cracked at some time in the future, and so NIST wants alternatives, and one of the most robust from a security point-of-view is hash-based signatures. So let’s meet the might SLH-DSA (aka SPHINCS+) method.
Introduction
Well, as if cybersecurity doesn’t have enough acronyms. There’s RIP, OSPF, TCP, IP, SSH, AES, and so many others. Now, there are three really important ones to remember: ML-KEM (Module Lattice-Based Key Encapsulation Mechanism), ML-DSA (Module Lattice-Based Signature Standard) and SLH-DSA (Stateless Hash-based Digital Signature Standard). ML-KEM is defined in the FIPS 203 standard, ML-DSA is FIPS 204, and for SLH-DSA, we have FIPS 205.
Many, though, would recognise ML-KEM as CRYSTALS-Kyber, ML-DSA as CRYSTALS Dilithium and SLH-DSA as the SPHINCS+ method. And, so, on the 13th of August 2024, FIPS 204 was born [here]:
and, on the same day, NIST published FIPS 205 [here]:
And also FIPS 203 [here]:
At present, there is only one replacement for our key exchange methods: ML-KEM, and two replacements for digital signatures (eg RSA, ECDSA and EdDSA): ML-DSA and SLH-DSA. Both ML-KEM and ML-DSA are lattice-based, while SLH-DSA uses a hash-based signature approach, which is stateless.
SLH-DSA
With this, we have a number of private keys, and which can then be hashed within a Merkle Tree to produce a root public key signature. The problem with this method is that we cannot reuse one of our private keys, as we have shown the path it takes to get to the root public key. For this, SPHINCS+ converts the method into a stateless method, and uses trees of hashes.
SPHINCS+ was one of the winners in the NIST standard for PQC (Post Quantum Cryptography), was proposed by Bernstein et al. in 2015 and updated in [2]. SPHINCS+ 256 128-bit has a public key size of 32 bytes, a private key size of 64 bytes, and a signature of 17KB. It has now been standardized by NIST as FIPS 205, and can be used with SHA-256 or SHAKE-256. These include SLH-DSA-SHAKE-128f and SLH-DSA-SHA2–128f.
The following provides an analysis of the PCQ methods for digital signing:
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
RSA-2048 256 256 256
ECC 256-bit 64 32 256
Crystals Dilithium 2 1,312 2,528 2,420 1 (128-bit) Lattice
Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice
Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice
SLH-DSA-SHA2-128f 32 64 17,088 1 (128-bit) Hash-based
SLH-DSA-SHA2-192f 48 96 35,664 3 (192-bit) Hash-based
SLH-DSA-SHA2-256f 64 128 49,856 5 (256-bit) Hash-basedWe can see that the public and private key are small, with only 32 bytes for the public key and 64 bytes for the private key for SLH-DSA-SHA2–128f. This is much smaller than Dilithium (ML-DSA-512). But the digital signature is larger, with 17,088 bytes against 2,420 for the equivalent Dilithium signature.
For stack memory size on an ARM Cortex-M4 device [1] and measured in bytes:
Method Key generation Sign Verify
----------------------------------------------------------------
Crystals Dilithium 2 (Lattice) 36,424 61,312 40,664
Crystals Dilithium 3 50,752 81,792 55,000
Crystals Dilithium 5 67,136 104,408 71,472
Falcon 512 (Lattice) 1,680 2,484 512
Falcon 1024 1,680 2,452 512
SLH-DSA-SHA2-128f 2,192 2,248 2,544
SLH-DSA-SHA2-192f 3,512 3,640 3,872
SLH-DSA-SHA2-256f 5,600 5,560 5,184For code size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Memory (Bytes)
-------------------------------------------------
Crystals Dilithium 2 (Lattice) 13,948
Crystals Dilithium 3 13,756
Crystals Dilithium 5 13,852
Falcon 512 (Lattice) 117,271
Falcon 1024 157,207
Sphincs SHA256-128f Simple 4,668
Sphincs SHA256-192f Simple 4,676
Sphincs SHA256-256f Simple 5,084For performance, it is much slower than ML-DSA (Dilithium) for key generation, signing and verification [here]:
Overall, the Haraka hashing method is the fastest but has not been approved as a FIPS standard. The two main standards use the NIST-approved hashes of SHA2 and SHAKE. Overall, there are two main methods for signing: a “pure” version (slh_sign) and a “pre-hash” version (hash_slh_sign). With the pre-hash version, we hash the message before it is sent for signature. This means that there is less data to deal with for the signature and can thus reduce the computational load on the signing application.
Code
We can install SHLDSA with [here]:
pip install slh-dsaThe code to implement this is [here]:
from slhdsa import KeyPair, sha2_128s,sha2_128f, sha2_192s, sha2_192f, sha2_256s, sha2_256f, shake_128s, shake_128f, shake_192s, shake_192f, shake_256s, shake_256f, PublicKey
import binascii
import sys
para=shake_256f
message='Hello'
method='sha2_128s';
if (len(sys.argv)>1):
message=str(sys.argv[1])
if (len(sys.argv)>2):
method=str(sys.argv[2])
if (method=='sha2_128s'): para=sha2_128s
elif (method=='sha2_128f'): para=sha2_128f
elif (method=='sha2_192s'): para=sha2_192s
elif (method=='sha2_192f'): para=sha2_192f
elif (method=='sha2_256s'): para=sha2_256s
elif (method=='sha2_256f'): para=sha2_256f
elif (method=='shake_128s'): para=shake_128s
elif (method=='shake_128f'): para=shake_128f
elif (method=='shake_192s'): para=shake_192s
elif (method=='shake_192f'): para=shake_192f
elif (method=='shake_256s'): para=shake_256s
elif (method=='shake_256f'): para=shake_256f
kp = KeyPair.gen(para)
sig = kp.sign(message.encode())
rtn=kp.verify(message.encode(), sig)
print(f"Message: {message}")
print(f"Method: {method}\n")
rtn=kp.verify(b"In correct message",sig)
print("\nBad signature valid: ",rtn)
print("Signature (first 32 bytes): ",binascii.hexlify(sig[:32]))
print(f"Signature length: {len(sig)} bytes")
print("Signature valid: ",rtn)
print("Privte key size: ",len(kp.sec.key[0]*2))
print("Public key size: ",len(kp.pub.key[0]))A sample run with SHA2–128f gives [here]:
Message: Post Quantum Crypto
Method: sha2_128f
Private key size: 32
Public key size: 16
Signature (first 32 bytes): b'b1ecc5b25c8ee52ba0d42de7684e56c544e2ec64ae42f93be654d98f6925c918'
Signature length: 17088 bytes
Signature valid: True
Bad signature valid: FalseA sample run with SHA2–256f gives [here]:
Message: Post Quantum Crypto
Method: sha2_256f
Private key size: 64
Public key size: 32
Signature (first 32 bytes): b'1d18751a62751584e4f93e52f31f5f2c7033ae77936a5f405a18c722fd792db8'
Signature length: 49856 bytes
Signature valid: True
Bad signature valid: FalseConclusions
SLH-DSA is a solid signature and has small keys, but the signature is larger than RSA, ECDSA and ML-DSA. It also has rock-solid security proofs, which is not quite the case for RSA, ECDSA and ML-DSA. So, as an alternative to ML-DSA, it’s a great method. A little slow in places but highly secure.
References
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].
[2] 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)
