WOTS Up With Post Quantum Cryptography?
WOTS Up With Post Quantum Cryptography?
Like it or not, due to the advancement of quantum computers, we are likely to say goodbye to all our existing public key methods, including ECDH and RSA (for key exchange) and RSA, ECDSA, EdDSA and ElGamal (for digital signatures). What’s the alternative? Well, one replacement for digital signatures is to use a hash-based method, where we create lots of private keys and then hash these to a Merkle root. The root hash is then the public key that verifies all of our private keys.
In the NIST competition for PQC (Post Quantum Cryptography), it was the SPHINCS+ method which is now progressing as one of the standards for digital signing [here]. Overall, this method uses the Winternitz one-time signature scheme (W-OTS) and provides relatively small private and public keys and a fairly small ciphertext size.
A method proposed by the IETF and NIST to support PQC digital signatures is the LMS (Leighton-Micali Hash-Based Signature) [1] and is defined in RFC 8554 [here]:
and [here]:
As with SPHINCS+, LMS uses the WOTS one-time signature scheme. So let’s implement the LMS method in this article.
Overall, we generate many private keys and hash these into a Merkle tree, the root hash is then the public key associated with all of these private keys. If the root public key has a node number of 1, then its child nodes will have node numbers of 2 and 3. If we define that we have a h level and are at node N, then the left child node will be 2*N and the right node will be 2*N+1. Each level will thus have leaves of 2^h,(2^h)+1, (2^h)+2, …, (2^h)+(2^h)-1:
Winternitz one time signature scheme (W-OTS)
The W-OTS method was proposed by Robert Winternitz of the Stanford Mathematics Department. It uses relatively small key and signature sizes and is thought to be quantum robust. Overall 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 then 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 signature is then derived from the signature.
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 keys and the first public keys [here]:
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 TrueA demonstration of the method is given here, and an outline here:
https://www.youtube.com/watch?v=eqMMlcN4zSc
LMS
In a WOTS implementation, we have a number of parameters and which vary the security of our implementation:
|------------------------------------------------------------|
| Parameter Set Name | H | n | w | p | ls | sig_len |
|------------------------------------------------------------|
| LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 8516 |
| | | | | | | |
| LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 4292 |
| | | | | | | |
| LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 2180 |
| | | | | | | |
| LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 1124 |
|------------------------------------------------------------|In this case, n is the hash size (32 bytes — 256 bits), and p is the number of n-byte string elements. We then have n times p keys to use, and where the signature length is n times p + 4 + 32 bytes. The smallest signature length in the table is LMOTS_SHA256_N32_W8 and which is 1,124 bytes long.
In the RFC, we have m for the number of bytes associated with each private key, and h as the height of the Merkle tree. Then one LMS private key is defined as 2^h OTS private keys:
+--------------------+--------+----+----+
| Name | H | m | h |
+--------------------+--------+----+----+
| LMS_SHA256_M32_H5 | SHA256 | 32 | 5 |
| | | | |
| LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
| | | | |
| LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
| | | | |
| LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
| | | | |
| LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |
+--------------------+--------+----+----+The number of private key is then 2^h * ((n*p)+4). For LMS_SHA256_M32_H5, we will get 2⁵ *((32*34) + 4) = 34 944 bytes ~ 34 KB. Note there is no need to store the private keys, as we can compute the tree whenever required. This leads to more processing but less memory storage. A comparison with key sizes compared with other methods is:
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
LMS_sha256_n32_h5 56 72 2,348
LMS_sha256_n32_h10 56 72 2,508
LMS_sha256_n32_h15 56 72 2,668
RSA-2048 256 256 256
ECC 256-bit 64 32 256
Crystals Dilithium 2 (Lattice) 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
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice
Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice
Rainbow Level Ia (Oil-and-Vineger) 161,600 103,648 66 1 (128-bit) UOV
Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) UOV
Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) UOV
Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based
Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based
Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based
Picnic 3 Full 49 73 71,179 3 (192-bit) Symmetric
GeMSS 128 352,188 16 33 1 (128-bit) Multivariate
GeMSS 192 1,237,964 24 53 1 (128-bit) MultivariateNow let’s implement LMS using the Bouncy Castle library [here]:
namespace SphincsPlus
{
using Org.BouncyCastle.Pqc.Crypto.Lms;
using Org.BouncyCastle.Pqc.Crypto.SphincsPlus;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var msg="Hello";
var method="lms_sha256_n32_h5";
if (args.Length >0) msg=args[0];
if (args.Length >1) method=args[1];
var random = new SecureRandom();
var keyGenParameters = new LmsKeyGenerationParameters(new LmsParameters(LMSigParameters.lms_sha256_n32_h25, LMOtsParameters.sha256_n32_w4),random);
if (method=="lms_sha256_n32_h5") keyGenParameters = new LmsKeyGenerationParameters(new LmsParameters(LMSigParameters.lms_sha256_n32_h5, LMOtsParameters.sha256_n32_w4),random);
else if (method=="lms_sha256_n32_h10") keyGenParameters = new LmsKeyGenerationParameters(new LmsParameters(LMSigParameters.lms_sha256_n32_h10, LMOtsParameters.sha256_n32_w4),random);
// else if (method=="lms_sha256_n32_h15") keyGenParameters = new LmsKeyGenerationParameters(new LmsParameters(LMSigParameters.lms_sha256_n32_h15, LMOtsParameters.sha256_n32_w4),random);
// else if (method=="lms_sha256_n32_h20") keyGenParameters = new LmsKeyGenerationParameters(new LmsParameters(LMSigParameters.lms_sha256_n32_h20, LMOtsParameters.sha256_n32_w4),random);
// else if (method=="lms_sha256_n32_h25") keyGenParameters = new LmsKeyGenerationParameters(new LmsParameters(LMSigParameters.lms_sha256_n32_h25, LMOtsParameters.sha256_n32_w4),random);
var keyPairGen = new LmsKeyPairGenerator();
keyPairGen.Init(keyGenParameters);
var keyPair = keyPairGen.GenerateKeyPair();
var pubKey = (LmsPublicKeyParameters)keyPair.Public;
var privKey = (LmsPrivateKeyParameters)keyPair.Private;
// Signing
var aliceSign = new LmsSigner();
aliceSign.Init(true, privKey);
var signature = aliceSign.GenerateSignature(System.Text.Encoding.UTF8.GetBytes(msg));
// verify signature
var bobVerify = new LmsSigner();
bobVerify.Init(false, pubKey);
var rtn = bobVerify.VerifySignature(System.Text.Encoding.UTF8.GetBytes(msg), signature);
Console.WriteLine("Message:\t{0}",msg);
Console.WriteLine("Method:\t\t{0}",method);
Console.WriteLine("\nPublic key (length):\t{0} bytes",pubKey.GetEncoded().Length);
Console.WriteLine("Alice Public key :\t{0}",Convert.ToHexString(pubKey.GetEncoded()));
Console.WriteLine("\nPrivate key (length):\t{0} bytes",privKey.GetEncoded().Length);
Console.WriteLine("Alice Private key:\t{0}",Convert.ToHexString(privKey.GetEncoded()));
Console.WriteLine("\nSignature (length):\t{0} bytes",signature.Length);
Console.WriteLine("Signature (first 50 bytes):\t\t{0}",Convert.ToHexString(signature)[..100]);
Console.WriteLine("\nVerified:\t{0}",rtn);
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}A sample run with lms_sha256_n32_h5 gives [here]:
Message: Post Quantum Crypto
Method: lms_sha256_n32_h5
Public key (length): 56 bytes
Alice Public key : 0000000500000003A1FC28853207AEA5B5A6B92093CF0F0B678452F69AC8F343A1A4BC3A08A14130AAF07CF46C2D4717D640B0746B8B0292
Private key (length): 72 bytes
Alice Private key: 000000000000000500000003A1FC28853207AEA5B5A6B92093CF0F0B000000010000002000000020212CF1DB290D1EFD36F43290B18C58912D251A74E5CB070DBF79B54F51B4484B
Signature (length): 2348 bytes
Signature (first 50 bytes): 00000000000000039E2822055561084B6B8567F4122C8F6970651DD985476AFA21410F5A3E4854E6F67F2479203E3B4F1BD0
Verified: Trueand for lms_sha256_n32_h10 [here]:
Message: Post Quantum Crypto
Method: lms_sha256_n32_h10
Public key (length): 56 bytes
Alice Public key : 00000006000000036776613E88BAB931143A8657120F40BD0E909CF2D085979E22B3DF4B56D9D93D386218BA54A1AE563153A489DCCA10FD
Private key (length): 72 bytes
Alice Private key: 0000000000000006000000036776613E88BAB931143A8657120F40BD0000000100000400000000209A8104C4C968E7F9F07585F733BB1C3275268FD3C05380B5878D752469AC11DD
Signature (length): 2508 bytes
Signature (first 50 bytes): 00000000000000033E1E15A47125291359291E973C84A9A2083FEA6D67092CED1DF33AF317739D7E5ACCAD311326E63785F0
Verified: Trueand lms_sha256_n32_h15 [here]:
Message: Post Quantum Crypto
Method: lms_sha256_n32_h15
Public key (length): 56 bytes
Alice Public key : 0000000700000003D4754AAC03B588E4A21723267711F2C25F9BDFA9EF7A3A07D64D580F07BFD17FFF2EDDA266248E765DF13A066CD1AEEB
Private key (length): 72 bytes
Alice Private key: 000000000000000700000003D4754AAC03B588E4A21723267711F2C2000000010000800000000020E900DC335DE013AC77B42B3523B05548A923859FCE254CD7FFF89DC62B7AD763
Signature (length): 2668 bytes
Signature (first 50 bytes): 0000000000000003C8DBA13DDDFF10554839ECA3073526564C4E59C0BCBF93EC393108EC8D6E4E336277E13A054A0C936BBF
Verified: TrueConclusions
There’s a feeling that the lattice methods proposed for digital signatures, such as Dilithium and FALCON, might show some weaknesses in the future. If they do, we will at least have SPHINCS+ and LMS to fall back on. Here is SPHINCS+:
https://asecuritysite.com/bouncy/bc_sphincs
And if you want to read some more about PQC:
or in using the Bouncy Castle library:
https://asecuritysite.com/bouncy
References
[1] McGrew, D., Curcio, M., & Fluhrer, S. (2019). RFC 8554: Leighton-Micali hash-based signatures.