Having Your Crypto Handshaking Cake And Eating It: X25519 or Kyber … Why Not Have Both?

Having Your Crypto Handshaking Cake And Eating It: X25519 or Kyber … Why Not Have Both?

And, so, how do we migrate from our existing key exchange methods into a world with does not contain any elliptic curve methods? Well, one way is to use a Hybrid method that integrates both lattice methods (with Kyber) and a compatible key exchange method (such as with X25519). The advantage of this is that we can try out Kyber but still keep compatibility with existing browser implementations.

For this, Cloudflare has created pure Kyber implementations alongside Kyber-X25519:

The Golang code for this is [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))

}

X25519 and Kyber/X25519

For X25519, we have a 256-bit curve (based on Curve 25519(, we have a secret key (sk) and a public key (pk). The secret key is 32 bytes long (256 bits), and the public key is then pk=sk.G (where G is the base point on the curve). Normally we would need to use a 64-byte public key (as with secp256k1) in order to order the (x,y) coordinate, but in Curve 25519, we only need to store the x-axis value. Thus, the public key is the same size as the secret key and also the same size as the cipher [here]:

Method: HPKE_KEM_X25519_HKDF_SHA256 
Public Key (pk) = 063717715226516938ED3CC0278E8FD67DF558DE611E8B9BBE11936A3EF4B228 (first 32 bytes)
Private key (sk) = 193FC8C3A73782DA18B238915C941CEF5E985DB388C881BD3C0E9EF496894A19 (first 32 bytes)
Cipher text (ct) = 414CC12D11411D395E0CF4BBB6C0DF8D07C3C46D031A420614E960B13C46441B (first 32 bytes)Shared key (Bob): C986A796CE4C0C0F46F391A940D8CE306DD0B02804B6B12F59D65381DBC4268D
Shared key (Alice): C986A796CE4C0C0F46F391A940D8CE306DD0B02804B6B12F59D65381DBC4268DLength of Public Key (pk) = 32 bytes 
Length of Secret Key (sk)  = 32  bytes
Length of Cipher text (ct) = 32  bytes

For Kyber512, the keys are larger, such as 800 bytes for the public key, and 1,632 bytes for the secret key [here]:

Method: Kyber512 
Public Key (pk) = 7D14346DC062275A58E5B50F74768ACCE0B1B9370622F84EDD187F44EA7F137B (first 32 bytes)
Private key (sk) = 7D1B4EEF8979636C8E0853716C588B084378FA5BB39C0BC3877670054491FD72 (first 32 bytes)
Cipher text (ct) = 4DAA3FBBE9E0B13187A5E231017F9EC347CC11AA0178F37FD19E94A2A2041B46 (first 32 bytes)Shared key (Bob): B7FEF95059E01B8380B8374AD3FB5CAEEEF11B20B32BDE3213B8C9391E5B5A36
Shared key (Alice): B7FEF95059E01B8380B8374AD3FB5CAEEEF11B20B32BDE3213B8C9391E5B5A36Length of Public Key (pk) = 800 bytes 
Length of Secret Key (sk)  = 1632  bytes
Length of Cipher text (ct) = 768  bytes

With the X25519, we add another 32 bytes on the key exchange, in order to add in the Curve 25519 part [here]:

Method: Kyber512-X25519 
Public Key (pk) = C048A578B8949480323DB530222BA1E42828D371426FB1AFE814A63B10892D33 (first 32 bytes)
Private key (sk) = 1587A3858706B9673A59A01B8C6C8B6BD85B5BA08904AABA95C9458595026D96 (first 32 bytes)
Cipher text (ct) = CA20703F2804D0C900358952D449FEDD192124C9193D9F3D70910C2B648F6FB6 (first 32 bytes)Shared key (Bob): FA098D84D6ABE660B10111AF7EE41C293C8E6591A9325B9E4A276FF66D9D6766C067DF67A6BA7014CCE2E8222B140DBA29C9EF79329F27ECC8CDB07755492F93
Shared key (Alice): FA098D84D6ABE660B10111AF7EE41C293C8E6591A9325B9E4A276FF66D9D6766C067DF67A6BA7014CCE2E8222B140DBA29C9EF79329F27ECC8CDB07755492F93Length of Public Key (pk) = 832 bytes 
Length of Secret Key (sk)  = 1664  bytes
Length of Cipher text (ct) = 800  bytes

Cloudflare has already started to prototype the Hybrid scheme, and thus investigate it for performance levels. With Wireshark, Cloudflare detects the TLS handshake (such as from the Client Hello and then onto the Server Hello) for X25519:

As we have seen previously, we can see that the key length is 32 bytes (256 bits). With Kyber and X25519, the Client Hello is sent with a single packet but results in a larger packet size (1163 bytes instead of 360 bytes, and where we have added 803 bytes (with 800 extra bytes for public key — as shown previously). There is unlikely to be too much of an extra overhead for the network latency, as we are still using a single packet. For the Server Hello, though, we require three packets (as opposed to two with X25519). This is because of the server has a larger key share (832 bytes as opposed to only 32 bytes for X25519):

Conclusions

And, so, we have largely adopted ECC (Elliptic Curve Cryptography) for so many of our applications (including with blockchains and TLS), because it is so efficient and has relatively small key sizes. But, that will end. So, we need to migrate from ECC (and RSA) towards the post-quantum methods. The hybrid Kyber/X25519 implementation is, at least, a start to the migration, but it must be remembered that the hybrid method will still be crackable by quantum computers. A core advantage of using Kyber/X25519 is that the key exchange parameters (800 bytes) fit into a single data packet, and thus cutting down the overhead.