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. 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.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.
Leighton-Micali Hash-Based Signatures using Bouncy Castle and C# |
Details
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. 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.
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]:
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 as a node number of 1, then its child nodes will have a 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 signatures 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 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 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 key 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 True
A demonstration of the method is given here.
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 tre. 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 sise 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) Multivariate
Now let's implement LMS using the Bouncy Castle library:
namespace LMS { using Org.BouncyCastle.Pqc.Crypto.Lms; 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:
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: True
and for lms_sha256_n32_h10:
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: True
and lms_sha256_n32_h15:
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: True
References
[1] McGrew, D., Curcio, M., & Fluhrer, S. (2019). RFC 8554: Leighton-Micali hash-based signatures.