McEliece Key Exchange: The Tortoise Shell Is A Little Broken, But It Is Still Secure

McEliece Key Exchange: The Tortoise Shell Is A Little Broken, But It Is Still Secure

Daniel J. Bernstein, Tanja Lange, Christiane Peters create a new record in cracking McEliece Key Exchange

We had a great talk with the creator of Elliptic Curve Cryptography (ECC) on Friday (Neal Koblitz), and he talked about the spy vs. spy culture in cryptography. For this we create ciphers, and then try to knock them down. With RSA, there are a number of live factorization challenges, and where we see that a 829-bit modulus was cracked in 2020:

But, RSA will fail within a post-quantum computer world. Thus we must find a replacement, and the McEliece key exchange method is an important contender — especially as it has been around for so long, and still seen to be secure.

To assess the security of the coding theory that McEliece is based on, in 2019, Julien Lavauzelle, Matthieu Lequesne, and Nicolas Aragon created a range of challenges for the coding theory method used within the McEliece key exchange method [here]:

Overall, McEliece is slowly moving towards standardization by NIST, even though it is relatively slow for key generation (compared with Kyber) [here]:

And that it has a relatively large public key size [here]:

But now a length of length-1223 and length-1284 was broken in 2021, and outlined within a paper at Eurocrypt 2022 [here][2]:

But, just in the past few days, Daniel J. Bernstein, Tanja Lange, Christiane Peters overtook these by cracking McEliece-1347 [here]:

Overall, there are no new cracks defined in the paper, as they are all just based on this paper from 2008 [here][1]:

The fact that this is not a new attack is good news for McEliece, as there have been no better attacks than this one in the past 15 years. To break the smallest NIST-defined Classic McEliece parameter set (mceliece348864 which has a length of 3488 and 64 errors) would need all the computing power for Bitcoin mining over the past year to crack one ciphertext. It is likely though that mceliece6960119 (a length of 6960 and 119 errors) and mceliece6688128 (a length of 6688 and 128 errors) will be used in production, and which have a large amount of headroom for cracking.

If you are interested, here’s a bit of history about McEliece:

References

[1] Bernstein, D. J., Lange, T., & Peters, C. (2008). Attacking and defending the McEliece cryptosystem. In Post-Quantum Cryptography: Second International Workshop, PQCrypto 2008 Cincinnati, OH, USA, October 17–19, 2008 Proceedings 2 (pp. 31–46). Springer Berlin Heidelberg.

[2] Esser, A., May, A., & Zweydinger, F. (2022, May). Mceliece needs a break–solving mceliece-1284 and quasi-cyclic-2918 with modern isd. In Advances in Cryptology–EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30–June 3, 2022, Proceedings, Part III (pp. 433–457). Cham: Springer International Publishing.