Classic McEliece Security Considerations

2.1. Cryptosystem information

https://classic.mceliece.org/mceliece-spec-20221023.pdf [CM-spec] is the authoritative definition of Classic McEliece. A supplement https://classic.mceliece.org/mceliece-pc-20221023.pdf [CM-pc] describes optional parameter sets labeled pc.¶

https://classic.mceliece.org/mceliece-security-20221023.pdf [CM-security] is the official guide for Classic McEliece security reviewers.¶

https://classic.mceliece.org/mceliece-rationale-20221023.pdf [CM-rationale] is the official statement of the Classic McEliece design rationale.¶

Further official Classic McEliece documents are on the Classic McEliece team site https://classic.mceliece.org [CM-website].¶

2.2. Information for implementors

https://classic.mceliece.org/mceliece-impl-20221023.pdf [CM-impl] is the official guide for Classic McEliece implementors. It reviews security goals for implementations, describes considerations in selecting a parameter set, and includes pointers to further resources.¶

The official Classic McEliece software is released via the SUPERCOP framework from https://bench.cr.yp.to, in subdirectories such as crypto_kem/mceliece6688128 named by Classic McEliece parameter sets. SUPERCOP automatically carries out various positive tests, negative tests, interoperability tests across multiple implementations in SUPERCOP, and constant-time tests.¶

The official Classic McEliece integration is libmceliece from https://lib.mceliece.org [libmceliece-website]. This library includes its own test framework.¶

Some portions of the software have been formally verified. https://lib.mceliece.org/verification.html tracks this.¶

3.1. API overview

Classic McEliece is a family of key-encapsulation mechanisms (KEMs). Each parameter set specifies one KEM in the family. Each KEM provides three operations: keygen produces a public key and private key; enc produces a session key and ciphertext given a public key; dec produces a session key given a ciphertext and a private key.¶

Session keys are 32 bytes. Applications typically use session keys as keys for an authenticated cipher to encrypt and authenticate user data, or as message-authentication keys if messages are public.¶

3.2. Parameter sizes

The selected parameter sets supported by the official Classic McEliece software have five sizes. The following numbers are copied from https://classic.mceliece.org/impl.html:¶

https://classic.mceliece.org/nist/mceliece-20190331-mods.pdf states the design goals of the selected parameter sets. For example, mceliece6688128 is designed for "optimal security within 2^20^ bytes if n and t are required to be multiples of 32".¶

The Classic McEliece team recommends the mceliece6* parameter sets for long-term security. mceliece6688128 is a reasonable default choice.¶

Comparison to alternatives: For static public keys such as long-term encryption keys and long-term authentication keys, Classic McEliece uses less bandwidth than most post-quantum KEMs and less bandwidth than most post-quantum signature systems. For one-time public keys, Classic McEliece uses more bandwidth than most other options. For intermediate possibilities, the comparison depends on the number of ciphertexts sent per key.¶

3.3. Parameter options

Within each parameter size, there are two non-interoperable options, called pc and non-pc. Advantages and disadvantages of pc are presented in https://classic.mceliece.org/nist/mceliece-mods3-20221023.pdf. The pc ciphertexts are 32 bytes larger than non-pc ciphertexts. Non-pc is a reasonable default choice.¶

The specification and some test frameworks also distinguish an f (and pcf) option from non-f, where f provides faster key generation and non-f provides simpler key generation. However, f and non-f are interoperable: the same enc/dec implementations handle both f keys and non-f keys.¶

The Classic McEliece specification includes internal details of encoding of each object (public key, private key, ciphertext) as a byte string, and includes exact specification of how each possible input string is handled, depending on pc, f, and the parameter size. The details are designed to avoid various security risks. The Classic McEliece caller uses keygen, enc, and dec without being exposed to the internal details.¶

4.1. Cryptosystem security goals and basis for confidence

https://classic.mceliece.org/index.html says that Classic McEliece is "a KEM designed for IND-CCA2 security at a very high security level, even against quantum computers".¶

Classic McEliece appeared in 2017, including the 6960119 and 8192128 parameter sets. The list of parameter sets was later expanded to include smaller options. No parameter sets have been dropped. The cryptosystem details remain stable so that security analyses continue to apply. The 2017 software is interoperable with the current software. Classic McEliece is not a moving target.¶

Furthermore, any QROM IND-CCA2 attack against Classic McEliece tightly implies a one-wayness attack against the original 1978 McEliece cryptosystem. Quantitatively, for each of the selected parameter sets, B bits of one-wayness security imply at least B−5 bits of QROM IND-CCA2 security. One-wayness is the simplest property of a public-key cryptosystem and is the most common focus of the attack literature.¶

Because of this implication, confidence in the QROM IND-CCA2 security of Classic McEliece follows from confidence in the one-wayness of the original McEliece cryptosystem. This connection is the reason for the Classic McEliece name.¶

https://classic.mceliece.org/papers.html [CM-papers] includes pointers to many papers from many authors over many years studying the cost of one-wayness attacks against the McEliece cryptosystem, including quantum attacks. Confidence in the hardness of this one-wayness problem comes not just from the volume of the literature but from how well the problem has resisted attack. The algorithm can be traced back to the initial [McEliece] paper from 1978.¶

