Kyber Standardization Updates

[randombit]

We shouldn't change anything right away but the Kyber designers are making changes to their code to target the 'final' version of Kyber.

So far these seem to include

• No more 90s mode (this will allow a nice simplification of the codebase)
• Using SHAKE128 instead of CTR-DRBG to generate the test vectors
• Using SHAKE256 instead of SHA-3 for PRF

Looking over the commits I don't see any changes to the core encap/decap algorithms

[randombit]

https://www.federalregister.gov/documents/2023/08/24/2023-18197/request-for-comments-on-draft-fips-203-draft-fips-204-and-draft-fips-205

[randombit]

https://csrc.nist.gov/pubs/fips/203/ipd

[reneme]

Now that the draft standard documents are out, we should agree on a transition strategy. NIST uses "ML-KEM" for the to-be-standardized algorithm. Going forward, I'll refer to our existing implementation as "Kyber", and use "ML-KEM" when I mean the draft revision.

Regarding semver: Do you think we'll have to keep Kyber until Botan 4.0 or could we remove it earlier? I'm assuming that it could be removed soon after the final ML-KEM standard is finalized and published by NIST.
Internally, hybrid TLS (#3609) might benefit from at least a short-term backward compatibility, pending update of the relevant external cloud endpoints.

My working assumption would roughly look like this:

• Botan 3.2.0 (maybe 3.3.0) should provide "ML-KEM" and "Kyber"/"Kyber-90s" (both deprecated)
• ML-KEM should be marked "experimental" in a sense that draft-standard updates would simply be applied in the next release, without backward compatibility
• Botan 4.0.0 (at the latest) would remove support for "Kyber"/"Kyber-90s"

Probably, "Dilithium" will take a similar path.

[randombit]

In large part it depend on how big the difference is between the proposed and final versions. From what I've seen it is pretty minor, and we could accommodate it with just a new KyberMode.

I think we should deprecate Kyber 90s mode, since it is not only not going to be in the final version but also many Kyber implementations already use only the SHAKE based primitives, and 90s mode leads to some significant extra complexity in the code, eg the CTR XOF. We could probably consider an accelerated (pre 4.0) removal here.

I rather suspect that round2 SHAKE based Kyber is here to stay. There are already a number of deployed systems that use it (for instance Signal) and in the near term that is likely to increase since nobody implements the final NIST version yet, so any new systems adopting Kyber today are going to pick up the non-final version.

Re terminology, I'd prefer continuing to call it Kyber since that is the name under which it is known generally. I've already had some experience with calling something under the name from a standard rather than the conventional name ("EMSA3" vs "PKCS1v15") and it just leads to user confusion.

[falko-strenzke]

• ML-KEM should be marked "experimental" in a sense that draft-standard updates would simply be applied in the next release, without backward compatibility

I would prefer to refrain from this approach. Marking it "experimental" isn't solving the problem of those who will use it for experimental implementations that are supposed to be interoperable with other implementations. Silently changing the implementation is not a good idea. In #3697 I proposed a different naming which would prevent such confusion.

[falko-strenzke]

Re terminology, I'd prefer continuing to call it Kyber since that is the name under which it is known generally. I've already had some experience with calling something under the name from a standard rather than the conventional name ("EMSA3" vs "PKCS1v15") and it just leads to user confusion.

I think the experience regading EMSA3 and PKCS1v15 cannot be so easily generalized. We also have the example of Keccak and SHA3, where today colloquially Keccak denotes the submission version without any final bit padding that is different from SHA3. I agree that it may make sense to keep the final submission version (= currently implemented version if am not mistaken) under the name "Kyber," but the finally standardized version needs to be named "ML-KEM". Otherwise it will be confusion, as "Kyber" will most likely suggest the final submission version to many. Naming the finally standardised version anything else than "ML-KEM" will lead to confusion.

[reneme]

For reference: additional test vectors: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/aCAX-2QrUFw

[reneme]

After refactoring the existing implementation of Kyber-R3 (#3887), I added an implementation of ML-KEM-ipd (#3893). In the hope that the final standard won't contain major changes, we should be set for a speedy adoption.

[reneme]

#3893 is merged.