The Great Cybersecurity Switch-over Has Begun: Meet PQXDH

I have four major presentations coming up over the next few weeks. And the topic? Quantum computers: their risks and benefits.

The Great Cybersecurity Switch-over Has Begun: Meet PQXDH

I have four major presentations coming up over the next few weeks. And the topic? Quantum computers: their risks and benefits.

One of the greatest changes in cybersecurity is underway. Some companies will immediately move, some will wait, and then others may not change over at all. What’s the change? Well, it is the risk of quantum computers to crack public key encryption. Why’s that so important? Well, the Internet would be completely untrustworthy if we removed public key encryption.

Overall, we use public key encryption in two ways. The first is in the exchange of the symmetric key that will be used to encrypt the tunnel, and then we use it to prove the identity of the server using a digital signature. Using Shor’s algorithm, it would be possible to crack the key exchange and also the digital signature. The Internet would then become completely open and untrustworthy.

And, so, many organisations that take cybersecurity seriously are now looking at a switch-over, and one of the first to move is Signal. At the present time, Signal uses X3DH (“Extended Triple Diffie-Hellman”) and will migrate towards PQXDH (“Post-Quantum Extended Diffie-Hellman”). With PQXDH, we use a hybrid key exchange method of X25519 with CRYSTALS-Kyber. Overall, Kyber is the newly defined NIST standard for PQC key exchange.

PQXDH

In order to improve the performance of PQC key exchange, we can create a hybrid model and use X25519 and X488. In this case we will use Kyber512-X25519, Kyber768-X448 and Kyber1024-X448, and which uses X25519 and X448 key exchange methods. The key size for this change a little, and where Kyber512 produces an 800 byte public key, and with 832 bytes for Kyber512-X25519. This means that the public key can be exchanged within a single data packet.

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

Figure 1: [here]

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:

Figure 2: X25519 Key Exchange [here]

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):

Figure 3: Kyber512 and X25519 [here]

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.