After 48 Years, It’s A Long Goodbye to the Diffie-Hellman Method

Apple [here]

This week, in my lecture, I will outline one of the most amazing methods ever created in computer science: the Diffie-Hellman method. It was first outlined by Whitfield Diffie and Marty Hellman in 1976 in a paper that built the foundation of our modern world of cybersecurity:

And so, after nearly five decades (48 years, to be precise), the Diffie-Hellman method has done so well in protecting citizen data, and is used in virtually every connection we make to the Internet. For this, Bob and Alice can create session key pairs, and then pass their public key values, and then end up with the same shared key:

The original paper was based on discrete logarithms, and where Bob and Alice agree on a base generator (g) and a large prime number (p). They then create a secret value (a and b), and pass a public value (either g^a (mod p) or g^b (mod p)):

These days, though, we tend not to use discrete log methods, and use elliptic curve methods instead:

But quantum methods is likely eventually put an end to the usage of the Diffie-Hellman method. The only hope for it is that we might use isogenies, but where the SIKE method proposed in the NIST PQC competition was cracked due to a weak set of parameters. The future of key exchange is now likely to be key encapsulation, and where we encrypt the shared key with the receiver’s public key, and then they decrypt this with their private key.

This method was actually used in TLS versions up to 1.2, but was dropped in TLS 1.3, as a hack of Alice’s private key causes all the previous keys that were generated associated with that key to be revealed. Thus, we need to start talking about Key Encapsulation Mechanisms (KEM) rather than Key Exchange Methods.

For this, it is CRYSTALS-Kyber that has been standardized by NIST as FIPS 203, and will know be known as the boring name of ML-KEM. There are then three new methods: ML-KEM-512 (128-bit equivalent security), ML-KEM-768 (192-bit equivalent security) and ML-KEM-1024 (256-bit equivalent security). The coding for these is given here:

Kyber and SIKE PQC Key Exchange Mechanism (KEM) with CIRCL

A pure ML-KEM-512 handshake creates an 768 byte ciphertext value to be passed, and which will fit inside a single data packet [here]:

Method: Kyber512 
Seed for key exchange: CFA21062F8923F870AE2C4A6B832130DB76E106C7ADD668B3B7700050A9CD3D9A75443101793F8BA48291AC005F79666
Public Key (pk) = 6243172297AAD3D652AE48BA19F124A30B4893A70A43885C8B4AA73C58490E0C (first 32 bytes)
Private key (sk) = 9D082E77E545B5A130B6186CDBF5692D0358B4A21F8159CC0D34080BD03C7211 (first 32 bytes)
Cipher text (ct) = 913460CCFDC60B330360471EAE95D3AB43AA3B80252DDC97757400905F0682B6 (first 32 bytes)

Shared key (Bob): 15C3E57CA2A266120D668360C10D4DBDD10F1F1ABC1B9B582D5254ED73303903
Shared key (Alice): 15C3E57CA2A266120D668360C10D4DBDD10F1F1ABC1B9B582D5254ED73303903

Length of Public Key (pk) = 800 bytes 
Length of Secret Key (sk)  = 1632  bytes
Length of Cipher text (ct) = 768  bytes

If we ramp up to Kyber-768 — and which seems to be the choice for many designers — we have a 1,088 byte ciphertext value, and which will also fit into a single data packet [here]:

Method: ML-KEM-768 
Seed for key exchange: D306DEF7644294FE979232D93CEE9D6F8C1AFB33D281D84B83AC0ED1B51CE726818BC6BD13D0262DA96896B77D23D9F3
Public Key (pk) = DDEC346B7A7593CA8F798820802B9B4D22CE66DC200B079077CBB77C75070387 (first 32 bytes)
Private key (sk) = A3065A9EE6477542B3D5F243B355A099E9691A5A1D954339D7E1B7F870158D33 (first 32 bytes)
Cipher text (ct) = 4A04BB5F417936ED308A36CF390B4A47FE6FC6D50F3ECFF5FEECF95C53512B01 (first 32 bytes)

Shared key (Bob): C4352D975D6EFC14B83D789DF21F7F68DF5BFF78B9DEB83305BA09769E67CF6E
Shared key (Alice): C4352D975D6EFC14B83D789DF21F7F68DF5BFF78B9DEB83305BA09769E67CF6E

Length of Public Key (pk) = 1184 bytes 
Length of Secret Key (sk)  = 2400  bytes
Length of Cipher text (ct) = 1088  bytes

For the short-term, what is more likely is that we will use a drop-in hybrid system, such as including the X25519 ciphertext value alongside the Kyber ciphertext value. For an X25519-ML-KEM-738 method, we increase the ciphertext size to 1,120 bytes, and which again will fit into a single TLS packet [here]:

Method: X25519MLKEM768 
Seed for key exchange: 8E6C3F931B4DB14B6033F785F07C428A1EA0C8C5DBEFB232513025C8F3D16B071B3765AAD2CBC778E4D49EA6AC3A9781
Public Key (pk) = 513BCBAB78004E09629F04B977432ECD03098E69388D9428DBB94AB0B4AD4FD4 (first 32 bytes)
Private key (sk) = C9B7C29E31B55F8B65E520B264011745499738492AEF5726DD7C1A100B15D50B (first 32 bytes)
Cipher text (ct) = 2D1274E1E1D9848DD5E57CBCA2048D9A57864E49DFA9B912F1C5ECAE60B7DECC (first 32 bytes)

Shared key (Bob): A341FDA114D99705BF3EF9947D6AA2198AB2CF8CEB64EB0FBDEC4175CD037726F66DECC923F1E95CE62A5B1C7AE8D20E60FE52106CBB184FF8A45535E3FCA95B
Shared key (Alice): A341FDA114D99705BF3EF9947D6AA2198AB2CF8CEB64EB0FBDEC4175CD037726F66DECC923F1E95CE62A5B1C7AE8D20E60FE52106CBB184FF8A45535E3FCA95B

Length of Public Key (pk) = 1216 bytes 
Length of Secret Key (sk)  = 2432  bytes
Length of Cipher text (ct) = 1120  bytes

And, so, the near future is likely to be a hybrid key exchange method, and where we mix our Diffie-Hellman key exchange method with ML-KEM (aka Kyber).

Conclusions

It will take a while to migrate, but the usage of the Diffie-Hellman method will decrease over the next decade or so. Here is it in all its glory:

and here is the mighty Whit:

and Marty: