Frodo KEM is based on the learning with errors (LWE) problem, and has a number of levels: FrodoKEM-640 (Level 1, equivalent in security to AES-128), FrodoKEM-976 (Level 3, equivalent in security to AES-192), and FrodoKEM-1344 (Level 5, equivalent in security to AES-256). There are two main variants of these for FrodoKEM-X-AES and FrodoKEM-X-SHAKE. The -AES version has hardware acceleration for AES, and can run faster on processors that support hardware acceleration for AES, while the -SHAKE version is faster on systems that do not support this. For FrodoKEM-640-SHAKE, we can see that the size of Alice's public key is 9,616 bytes long, and her private key is 19,888 bytes long. The ciphertext passed is 9,270 bytes long. FrodoKEM is a NIST final round contender for key exchange (replacing ECDH) and public key encryption (replacing ECC and RSA). With this, we will see that Frodo 19888 produces 128-bit security, Frodo 31296 produces 192-bit security, and Frodo 43088 produces 256-bit security.
Frodo PQC KEM using Bouncy Castle and C# |
Theory
Well, who knows when quantum computers will be built at scale, but one thing that is for sure, is that the will break the fundamental core of security on the Internet. With this our existing public key encryption, digital signature and key exchange methods will be a severe risk. And so we must find alternatives, and one of these is FrodoKEM - and which is a NIST final round contender for key exchange. I like the Frodo method, as it's a pure learning with errors method.
It is based on the learning with errors (LWE) problem, and has a number of levels: FrodoKEM-640 (Level 1, equivalent in security to AES-128), FrodoKEM-976 (Level 3, equivalent in security to AES-192), and FrodoKEM-1344 (Level 5, equivalent in security to AES-256). There are two main variants of these for FrodoKEM-X-AES and FrodoKEM-X-SHAKE. The -AES version has hardware accelleration for AES, and can run faster on processors that support hardware accelleration for AES, while the -SHAKE version is faster on systems that do not support this.
With Frodo, the steps to generate a key, encrypt a message, and decrypt are given next.
Key pair generation
To generate a key pair we create a public key of \(A\), \(B\), and then a private key of \(s\), and where:
\(B= A.s + e \pmod q\)
In this case e is an error, and \(A\) and \(B\) are matrices.
Encryption
If Alice wants to send to Bob, she uses his public key, and generates two secret vectors ((\(s_1\), \(e_1\)) and (\(e_2\))). She then computes:
\(b_1 = A.s_1 + e_1 \pmod q\)
\(v_1 = B.s_1 + e_2 \pmod q\)
Then she adds the message \(m\) to the most significant bit of \(v_1\). The values of \(b_1\) and \(v_1\) are then sent back to Bob.
Decryption
Bob computes the message from:
\(m = v_1 - b_1.s \)
This works as:
\(v_1- b_1 .s\)
gives
\(m + e_2\)
and where \(e_2\) has a negliable affect on the message. The proof is:
\( \begin{aligned} M &= (m + v_1 ) - b_1.s\\ &=m + (B.s_1 + e_2) - (A.s_1.s+e_1.s)\\ &= m + (A.s+e).s_1 + e_2 - A.s_1.s-e_1.s\\ &= m + A.s.s_1+e.s_1+e_2-A.s_1.s-e_1.s\\ &= m + e_2 \end{aligned} \)
This is the basics of FrodoPKE (Public Key Encryption).
Key Encapsulation Mechanism (KEM)
With KEM, Bob and Alice need to generate a shared secret, and which they are likely to use to create a secure tunnel between them. Bob initially creates a key pair \((pk,sk)\), and then generates a hash of the public key:
\(pkh =H(pk)\)
and where \(H()\) is the hashing method. Bob then selects a random value (\(s\)), and thus has a public key of \(pk\) and the private key \(sk_1\) of \((sk, s, pk, pkh)\). He selects a random value (\(u\)) and hashes this with the public key (\(pkh\)) to give:
\((r, k) = H(pkh || u)\)
Next we encrypt as before to get the ciphertext (\(ct\)):
\(ct =Encrypt(u, pk, r)\)
and then hash to get \(ss\) (secret share):
\(ss =H(ct || k)\)
Bob will select \(s\) at random, and sends the ciphertext (\(ct\)) to Alice. She has \((sk, s, pk, pkh)\) and will receive \((ct)\). She can then discover the shared secret with:
\((u, pk, r) = Decrypt(ct)\)
Then:
\( (r , k) = H(pkh || u)\)
Next, Alice discovers the shared secret with:
\(ss =H(ct || k)\)
This recovers the shared secret, and Bob and Alice have the same value.
Keysizes
For our existing ECC methods, the key sizes are:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ P256_HKDF_SHA256 65 32 65 P384_HKDF_SHA384 97 48 97 P521_HKDF_SHA512 133 66 133 X25519_HKDF_SHA256 32 32 32 X448_HKDF_SHA512 56 56 56
In this case, we see a 32-byte secret (private) key size for P256, and 64 bytes for the public key (as it has an x- and y-co-ordinate value) and then another byte added to identify the type of point. This gives a 65 byte public key. For X22519, we only require a single co-ordinate value, and thus only need 32 bytes for the public key (and which is the same size as the secret key). The following defines the key sizes for Kyber, SABER, NTRU and McEliece:
Type Public key size (B) Secret key size (B) Ciphertext size (B) ------------------------------------------------------------------------ Kyber512 800 1,632 768 Kyber738 1,184 2,400 1,088 Kyber1024 1,568 3,168 1,568 LightSABER 672 1,568 736 SABER 992 2,304 1,088 FireSABER 1,312 3,040 1,472 McEliece348864 261,120 6,452 128 McEliece460896 524,160 13,568 188 McEliece6688128 1,044,992 13,892 240 McEliece6960119 1,047,319 13,948 226 McEliece8192128 1,357,824 14,120 240 NTRUhps2048509 699 935 699 NTRUhps2048677 930 1,234 930 NTRUhps4096821 1,230 1,590 1,230 SIKEp434 330 44 346 SIKEp503 378 56 402 SIKEp751 564 80 596 Frodokem19888 9,616 19,888 9,720 Frodokem31296 15,632 31,296 15,744 Frodokem43088 21,520 43,088 21,632
Note: LightSABER has a security level of AES-128, SABER maps to AES-192, and FireSABER to AES-256. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256. NTRUhps2048509 has a security level of AES-128, NTRUhps2048677 maps to AES-192, and NTRUhps4096821 to AES-256.
In terms of performance on an ARM Cortex-M4 (32-bit RISC processor), the following is the number of cycles taken for various operations for key generation, key encapulation and key decapsulation:
scheme (implementation) level key generation encapsulation decapsulation ---------------------------------------------------------------------------- frodokem640aes (m4) 1 48,348,105 47,130 922 46,594,383 kyber512 (m4) 1 463,343 566,744 525,141 kyber768 (m4) 3 763,979 923,856 862,176 lightsaber (m4f) 1 361,687 513,581 498,590 saber (m4f) 3 654,407 862,856 835,122 ntruhps2048509 (m4f) 1 79,658,656 564,411 537,473 ntruhps2048677 (m4f) 3 143,734,184 821,524 815,516 sikep434 (m4) 1 48,264,129 78,911,465 84,276,911 sikep610 (m4) 3 119,480,622 219,632,058 221,029,700 mceliece348864f 1 1,430,811,294 582,199 2,706,681 mceliece348864 1 2,146,932,033 582,199 2,706,681
Coding
Next some code:
namespace Frodo { using Org.BouncyCastle.Pqc.Crypto.Frodo; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var method="frodokem19888r3"; if (args.Length >0) method=args[0]; var random = new SecureRandom(); var keyGenParameters = new FrodoKeyGenerationParameters (random, FrodoParameters.frodokem19888r3); if (method=="frodokem19888r3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem19888r3); else if (method=="frodokem31296r3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem31296r3); else if (method=="frodokem43088r3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem43088r3); else if (method=="frodokem19888shaker3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem19888shaker3); else if (method=="frodokem31296shaker3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem31296shaker3); else if (method=="frodokem43088shaker3") keyGenParameters = new FrodoKeyGenerationParameters(random, FrodoParameters.frodokem43088shaker3); var FrodoKeyPairGenerator = new FrodoKeyPairGenerator(); FrodoKeyPairGenerator.Init(keyGenParameters); var aKeyPair = FrodoKeyPairGenerator.GenerateKeyPair(); var aPublic = (FrodoPublicKeyParameters)aKeyPair.Public; var aPrivate = (FrodoPrivateKeyParameters)aKeyPair.Private; var pubEncoded =aPublic.GetEncoded(); var privateEncoded = aPrivate.GetEncoded(); var bobFrodoKemGenerator = new FrodoKEMGenerator(random); var encapsulatedSecret = bobFrodoKemGenerator.GenerateEncapsulated(aPublic); var bobSecret = encapsulatedSecret.GetSecret(); var cipherText = encapsulatedSecret.GetEncapsulation(); var aliceFrodoKemExtractor = new FrodoKEMExtractor(aPrivate); var aliceSecret = aliceFrodoKemExtractor.ExtractSecret(cipherText); Console.WriteLine("Frodo Engine:\t\t\t{0}",keyGenParameters.Parameters.Name); Console.WriteLine("Frodo Key Size:\t\t\t{0}",keyGenParameters.Parameters.DefaultKeySize); Console.WriteLine("Frodo N:\t\t\t{0}",keyGenParameters.Parameters.N); Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length); Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length); Console.WriteLine("Ciphertext length:\t\t{0} bytes",cipherText.Length); Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]); Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]); Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]); Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret)); Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret)); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
Frodo 19888 produces a 128-bit key size:
Frodo Engine: frodokem19888 Frodo Key Size: 128 Frodo N: 640 Private key length: 19888 bytes Public key length: 9616 bytes Ciphertext length: 9720 bytes Alice private (first 50 bytes): 60E94F807790F80CC887AAD61DEC343CAAF5A20D3A76A4B348B7C73EB815DD9DFC84DED0961681EDA8B134056AE03D22CEB7 Alice public (first 50 bytes): AAF5A20D3A76A4B348B7C73EB815DD9DFC84DED0961681EDA8B134056AE03D22CEB7AAC9DF2EC4C45220F1D11FAF6B7DE887 Cipher (first 50 bytes): 9F9CB943AFBC9CE6CB94C5CC9037C1274366604E853291F821660513BB913C54FE336680E965859B2A47E40786ECD16CC649 Bob secret: AD2CBB2E9755D3E7EB3DF780EF86DA9F Alice secret: AD2CBB2E9755D3E7EB3DF780EF86DA9F
and for Frodo 31296, we have a 192-bit key size:
Frodo Engine: frodokem31296 Frodo Key Size: 192 Frodo N: 976 Private key length: 31296 bytes Public key length: 15632 bytes Ciphertext length: 15744 bytes Alice private (first 50 bytes): CBAE417B2E3182770219415A474CFE1F68CE1F9168A3CC2716B4FB19C038F235145E3487F50B6AC199F6313A0F45887830E8 Alice public (first 50 bytes): 16B4FB19C038F235145E3487F50B6AC199F6313A0F45887830E87949D6D2EF19381201FAD76F20668D8EAED014076ACDAF0A Cipher (first 50 bytes): 72C7942F0C78C3DC4BF12116DB8CACABC4D9D55C5AF2D4F16AD616ABFC5555BA9D8771C14C22F1051AC38E7384E09938220F Bob secret: FECD0AB21291E4027DE53D5D37A64C3E2BA40A606B37FD8B
and for Frodo 43088, we get a 256-bit key:
Frodo Engine: frodokem43088 Frodo Key Size: 256 Frodo N: 1344 Private key length: 43088 bytes Public key length: 21520 bytes Ciphertext length: 21632 bytes Alice private (first 50 bytes): CEC1D8A812454DFABCD95DEA297F791AD542EF49E6552324F20A09D4F9D9E52278D4009BD9A2A5299D22C78BFB5B69015E97 Alice public (first 50 bytes): 78D4009BD9A2A5299D22C78BFB5B69015E9717124EF893467ADB0B17CA548C5AEC358786C22A0641D0B62F1D356FB58DBC75 Cipher (first 50 bytes): 71C933B3C066C4BA854D218E96C9EB78C7BE5606D1CED587EFF7E6E12C00FE2E8C189922CAAC66007D6EFAD94773E1512A15 Bob secret: 5056F91CB1FEFAFC56593E1C9F9FE9E5D549F1B34CD56743543847E9C18EAF6A Alice secret: 5056F91CB1FEFAFC56593E1C9F9FE9E5D549F1B34CD56743543847E9C18EAF6A