Goodbye to the 64-byte public keys of ECDH and Hello to 640KB public keys?
Mceliece is more suited to public key encryption than key exchange?
And, so, one thing we know from Peter Shorr is that quantum computers will break discrete log and elliptic curve problems. Over the next few years, we will have to deprecate ECDH (Elliptic Curve Diffie Hellman) and move towards a quantum robust approach. A note here is that ECDH is involved in virtually every connection we make with a website — so it’s a critical part of the Web.
For this, NIST is proposing that the Kyber lattice method will replace ECDH. For this, our 64-byte public key value that Bob and Alice will pass to each other will rise to 800 bytes. This is fine, as it will fit in a single packet. But what if lattice methods were cracked? We thus need a fall-back method that doesn’t involve lattices. One method — Classic Mceliece — has been around for a long time and is still uncracked, so it might be a strong contender. As we will find, though, it will have a significant impact on our key exchange methods — especially in the size of the public key.
And, so, did you know that if Classic Mceliece is adopted for TLS handshaking, the public key will be 261,120 bytes in size and will thus require 174 data packets to pass it? The key sizes for other PQC method are:
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)
Bike128 1,541 3,114 1,573 Code-based
Bike192 3,083 6,198 3,115 Code-based
Bike256 5,122 10,276 5,154 Code-based
HQC128 2,249 2,289 4,497 Code-based
HQC192 4,522 4,562 9,042 Code-based
HQC256 7,245 7,285 14,485 Code-based
McEliece348864 261,120 6,492 196 Code based
McEliece460896 524,160 13,608 156 Code based
McEliece6688128 1,044,992 13,932 208 Code based
McEliece6960119 1,047,319 13,948 194 Code based
McEliece8192128 1,357,824 14,120 208 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 Isogeny
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)The Mceliece key exchange method was created by Robert J. McEliece, and who passed away in May 2019 at the age of 76. While working on a range of space-related projects, he contributed in many areas including with information transmission and storage. Robert eventually was awarded the Claude E. Shannon Award for his work, and gave many memorable talks.
His best know work is around error-correcting codes, including within convolution codes, and now his work is causing great attention in creating an encryption system that would be robust against a quantum computer.
Robert McEliece
Many of our public key methods are based on discrete logarithms and which build on the theories created by John Napier. Bitcoin, Tor, smart cards, Wif-fi, and many other applications use discrete logarithms. But these methods, and other public-key methods, are at risk from quantum computers. One contender is the McEliece Cryptography method.
In a lesson for any modern researcher, in just two pages, Robert McEliece, in 1978, outlined a public key encryption method based on Algebraic Coding — now known as the McEliece Cryptography method [paper]. It is an asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender for a trapdoor method. Unfortunately, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers.
It has basically drifted for nearly 40 years. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor’s algorithm [here].
NIST has now started to move on quantum robust methods with a paper outlining the requirement for new cryptography methods, as a large-scale quantum computer will break most of the currently available public-key systems, including RSA and discrete logarithm methods. Overall public key encryption is most often used to protect secret keys used in symmetric encryption, and to prove identity. A large-scale breach of a public key would lead to a complete lack of trust on the Internet for the hacked entity.
The McEliece method
The McEliece method uses code-based cryptography. Its foundation is based on the difficulty in decoding a general linear code and is generally faster than RSA for encryption and decryption. Within it, we have a probabilistic key generation method, which is then used to produce the public and the private key. The keys are generated with the parameters of n, k and T.
The keys are generated with the parameters of n, k and t. With this, we create an [n,k] matrix of codes, and which is able to correct t errors. In his paper, McEliece defines defines n=1024, k=524, t=50, and which gives a public key size of 524x(1024–524) = 262,000 bits. In the example above we use k=1608, N=2048 and T=40, which gives a public key size of 1608x(2048–40) — 3,228,864 bits. For quantum robustness it is recommended that N is 6960, k is 5,412 and t is 119 (giving a large key size of 8,373,911 bits.
Performance
And, so, while the lattice methods have equivalent performance to elliptic curve techniques, Mceliece is especially slow for key generation. But, the performance of encapsulating a key and decapsulating it is not too bad [here]:
Mceliece is better for public key encryption?
But, would Mceliece be used in key exchange? Well, because of the key pair generation performance, it is highly unlikely that your browser would be able to create unique key pairs for each session. The focus for Mceliece could be where we need a long-term key pair, and where we use it not for key exchange, but for public key encryption, and where we can encrypt with the public key, and decrypt with the private key. These days, we often use RSA to encrypt something using public key encryption. This is typically an AES key. RSA, too, struggles with key generation, but relatively fast for encryption and decryption. So, Mceliece could be a strong replacement for RSA encryption (but not for RSA signing, as Mceliece doesn’t do digital signing).
Code
We can create a Dotnet console project for .NET 8.0 with:
dotnet new consoleFirst we install the Bouncy Castle library:
dotnet add package BouncyCastle.CryptographyNext some code [here]:
namespace Cmce
{
using Org.BouncyCastle.Pqc.Crypto.Cmce;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var size="mceliece348864";
if (args.Length >0) size=args[0];
var random = new SecureRandom();
var keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece348864r3);
if (size=="mceliece460896") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece460896r3);
else if (size=="mceliece6688128") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6688128r3);
else if (size=="mceliece6960119") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6960119r3);
else if (size=="mceliece6960119") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece6960119r3);
else if (size=="mceliece8192128") keyGenParameters = new CmceKeyGenerationParameters(random, CmceParameters.mceliece8192128r3);
var CmceKeyPairGenerator = new CmceKeyPairGenerator();
CmceKeyPairGenerator.Init(keyGenParameters);
var aKeyPair = CmceKeyPairGenerator.GenerateKeyPair();
var aPublic = (CmcePublicKeyParameters)aKeyPair.Public;
var aPrivate = (CmcePrivateKeyParameters)aKeyPair.Private;
var pubEncoded =aPublic.GetEncoded();
var privateEncoded = aPrivate.GetEncoded();
var bobCmceKemGenerator = new CmceKemGenerator(random);
var encapsulatedSecret = bobCmceKemGenerator.GenerateEncapsulated(aPublic);
var bobSecret = encapsulatedSecret.GetSecret();
var cipherText = encapsulatedSecret.GetEncapsulation();
var aliceKemExtractor = new CmceKemExtractor(aPrivate);
var aliceSecret = aliceKemExtractor.ExtractSecret(cipherText);
Console.WriteLine("Cmce-{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("Ciphertext length:\t\t{0} bytes",cipherText.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 for Mceliece 348864 (128-bit security) [here]:
Cmce-mceliece348864
Private key length: 6492 bytes
Public key length: 261120 bytes
Ciphertext length: 96 bytes
Alice private (first 50 bytes): D1400431A9A9A613AD8BE4DBD5EB83F06DB270BF41F4F5BF3EAD0A9A604D3D8CFFFFFFFF00000000FB0BA600F100A0020409
Alice public (first 50 bytes): 7B832C2A27C75DCAF27A189DE33550777356AE5FD9E26B3541F8E1A4475369EEDD9AAA5DAB04C48D339546986997AAA4F776
Cipher (first 50 bytes): 55DC03B3965AAB2CD0EB3399894ED0E46ABB853B3ED61316AB99974AE5331A61B58028BC0206692028956DD89E3B6ECB6A3B
Bob secret: 78AF1943C129D7296744E4C2D298DAE5
Alice secret: 78AF1943C129D7296744E4C2D298DAE5and for Mceliece 460896: (192-bit security):
Cmce-mceliece460896
Private key length: 13608 bytes
Public key length: 524160 bytes
Ciphertext length: 156 bytes
Alice private (first 50 bytes): E9A425034F39382A139313C0F8B1033D6964776723CE20A17B74ED4F9B825082FFFFFFFF00000000D419E11623092810A10D
Alice public (first 50 bytes): 74D04D58286B87EC03081B5B7362DF5CDC265CAB21A92F0D39F3EAC7DDD48AA4192181BFD5926B50DA5B7FA85B535A5483F4
Cipher (first 50 bytes): 37FE5AC631FA220E195DAF9081B30B47B792D1DC0FD708DE1B7E7E602A961D9056E3BBAC76845D29BFF841952D78EDBDF29C
Bob secret: FA2FD597E10738E78E6C8C9BB07A9C0BAB5D043A1F16A61A
Alice secret: FA2FD597E10738E78E6C8C9BB07A9C0BAB5D043A1F16A61AConclusions
Lattice methods are like the hare, and Mceliece is like the tortoise. But, sometimes the slow and dependable is good.