Quantitatively, https://cat.cr.yp.to/cryptattacktester-20240612.pdf is a Crypto 2024 paper presenting high-assurance predictions of the number of bit operations used by various one-wayness attacks, showing the effect of many years of attack development. For mceliece6688128, the predictions are 2^257.36^ bit operations for a modern attack, compared to 2^275.41^ bit operations for attack ideas from the 1980s.¶

Bitcoin currently carries out about 2^112^ bit operations per year. A large security margin beyond this is recommended as protection against further refinements in attack algorithms, against attackers with larger resources, against future attackers with better computer technology, against multi-target speedups, and against quantum speedups.¶

Comparison to alternatives: Post-quantum KEMs usually start from problems where attack costs are decreasing much more quickly than the cost of one-wayness attacks against the McEliece system, usually add further potentially damaging modifications to those problems as part of building a cryptosystem, and usually add subsequent "tweaks" that prevent earlier security analyses from applying to the latest cryptosystem details. Furthermore, many post-quantum KEMs do not provide tight QROM IND-CCA2 analyses starting from one-wayness: they allow looseness or assume stronger properties than one-wayness, so QROM IND-CCA2 security can be many bits weaker than one-wayness.¶

4.2. Security modularization

Classic McEliece is designed to encrypt a random session key, not to encrypt a user message. In other words, Classic McEliece is a KEM, not a PKE.¶

There is a well-known generic transformation ("KEM-DEM") that combines a KEM with symmetric cryptography to produce a PKE that encrypts a user message. This transformation allows designers to focus on the simpler task of designing a KEM.¶

Similarly, there are generic transformations that provide various properties beyond IND-CCA2 security. These transformations allow designers to focus on the simpler task of providing IND-CCA2 security.¶

Part of the official Classic McEliece design rationale stated in https://classic.mceliece.org/mceliece-rationale-20221023.pdf is the following: "Classic McEliece follows the principle that any generic transformation aiming at a goal beyond IND-CCA2 is out of scope for a KEM specification. Factoring the transformation out of KEM specifications simplifies the cryptographic ecosystem, making design and review easier, because the transformation is modularized instead of being handled redundantly by each cryptosystem. Each component is simpler, without any change in the composition provided to the end user."¶

Comparison to alternatives: IND-CCA2 KEMs have become a popular target for cryptosystem design, but some cryptosystems have other targets. For example, some public-key cryptosystems are designed directly as PKEs, rather than focusing on a KEM and relying on generic transformations. Some KEMs are designed to integrate properties beyond IND-CCA2 security, rather than focusing on IND-CCA2 security and relying on generic transformations.¶

4.3. Implementation security

Two resources regarding Classic McEliece implementation security are https://lib.mceliece.org/security.html and the official guide for implementors.¶

The main computations inside Classic McEliece are operations on bit vectors and on polynomials modulo 2. These computations avoid questions regarding variable-time integer multipliers on some CPUs. However, it is still important to carry out constant-time tests.¶

Post-quantum software is more complicated than pre-quantum software and can easily have bugs that compromise security. (Formal verification can convincingly eliminate bugs, but post-quantum software is currently only partially verified.) ECC+PQ double encryption reduces the impact of PQ bugs.¶

Cryptographic software is presumably breakable if the computer's RNG is weak, if other parts of the computer leak RNG data or other internal cryptosystem data, if attackers can access physical sensors such as electromagnetic sensors close to the computer, or if attackers have enough control over the computer to create faults in computations. Commonly discussed mitigations include recomputations to address physical faults, "masking" and "hiding" to reduce physical leakage of secret data, zeroing secrets after the secrets are used, combining multiple RNGs, centralizing RNGs for auditability, fixing security problems elsewhere in the computer, and isolating sensitive computations on separate devices.¶

4.4. Error-free APIs

For mceliece6960119, public keys and ciphertexts include some padding bits that are always set to 0 on encoding and that are required to be 0 by "narrow" decoders. For the other selected sizes (mceliece348864, mceliece460896, mceliece6688128, and mceliece8192128), all byte strings of the specified lengths are accepted as inputs.¶

Applications that focus on the other selected sizes (such as 6688128), or that do not care about changes in padding bits, can use error-free APIs for keygen, enc, and dec.¶

Most KEMs, including Classic McEliece, build dec internally on top of a simpler decryption mechanism. For "implicit rejection" KEMs, including Classic McEliece, ciphertexts rejected by the internal decryption mechanism produce pseudorandom KEM session keys, not KEM errors.¶

For some KEMs, the internal decryption mechanism occasionally rejects valid ciphertexts. The sender and receiver then occasionally end up with different session keys, normally triggering failures in higher-level protocols even when there are no KEM API errors. A KEM that reports a very small probability of these "decryption failures" might still be vulnerable to "failure boosting" attacks that search for valid ciphertexts that are more likely to fail and that deduce secret keys from the pattern of failures. For Classic McEliece, the internal decryption formulas are guaranteed to work for all valid ciphertexts; this is formally verified in https://cr.yp.to/papers.html#goppadecoding.¶