Missing KEMs

[tarcieri]

This is a tracking issue for KEMs we could potentially add to this repo:

• ML-KEM ("Kyber")
• X25519Kyber768 ("Xyber768")
• X-Wing
• NTRU Prime
• Classic McEliece
• FrodoKEM
• DHKEM
• HQC

Lacking a better place to put this, I'll stick it here, although if someone wants to implement it in earnest it could probably use its own repo since it isn't a proper "KEM":

• FFDH

[tarcieri]

There's already a pure Rust implementation of Kyber here: https://github.com/Argyle-Software/kyber

Unfortunately it doesn't yet implement the kem crate's API. I left a comment about that here: Argyle-Software/kyber#30 (comment)

That said, since there is an existing pure Rust implementation of Kyber I think it might be more interesting to start with X25519Kyber768.

[tarcieri]

Hmm, I guess there's already an implementation of X25519Kyber768 in rust-hpke: https://github.com/bwesterb/rust-hpke/blob/1805102ab387fcbd15ec637fd741e1c4743d159c/src/kem/xyber768d00.rs#L127

@rozbb we're trying to decide what to do with this repo and I guess a big question is whether or not it makes sense to extract KEMs from something like rust-hpke into their own per-algorithm crates so they can be used in applications outside HPKE (though what those applications would be, I'm not sure)

[BlackHoleFox]

... though what those applications would be, I'm not sure

Perhaps something like post-quantum Noise (RWC 2023) or SSH would be good candidates. Snow even has some basic support for Kyber in it due to an older proposed Noise extension.

In general it seems like it'd be good for protocols that have their own public key exchanges/formats defined and won't be adopting HPKE.

[tarcieri]

Yeah, transport encryption seems like a good use case

[bwesterb]

Hmm, I guess there's already an implementation of X25519Kyber768 in rust-hpke: https://github.com/bwesterb/rust-hpke/blob/1805102ab387fcbd15ec637fd741e1c4743d159c/src/kem/xyber768d00.rs#L127

It's merged in an upstream branch: https://github.com/rozbb/rust-hpke/tree/unstable-pq-xyber

Note that there are unfortunately two variants of X25519Kyber768: the one used in TLS and the one used in HPKE.

The TLS variant was first and doesn't hash the X25519 ciphertext into the shared secret — the HPKE variant does. HPKE needs this to remain IND-CCA2 if either X25519 or Kyber is broken. For TLS this is not required, as it has a transcript.

Kyber hashes the ciphertext into the shared secret itself, so there is no need to do that in the hybrid. ML-KEM, the final version of Kyber, is expected not to hash the ciphertext into the shared secret. So for HPKE the hybrid with X25519 needs to hash both the X25519 ciphertext and the Kyber ciphertext.

I prefer to converge on the same hybrid for TLS and HPKE for ML-KEM, but those ciphertext hashes aren't completely negligible with respect to performance, so there is a decent chance the TLS working group will want to keep using its own hybrid.

[tarcieri]

My understanding is the output of the HPKE KEM is the concatenation of the Kyber and X25519 secrets, with the hashing performed by HPKE?

[bwesterb]

HPKE doesn't use X25519 directly, but DHKEM(X25519), which adds some hashing. So the X25519Kyber variant for HPKE also uses DHKEM(X25519) instead of X25519 itself.

[oddcoder]

would there be interest in adding KEMs other than the one standardized by NIST, in particular NTRU-prime and McEliece.

I also want to ask about the scope of RustCrypto, is it just to offer interfaces or also implementation?
For some algorithms (like sha AEAD) I see rustcrypto offering full implementation but for other algorithms (x448 for instance) RustCrypor offers just interfaces. If it is the later, I can try offering some implementation in my free time if you accept PRs but please note I am not expert crypto implementer.

[tarcieri]

@oddcoder I've added NTRU Prime and Classic McEliece to the list.

We mostly provide algorithm implementations using a common interface (the kem crate in this repo's case).

However, in some cases, primarily https://github.com/rustcrypto/signatures, we have provided some common types that various implementations of the same algorithm can share. The main purpose of this is typically so things like hardware-backed implementations of signature algorithms can "plug in" in place of software implementations via traits.

[oddcoder]

Alright then noted, I assume that mean I can try to start implementing NTRU-Prime. Unfortunately I cannot offer proper time line because I do this in my free time. If there is common coding guidelines particular to RustCrypto or anything I should be aware of, please let me know.

[rozbb]

Some broad guidelines now that I've written a KEM impl.

• Make the compiler happy. Notice warnings because sometimes they will catch hard-to-see correctness errors that would otherwise cost you and hour of tracking
• Similarly, make clippy happy. It will also sometimes push you away from indexing into arrays. This is good style and comes with a performance boost.
• Use subtle for constant-time operations. For the PQC KEMs, the only part that needs it is the Fujisaki-Okamoto transform
• Write lots of comments and unit tests. Also reference specific places/algorithms in the paper so any reviewer has a good idea of what's happening
• Prefer simplicity over everything else, at least at first. The first question anyone will ask themselves about a crypto crate is "is this obviously correct and secure?" The smaller and better documented the code is, the easier they can get to that answer
• Similarly, have lots of tests. Correctness tests ("does this work as expected?"), soundness tests ("does this fail when I mess with it?"), regression tests ("did I really fix this bug?"), known-answer tests ("is this compatible with other implementations?")
• Use the kem traits (once they're updated)
• Use the type system to separate the data types you use (pubkey, privkey, ciphertext, shared secret). Especially make it hard to confuse a shared secret and a ciphertext (I've heard one example of someone accidentally sending a shared secret over the wire instead of a ciphertext).

I hope that's helpful and not just idle ranting

[tarcieri]

Use subtle for constant-time operations. For the PQC KEMs, the only part that needs it is the Fujisaki-Okamoto transform

Note: it's also useful for the recently discussed Kyber timing variability in poly_frommsg, where bitwise masking is being used to perform a conditional select. Instead you can use subtle to perform the conditional select using the ConditionallySelectable trait, which acts as an optimization barrier.

[pqcfox]

With the news from this morning that HQC is now selected for standardization by NIST, would it make sense to add HQC to the above desired KEM list?