Post Quantum and Non-Post Quantum Key Exchange: ECC and Kyber Working in Harmony
Post Quantum and Non-Post Quantum Key Exchange: ECC and Kyber Working in Harmony
And, so, like it or not, our existing key exchange methods will eventually be deprecated with the rise of quantum computers. In most cases we use elliptic curve methods for key exchange, and which has replaced the Diffie Hellman method. The two main methods are ECDH (using P-256 and secp256k1) and X.25519 (using Curve 25519). After a relatively long competition, NIST has defined that Kyber is progressing to a standard for key exchange.
But, what can you do now? Well, it’s unlikely we will be switching of ECDH/X.25519 key exchange any time soon. One way is to support both Kyber and ECDH/X.25519 in a key exchange session — this is known as a hybrid method.
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 56In 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 x 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 596It is obvious why Kyber won the competition, as it has such small key sizes compared with McEliece. Unfortunately SIKE was cracked, so failed to progress. We can now use the CIRCL library to implement the Hybrid method [here]:
package main
// Based on examples at https://github.com/cloudflare/circl/tree/master/kem/kyber
import (
"fmt"
"math/rand"
"os"
"time"
"github.com/cloudflare/circl/kem/schemes"
)
func main() {
meth := "Kyber512-X25519" // Kyber768-X448 Kyber1024-X448
argCount := len(os.Args[1:])
if argCount > 0 {
meth = os.Args[1]
}
scheme := schemes.ByName(meth)
rand.Seed(time.Now().Unix())
pk, sk, _ := scheme.GenerateKeyPair()
ppk, _ := pk.MarshalBinary()
psk, _ := sk.MarshalBinary()
ct, ss, _ := scheme.Encapsulate(pk)
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 (sk) = %d bytes\n", len(psk))
fmt.Printf("Length of Cipher text (ct) = %d bytes\n", len(ct))
}A sample run for Kyber512-X25519 is [here]:
Method: Kyber512-X25519
Public Key (pk) = 0D584135D3242392B5E6EC06B3990CEEC43CB3A35875F3CDECC53FEADA33E047 (first 32 bytes)
Private key (sk) = 7B558F88CA046A7C1A83431ACAD94629B4A72E8BBEFFF40AD1A7024A2A6DC8A5 (first 32 bytes)
Cipher text (ct) = 170F2B8C341B603A38520E16404C3D507ACB5A45BC582F4CCA1AD807196D071B (first 32 bytes)
Shared key (Bob): 82B7AECBC7A5C381C712FBA258A38984DA32B9D2B39B2D118B7978371402CD9E413574B7684518ECC484D4DFDCFA0EBFE377FEF3AB982F60F47AD666C56EC196
Shared key (Alice): 82B7AECBC7A5C381C712FBA258A38984DA32B9D2B39B2D118B7978371402CD9E413574B7684518ECC484D4DFDCFA0EBFE377FEF3AB982F60F47AD666C56EC196
Length of Public Key (pk) = 832 bytes
Length of Secret Key (sk) = 1664 bytes
Length of Cipher text (ct) = 800 bytesAnd for improved security, we can use X-488 and Kyber768 [here]:
Method: Kyber768-X448
Public Key (pk) = 0F3BC5031BB49ED1184E378C39E8BB1696442290329B716A97E79FF100B73599 (first 32 bytes)
Private key (sk) = 7B86917D307381BC146125709BD2A39EF6623F8A05F264416E26660F04CA4D20 (first 32 bytes)
Cipher text (ct) = 6575C5E916830D96D36C204307284AF89587BEFFC3F579EFEBE352198709FCE5 (first 32 bytes)
Shared key (Bob): 5FC20E38B2267E042BCB36319732E2BD5C2D57A9C78D4955FB9423D3D982CA5A1FF791AD7707E18942505334C02FB36F30BD55ED660A781B1101B0CF205C30D767D8718E752107C3B82145330DC0B5817B5788F4A25FC4FB51BF71477B03346A
Shared key (Alice): 5FC20E38B2267E042BCB36319732E2BD5C2D57A9C78D4955FB9423D3D982CA5A1FF791AD7707E18942505334C02FB36F30BD55ED660A781B1101B0CF205C30D767D8718E752107C3B82145330DC0B5817B5788F4A25FC4FB51BF71477B03346A
Length of Public Key (pk) = 1240 bytes
Length of Secret Key (sk) = 2456 bytes
Length of Cipher text (ct) = 1144 bytesAnd for the best security, we can have Kyber1024-X448 [here]:
Method: Kyber1024-X448
Public Key (pk) = ACDC644291611A014B41408A16D52479B513FBE15906B259660BB0579B1D9508 (first 32 bytes)
Private key (sk) = 690133C140927B6212D539458DB18DC0F28B7CEB549BF32C2FB03229A109C705 (first 32 bytes)
Cipher text (ct) = 488232A8878C312FE5988DD19EA04CBC892F25036569423E83061CAEF2C32FC7 (first 32 bytes)
Shared key (Bob): FFE3DA3744D79EEBAC20C6224B9EAE6B9622F5B8202C4227A7500984DC0943842A1EE9A775E5CD699CAE5A3134925F666F0F1C78B9B3237F4EFA50EE7632F47485A9D402238AAB802E1100A1DD037EEBC781889E335328D25E536B04528D343A
Shared key (Alice): FFE3DA3744D79EEBAC20C6224B9EAE6B9622F5B8202C4227A7500984DC0943842A1EE9A775E5CD699CAE5A3134925F666F0F1C78B9B3237F4EFA50EE7632F47485A9D402238AAB802E1100A1DD037EEBC781889E335328D25E536B04528D343A
Length of Public Key (pk) = 1624 bytes
Length of Secret Key (sk) = 3224 bytes
Length of Cipher text (ct) = 1624 bytesConclusions
So, goodbye ECC and hello lattice.