Goodbye ECDH, and Hello To Kyber
Goodbye ECDH, and Hello To Kyber
I have my first invited Black Hat talk coming up, and it will focus on Post Quantum Cryptography [here]:
So, like it or not — no matter when quantum computers will be built at production levels — we will have to replace ECDH (Elliptic Curve Diffie Hellman) for key exchange with a Post Quantum robust method. The top of the list for this is Kyber, and which is likely to be integrated into browsers and servers over the next few years. And, so, in this article, I will present some simple code to illustrate its usage.
It should be noted that Kyber is not a Diffie-Hellman key exchange method, but a key encapsulation method, and where Bob will encapsulate the key with Alice’s public key, and then pass this to Alice, and where Alice decrypts it with his private key to reveal the key that they will share:
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. A new lattice attack was discovered within the period of the assessment [1], but it is hoped that an updated version of Kyber can be produced for the final assessment. NIST have some worried about its side-channel robustness, but is a strong contender for KEM.
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.
Key sizes
With ECDH, we have a private key of 32 bytes (256 bits) and a public key size of 64 bytes (512 bits). These sizes will increase for Kyber and where Kyber-512 will have a private key of 1,632 bytes and a public key of 800 bytes. Normally the private key is never revealed, but the public key is passed between Bob and Alice, and so there will be a network overhead in passing the public key and the ciphertext. Luckily for Kyber512 and Kyber738, this can be sent in a single data packet.
The key sizes for Kyber and other PQC methods are:
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 Learning with errors (Lattice)
Kyber738 1,184 2,400 1,088 Learning with errors (Lattice)
Kyber1024 1,568 3,168 1,568 Learning with errors (Lattice)
LightSABER 672 1,568 736 Learning with rounding (Lattice)
SABER 992 2,304 1,088 Learning with rounding (Lattice)
FireSABER 1,312 3,040 1,472 Learning with rounding (Lattice)
McEliece348864 261,120 6,452 128 Code based
McEliece460896 524,160 13,568 188 Code based
McEliece6688128 1,044,992 13,892 240 Code based
McEliece6960119 1,047,319 13,948 226 Code based
McEliece8192128 1,357,824 14,120 240 Code based
NTRUhps2048509 699 935 699 Lattice
NTRUhps2048677 930 1,234 930 Lattice
NTRUhps4096821 1,230 1,590 1,230 Lattice
SIKEp434 330 44 346 Isogeny
SIKEp503 378 56 402 Isogeny
SIKEp751 564 80 596 Isogeny
SIDH 564 48 596 IsogenyCode
We can create a .NET console project with:
dotnet new consoleFirst we install the Bouncy Castle library:
dotnet add package BouncyCastle.CryptographyNext some code [here]:
namespace Kyber
{
using Org.BouncyCastle.Pqc.Crypto.Crystals.Kyber;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var size="768";
if (args.Length >0) size=args[0];
var random = new SecureRandom();
var keyGenParameters = new KyberKeyGenerationParameters(random, KyberParameters.kyber512);
if (size=="768") keyGenParameters = new KyberKeyGenerationParameters(random, KyberParameters.kyber768);
else if (size=="1024") keyGenParameters = new KyberKeyGenerationParameters(random, KyberParameters.kyber1024);
var kyberKeyPairGenerator = new KyberKeyPairGenerator();
kyberKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = kyberKeyPairGenerator.GenerateKeyPair();
var aPublic = (KyberPublicKeyParameters)aKeyPair.Public;
var aPrivate = (KyberPrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobKyberKemGenerator = new KyberKemGenerator(random);
var encapsulatedSecret = bobKyberKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceKemExtractor = new KyberKemExtractor(aPrivate);
var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Kyber-{0}",size);
Console.WriteLine("Private key length:\t\t{0} bytes",aPrivate.GetEncoded().Length);
Console.WriteLine("Public key length:\t\t{0} bytes",aPublic.GetEncoded().Length);
Console.WriteLine("\nAlice private (first 50 bytes):\t{0}",Convert.ToHexString(aPrivate.GetEncoded())[..100]);
Console.WriteLine("Alice public (first 50 bytes):\t{0}",Convert.ToHexString(aPublic.GetEncoded())[..100]);
Console.WriteLine("\nCipher (first 50 bytes):\t{0}",Convert.ToHexString(cipherText)[..100]);
Console.WriteLine("\nBob secret:\t\t{0}",Convert.ToHexString(bobSecret));
Console.WriteLine("Alice secret:\t\t{0}",Convert.ToHexString(aliceSecret));
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}A sample run showing the cipher text, and the public and private key is [here]:
Kyber-512
Private key length: 1632 bytes
Public key length: 800 bytes
Ciphertext length: 768 bytes
Alice private (first 50 bytes): 387645302B35F9D2CD22A8BAAE663E53961641060C4D4C17253A036D47AE3C220529740DDAC74CAE6C9764876C8EA32687A6
Alice public (first 50 bytes): 70127E4750B0EFB07F29A687388269E5DCB6FBA51759B5225629247CE508A37A08B9325852D625F7653976C40B9B85C3EAE4
Cipher (first 50 bytes): C56FB383D8CEE19C2EA8F682E0287302B86870625DBE2AA2FF9A2B348E68386347499E668442FEC8FD4A719CF410D9CDD58E
Bob secret: 79A42C2F255797D94662C95F8623968C4E3044F64CD48909BE31B386DF88A885
Alice secret: 79A42C2F255797D94662C95F8623968C4E3044F64CD48909BE31B386DF88A885We can see that Bob and Alice end up with the same 256-bit shared key, and which can now be used to encrypt data within a secure tunnel. The ciphertext passed is 768 bytes, and the public key is 800 bytes — both of these can pass in a single data packet.
Conclusions
There is much debate about when quantum computers will arrive, but no matter when they do, we perhaps need to switch over to Kyber sooner rather than later. Overall, lattice methods should be more robust to cracking in the future than elliptic curves — so here’s to a world of errors!
Run the code here: