Classic McEliece
John Mattsson
Thanks Dan, for a very good presentation yesterday. I think NIST should standardize Classic McEliece as there is quite strong interest from both governments and industry and it is very important with open-access standards. Classic McEliece
- is a very conservative choice,
- offers the best performance for static-ephemeral key exchange.
We need replacements not only for ephemeral-ephemeral, but also for static-ephemeral, ephemeral-static, and static-static ECDH [1]. I hope that we in the future will get quantum-resistance NIKE, and I was happy to see that isogeny cryptography is once again a very hot topic [2].
One big deployment of static-ephemeral ECDH is ECIES for encryption of identities (IMSIs) in 5G (mostly over the radio access network) [3]. Both 5G and 6G will migrate to PQC [4]. The small Classic McEliece ciphertext sizes would be very nice in this use case. In 5G (and 6G) the operator generates a key pair and provisions it on the (e)SIM, the UE (which might be constrained) encapsulates, and the core network (which is not constrained) decapsulates. In this use case, key gen performance is irrelevant and decapsulation performance is not so important. My understanding is that Classic McEliece has very good encapsulation performance [5] and that it can be implemented with very little memory [6,7]. The public key sizes (261 kB for mceliece348864) would however be problematic in current (e)SIMs. My understanding is that the mceliece348864 parameters were chosen to maximize security for public keys not larger than 2^18 bytes [8].
Is there any potential for other category 1 security (comparable to AES-128) parameters with smaller public keys?
Cheers,
John Preuß Mattsson, Ericsson
[1] Constrained Radio Networks, Small Ciphertexts, Signatures, and Non-Interactive Key Exchange
[2] An Attack Became a Tool: Isogeny-based Cryptography 2.0 (Eurocrypt 2024)
https://www.youtube.com/watch?v=CpqjkfuXeoQ
[3] Security architecture and procedures for 5G System
https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=3169
[4] Migration to quantum-resistant algorithms in mobile networks
https://www.ericsson.com/en/blog/2023/2/quantum-resistant-algorithms-mobile-networks
[5] What Happens After Kyber? Meet BIKE, HQC and Classical Mceliece
[6] Classic McEliece Implementation with Low Memory Footprint
https://eprint.iacr.org/2021/138.pdf
[7] Classic McEliece on the ARM Cortex-M4
https://eprint.iacr.org/2021/492
[8] Classic McEliece Design Rationale
https://classic.mceliece.org/mceliece-rationale-20221023.pdf
D. J. Bernstein
> One big deployment of static-ephemeral ECDH is ECIES for encryption of
> identities (IMSIs) in 5G (mostly over the radio access network) [3].
public encryption keys listed in the slides---
https://cr.yp.to/talks/2024.09.17/slides-djb-20240917-mceliece-16x9.pdf
---are (1) encryption of a file to the static public key of the user
authorized to read the file, as in Microsoft's EFS (this is a separate
security layer beyond full-disk encryption); and (2) typical PGP email
encryption to the static public key of the receiving user.
The slides also listed TLS server keys and authentication tokens as
examples of static public keys that currently use signatures but that
can easily use KEMs instead; and TLS CA keys as an example where the
current data flow requires signatures.
It would be interesting to build more systematic tables of applications
for each key type (one-time encryption keys vs. static encryption keys
vs. static signature keys vs. the flexible case of authentication keys),
given the post-quantum size differences.
> The small Classic McEliece ciphertext sizes would be very nice in this
> use case. In 5G (and 6G) the operator generates a key pair and
> provisions it on the (e)SIM, the UE (which might be constrained)
> encapsulates, and the core network (which is not constrained)
> decapsulates.
that encryption be to a core public key chosen independently of the
identity? I would then store this Classic McEliece public key once on
the phone (the UE), and then, for each encryption, stream the public key
(as in McTiny) through the eSIM chip, so the chip can get away with very
little storage. The chip can check a key hash to make sure it's talking
to the approved public key. Streaming can also be used for multiple
public keys, but then one should distinguish that key choice being
secret (the simplest ORAM approach being to stream all the keys) from
being public (just stream the selected key). In all cases, what goes
onto the network is just the ciphertext.
Of course, McEliece can also protect the confidentiality and integrity
of subsequent communication between the core and the eSIM. Provision the
eSIM with a McEliece private key, and remember the public key in the
core; the (encrypted) identity tells the core which public key to use,
and what's sent through the network to the eSIM is just the ciphertext.
---D. J. Bernstein (speaking for myself)
John Mattsson
Hi,
Below are answers how 5G works, 6G is currently in a requirement/research phase but is expected to be an evolution. The first commercial 6G systems are expected in 2030 [1].
D. J. Bernstein wrote:
>For maximum security of public-key encryption of identities, shouldn't
>that encryption be to a core public key chosen independently of the
>identity?
Yes, it can be assumed that the static encapsulation key is used for a large number of identities/SIM cards. It is up to operator policy how many encapsulation keys to use.
D. J. Bernstein wrote:
>I would then store this Classic McEliece public key once on
>the phone (the UE), and then, for each encryption, stream the public key
>(as in McTiny) through the eSIM chip, so the chip can get away with very
>little storage. The chip can check a key hash to make sure it's talking
>to the approved public key. Streaming can also be used for multiple
>public keys, but then one should distinguish that key choice being
>secret (the simplest ORAM approach being to stream all the keys) from
>being public (just stream the selected key). In all cases, what goes
>onto the network is just the ciphertext.
Currently, the static encapsulation key should be in the eSIM when it is sent to the UE manufacturer. And for removable SIMs, the key needs to be stored in the SIM. The encapsulation is done in the UICC or the UE. The decapsulation is done by the home operator. SIM storage can range from a few kB to several MB. Future SIMs could store Classic McEliece keys, but it might be problematic for current SIMs.
Distributing keys in the UE and identifying them with a hash would be a big change, and operators might not want to share information regarding their encapsulation keys and protection profiles with all UE manufacturers. Operators can use the predefined profiles (Currently X25519 + AES-128 + SHA-256 and secp256r1 + AES-128 + SHA-256) or define their own profiles. The home operator can configure that encapsulation of the identity is done inside the SIM.
The ability to stream the public key, the low memory footprint, and the excellent encapsulation performance was positive surprises for me when I read up more on Classic McEliece after your presentation. While I really like the conservative security, the performance aspects are what makes me interested in actually using it practically. I think the Classic McEliece team should market the performance aspects even more.
D. J. Bernstein wrote:
>Of course, McEliece can also protect the confidentiality and integrity
>of subsequent communication between the core and the eSIM. Provision the
>eSIM with a McEliece private key, and remember the public key in the
>core; the (encrypted) identity tells the core which public key to use,
>and what's sent through the network to the eSIM is just the ciphertext.
Yes, it could. Communication between the SIM and the home operator is however a completely different protocol.
---
NIST IR 8413-upd1 [2] states about Classic McEliece that:
"but its total cost would be much greater than any of the other candidate KEMs if the cost of transmitting the public key were included."
This seems incorrect. Unless I calculate something wrong, mceliece348864 has lower total cost (in bytes) than ML-KEM-512 after just 388 encapsulations. Many use cases would do far more encapsulations per static key.
“in settings where a public key is reused many times and does not be need to
be retransmitted for each new communication, it is possible that the performance profile of Classic McEliece could have some advantages”
This seems too pessimistic, seems quite clear that Classic McEliece has performance advantages in many use cases using static encapsulation keys. Especially if the public key is provisioned during manufacturing, but also when it is transmitted once.
“NIST would like feedback on specific use cases for which Classic McEliece would be a good solution.”
Classic McEliece seems like a good solution for most use cases of static encapsulation keys including identity protection in mobile systems. Mobile systems have always been designed with crypto agility in mind, and we like to have at least two different cryptographic algorithms implemented for everything. In case vulnerabilities (theoretical or implementation) are found in one algorithm, it should be possible to very quickly switch to another algorithm. ML-KEM and Classic McEliece seems to complement each other very well.
Cheers,
John Preuß Mattsson
Expert Cryptographic Algorithms and Security Protocols, Ericsson
[1] 6G standardization – an overview of timeline and high-level technology principles
https://www.ericsson.com/en/blog/2024/3/6g-standardization-timeline-and-technology-principles
[2] Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process
https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413-upd1.pdf