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).
FrodoKEM with Go |
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.
Coding
Now let's code using the Cloudflare CIRCL library:
// Code derived from https://github.com/cloudflare/circl/tree/main/kem/frodo package main import ( "crypto/aes" "fmt" "math/rand" "time" "github.com/cloudflare/circl/kem/schemes" ) func main() { fmt.Printf("FrodoKEM-640-SHAKE \n") scheme := schemes.ByName("FrodoKEM-640-SHAKE") var seed [48]byte kseed := make([]byte, scheme.SeedSize()) eseed := make([]byte, scheme.EncapsulationSeedSize()) s1 := rand.NewSource(time.Now().UnixNano()) r1 := rand.New(s1) for i := 0; i < 48; i++ { seed[i] = byte(r1.Intn(255)) } g := NewDRBG(&seed) g.Fill(seed[:]) g2 := NewDRBG(&seed) g2.Fill(kseed[:]) pk, sk := scheme.DeriveKeyPair(kseed) ppk, _ := pk.MarshalBinary() psk, _ := sk.MarshalBinary() g2.Fill(eseed) ct, ss, _ := scheme.EncapsulateDeterministically(pk, eseed) ss2, _ := scheme.Decapsulate(sk, ct) fmt.Printf("Alice pk (len=%d) = %X\n", len(ppk), ppk[:128]) fmt.Printf("Alice sk (len=%d) = %X\n", len(psk), psk[:128]) fmt.Printf("Bob seed = %X\n", seed) fmt.Printf("Bob creates ct (len=%d) = %X\n", len(ct), ct[:128]) fmt.Printf("Bob's ss (len=%d) = %X\n\n", len(ss), ss) fmt.Printf("Alice's ss (len=%d) = %X\n\n", len(ss2), ss2) }
This gives:
FrodoKEM-640-SHAKE Alice pk (len=9616) = 0D222B94CC90DA12261361FFDB836B5269D78A4C41A6CAB0E98AC987A3742EC81756E89C14D3E33A4044469D266621C71DD822EEB68F599066370B7EAF99CFB4698F8F7FC47EA56CC6F12136F457AD87428F4E714F83BD28C58433801C475FE0779551BD6B8D1AB026256869ADDD7BBD94B6FC4D4F42A9851B4CD5305F1C3B9C Alice sk (len=19888) = F4128363D2160476E500F3613156CA3E0D222B94CC90DA12261361FFDB836B5269D78A4C41A6CAB0E98AC987A3742EC81756E89C14D3E33A4044469D266621C71DD822EEB68F599066370B7EAF99CFB4698F8F7FC47EA56CC6F12136F457AD87428F4E714F83BD28C58433801C475FE0779551BD6B8D1AB026256869ADDD7BBD Bob seed = 59781635776B31FC58EFE3996DBB597EA598023D86F430CBF06AEF99268F3C99799071EC2A1723DCFF6EEAEE1F8A3968 Bob creates ct (len=9720) = 17092462CE3A37C4ACBAC70AC1E7487ED71B46984EBBEC37F8DF58555143A5321ED9BB2663ABEDD6567FF53C875ED44BD685F287CB3F9E6432B6B6E893473A0B8B9F8FFFB3122E0BEAB506C521EE8E8D24166C4EA6962749020FE6A3E9F95E2DEDC1AB06C5384BA4186C5FA1E779DCD3E3C250CCBFBCEAF8EF4E61EB1B8D83D2 Bob's ss (len=16) = 5532AA053D9A841ABE9DA6D701D89352 Alice's ss (len=16) = 5532AA053D9A841ABE9DA6D701D89352
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. You can test this here. In this case the shared secret is 729780FC51657E21357F03A338116569. You can check the key sizes [here].
Key sizes
The following are some sample results for the main PQC methods:
In terms of key sizes we get:
If we check, this matches with the results from the code.