Get Ready For The Great Cybersecurity Reboot
Get Ready For The Great Cybersecurity Reboot
Well, the next ten years will see a great transition in Cybersecurity. Why? Because the foundation of cybersecurity on the Internet — and which has developed over four decades — will crumble with the advent of quantum computers.
Shor and Grover showed that the basis of our existing public key methods will fail to be hard problems anymore, and everything we have built using our existing public key methods will be easily cracked. This includes key exchange, digital signatures and public-key encryption.
Just now your browser is happily creating a key exchange using elliptic curve methods (ECDH), and your digital signature probably is probably based on elliptic curves techniques (ECDSA or EdDSA). Even the digital certificate that your browser uses to check from Medium.com is likely to be based on RSA — and which can also be cracked by quantum computers.
And so, as an industry, it will be one of our major challenges to seamlessly migrate our existing fixation with ECC, Discrete Logs and RSA toward the quantum robust methods. Luckily, there are great companies such as Cloudflare and who are building and testing the migration of our existing public key methods towards a post-quantum world. And also where NIST is defining the standard that we will use.
So, let’s jump in, and implement one of the best key exchange methods around: Kyber, and use the Cloudflare CIRCL library.
Meet CRYSTALS Kyber
CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. CRYSTALS-Kyber uses LWE (Learning with Errors) with lattice methods. Overall a KEM allows a symmetric key to be passed using public-key methods. In this case, Alice will generate her key pair of a public key (pk) and a private key (sk). She then passes her public key to Bob, and then Bob creates a cipher text (ct) with Alice’s public key. He passes the ciphertext to Alice, and who decrypts with her private key. This will reveal the key that Bob wants Alice to use. Kyber512 has a security level of AES-128, Kyber738 maps to AES-192, and Keyber1024 to AES-256. In the case we will use the Cloudflare CIRCL library to implement Kyber [CIRCL].
In this example, we will use the Kyber 512 method [here]:
package main
// Based on examples at https://github.com/cloudflare/circl/tree/master/kem/kyber
import (
"fmt"
"os"
"github.com/cloudflare/circl/kem/schemes"
)
func main() {meth:="Kyber512"
argCount := len(os.Args[1:])
if argCount > 0 {
meth = os.Args[1]
}scheme := schemes.ByName(meth)
var seed [48]byte
kseed := make([]byte, scheme.SeedSize())
eseed := make([]byte, scheme.EncapsulationSeedSize())
for i := 0; i < 48; i++ {
seed[i] = byte(i)
}
g := NewDRBG(&seed)
g.Fill(seed[:])
fmt.Printf("Seed for key exchange: %X\n", seed)
g2 := NewDRBG(&seed)g2.Fill(kseed[:32])
g2.Fill(kseed[32:])
g2.Fill(eseed)
pk, sk := scheme.DeriveKeyPair(kseed)
ppk, _ := pk.MarshalBinary()
psk, _ := sk.MarshalBinary()
ct, ss, _ := scheme.EncapsulateDeterministically(pk, eseed)
ss2, _ := scheme.Decapsulate(sk, ct)
fmt.Printf("Method: %s \n", meth)
fmt.Printf("Public Key (pk) = %X (first 32 bytes)\n", ppk[:32])
fmt.Printf("Private key (sk) = %X (first 32 bytes)\n", psk[:32])
fmt.Printf("Cipher text (ct) = %X (first 32 bytes)\n", ct[:32])
fmt.Printf("\nShared key (Bob):\t%X\n", ss)
fmt.Printf("Shared key (Alice):\t%X", ss2) fmt.Printf("\n\nLength of Public Key (pk) = %d bytes \n", len(ppk))
fmt.Printf("Length of Secret Key (pk) = %d bytes\n", len(psk))
fmt.Printf("Length of Cipher text (ct) = %d bytes\n", len(ct))}
A sample run is for Kyber512 is [here]:
Method: Kyber512
Seed for key exchange: 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1
Public Key (pk) = 115ACE0E64677CBB7DCFC93C16D3A305F67615A488D711AA56698C5663AB7AC9 (first 32 bytes)
Private key (sk) = 6C892B0297A9C7641493F87DAF3533EED61F07F4652066337ED74046DCC71BA0 (first 32 bytes)
Cipher text (ct) = EDF24145E43B4F6DC6BF8332F54E02CAB02DBF3B5605DDC90A15C886AD3ED489 (first 32 bytes)
Shared key (Bob): 0A6925676F24B22C286F4C81A4224CEC506C9B257D480E02E3B49F44CAA3237F
Shared key (Alice): 0A6925676F24B22C286F4C81A4224CEC506C9B257D480E02E3B49F44CAA3237F
Length of Public Key (pk) = 800 bytes
Length of Secret Key (pk) = 1632 bytes
Length of Cipher text (ct) = 768 bytes
and for Kyber738:
Method: Kyber768
Seed for key exchange: 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1
Public Key (pk) = A72C2D9C843EE9F8313ECC7F86D6294D59159D9A879A542E260922ADF999051C (first 32 bytes)
Private key (sk) = 07638FB69868F3D320E5862BD96933FEB311B362093C9B5D50170BCED43F1B53 (first 32 bytes)
Cipher text (ct) = B52C56B92A4B7CE9E4CB7C5B1B163167A8A1675B2FDEF84A5B67CA15DB694C9F (first 32 bytes)
Shared key (Bob): 914CB67FE5C38E73BF74181C0AC50428DEDF7750A98058F7D536708774535B29
Shared key (Alice): 914CB67FE5C38E73BF74181C0AC50428DEDF7750A98058F7D536708774535B29
Length of Public Key (pk) = 1184 bytes
Length of Secret Key (pk) = 2400 bytes
Length of Cipher text (ct) = 1088 bytes
and for Kyber1024:
Method: Kyber1024
Seed for key exchange: 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1
Public Key (pk) = D22302CBD3399FACC630991FC8F28BDB4354762541527678BCF61F65C241146C (first 32 bytes)
Private key (sk) = 07638FB69868F3D320E5862BD96933FEB311B362093C9B5D50170BCED43F1B53 (first 32 bytes)
Cipher text (ct) = A6AF29D5F5B80BD130F518BADDD6C8F17545413D860FB3DE451979EBFA5E4E31 (first 32 bytes)
Shared key (Bob): B10F7394926AD3B49C5D62D5AEB531D5757538BCC0DA9E550D438F1B61BD7419
Shared key (Alice): B10F7394926AD3B49C5D62D5AEB531D5757538BCC0DA9E550D438F1B61BD7419
Length of Public Key (pk) = 1568 bytes
Length of Secret Key (pk) = 3168 bytes
Length of Cipher text (ct) = 1568 bytes
How does Kyber compare with the others?
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
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.
We can see that Kyber has a slightly smaller key size compared with SABER, and has a public key around the same size as SABER. While the signature size is larger than Mceliece, the key sizes for Mceliece are so much larger.
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 encapsulation and key decapsulation [1]:
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
Conclusions
Public key encryption is a fundamental part of our online security. It proves the identity of the servers we connect to, it proves our identity, it keeps our conversations safe from spies, and it allows us to sign for things digitally. And, so we must start planning now, for a seamless transition.
If you want to know more about the CIRCL library:
https://asecuritysite.com/circl
and for Post Quantum Crypto:
https://asecuritysite.com/pqc/
References
References
[1] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].