search

randombit / botan

Cryptography Toolkit
https://botan.randombit.net
BSD 2-Clause "Simplified" License
2.52k stars 556 forks source link

Kyber Standardization Updates #3543

Open randombit opened 1 year ago

randombit commented 1 year ago

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

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

randombit commented 1 year ago

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 commented 1 year ago

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

reneme commented 11 months ago

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:

Probably, "Dilithium" will take a similar path.

randombit commented 11 months ago

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 commented 11 months ago
  • 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 https://github.com/randombit/botan/issues/3697 I proposed a different naming which would prevent such confusion.

falko-strenzke commented 11 months ago

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 commented 8 months ago

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

reneme commented 7 months ago

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.