Implement new ML-KEM hybrid key exchange in TLS

[dstebila]

The new code points for ML-KEM hybrid key exchange in TLS are now available in https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-mlkem/

Note that order of concatenation has changed since previous drafts.

Depends on open-quantum-safe/liboqs#1899

[baentsch]

Thanks for the heads-up, @dstebila

Note that order of concatenation has changed since previous drafts.

Is your suggestion then to adapt this in the implementation generally (if I get it right, breaking all interop with old releases, i.e., assigning new code points/OIDs to all algorithms) or just for ML-KEM (minimizing the breakage with old code)?

[beldmit]

https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-mlkem/ seems to be not adopted by TLS WG yet.
And, even more, it's probably worth using p384 curve as a part of specification.

• @tomato42

[tomato42]

@dstebila I might have missed it, but when do you plan to raise it for discussion on the IETF TLS mailing list?

[bhess]

The order of the shares seem to be inconsistent between X25519MLKEM768 and SecP256r1MLKEM768 in https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-mlkem/01/:

"When the X25519MLKEM768 group is negotiated, the client's key_exchange value is the concatenation of the client's ML-KEM-768 encapsulation key and the client's X25519 ephemeral share."

and

"When the SecP256r1MLKEM768 group is negotiated, the client's key_exchange value is the concatenation of the secp256r1 ephemeral share and ML-KEM-768 encapsulation key."

The same for "server share" and "shared secret".

Is this intentional @dstebila ?

[dstebila]

Note that order of concatenation has changed since previous drafts.

Is your suggestion then to adapt this in the implementation generally (if I get it right, breaking all interop with old releases, i.e., assigning new code points/OIDs to all algorithms) or just for ML-KEM (minimizing the breakage with old code)?

I wouldn't change the order in any of the previous hybrids we have, so it would just be for the ML-KEM code points in this document.

[dstebila]

https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-mlkem/ seems to be not adopted by TLS WG yet. And, even more, it's probably worth using p384 curve as a part of specification.

* @tomato42

@dstebila I might have missed it, but when do you plan to raise it for discussion on the IETF TLS mailing list?

Kris Kwiatkowski is leading that document and I assume will be notifying the TLS mailing list about it shortly. The TLS WG chairs prompted for this so they are aware of it.

[dstebila]

The order of the shares seem to be inconsistent between X25519MLKEM768 and SecP256r1MLKEM768 in https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-mlkem/01/:

"When the X25519MLKEM768 group is negotiated, the client's key_exchange value is the concatenation of the client's ML-KEM-768 encapsulation key and the client's X25519 ephemeral share."

and

"When the SecP256r1MLKEM768 group is negotiated, the client's key_exchange value is the concatenation of the secp256r1 ephemeral share and ML-KEM-768 encapsulation key."

The same for "server share" and "shared secret".

Is this intentional @dstebila ?

Yes. Apparently NIST SP 800-56Cr2 is written so as to require the concatenation method place FIPS-approved keying material first, followed by auxiliary keying material. Since X25519 is not FIPS-approved, in order for X25519MLKEM768 to be FIPS-approvable, one would have to put the FIPS-approved algorithm (ML-KEM 768) first, and the non-FIPS approved algorithm second (X25519). Whereas for SecP256r1MLKEM768, since both are FIPS-approved, either can go first, and past codepoints had the ECC algorithm go first, so that's being maintained.

[bhess]

Thanks for the background @dstebila.

So to avoid much custom logic, the following rule should apply, right?

• If the PQ algorithm is FIPS-approved and the classical algorithm is not FIPS approved -> PQ share is first in the concatenation
• Otherwise -> Classical share is the first in the concatenation

[dstebila]

Thanks for the background @dstebila.

So to avoid much custom logic, the following rule should apply, right?

* If the PQ algorithm is FIPS-approved and the classical algorithm is not FIPS approved -> PQ share is first in the concatenation

* Otherwise -> Classical share is the first in the concatenation

That is the logic employed in draft-kwiatkowski-tls-ecdhe-mlkem. That being said, many of our existing hybrids start with a non-FIPS-approved algorithm like x25519 or x448, and I don't think we should go through the effort of changing all those -- no one's trying to get those FIPS-approved, they're just for prototyping/experimentation.

[bhess]

That is the logic employed in draft-kwiatkowski-tls-ecdhe-mlkem. That being said, many of our existing hybrids start with a non-FIPS-approved algorithm like x25519 or x448, and I don't think we should go through the effort of changing all those -- no one's trying to get those FIPS-approved, they're just for prototyping/experimentation.

I agree, and the rule above would also capture these existing hybrids.

[baentsch]

I wouldn't change the order in any of the previous hybrids we have, so it would just be for the ML-KEM code points in this document.

Hmm, I'm a bit concerned about the additional code complexity this special treatment adds (and I don't like code complexity, particularly in security software). Wouldn't it be (implementation and also security wise) more sensible to change the order for all algorithms? Does the spec prohibit this? What otherwise speaks against this given

they're just for prototyping/experimentation.

?

[dstebila]

I wouldn't change the order in any of the previous hybrids we have, so it would just be for the ML-KEM code points in this document.

Hmm, I'm a bit concerned about the additional code complexity this special treatment adds (and I don't like code complexity, particularly in security software). Wouldn't it be (implementation and also security wise) more sensible to change the order for all algorithms? Does the spec prohibit this? What otherwise speaks against this given

they're just for prototyping/experimentation.

?

It's true we don't make any promises about stability of these across releases, but it still seems courteous to our users to avoid changes if it's not too difficult. How much extra logic would be needed to keep the current order for our current hybrids but also accommodate the reversed order for the one new hybrid?

[baentsch]

How much extra logic would be needed to keep the current order for our current hybrids but also accommodate the reversed order for the one new hybrid?

I'm not sure that is a fair question to ask: We currently have absolutely no algorithm-specific code in oqsprovider exactly for the reason to make the code easy(er) to defend, understand, e.g., by third parties assessing it, and test.

Any "special code" goes against this primary goal. It will require extra testing, extra documentation, etc beyond just the algorithm-specific extra logic you're asking for. I'm all for courteousness, but should it trump security goals?

I totally would subscribe to your view if we'd agree to retain the original OQS mission, but this is not what the next goal seems to be.

Whichever way the discussions in the links above go, allow me thus to repeat my question to gauge options:

Does the spec prohibit this?

[dstebila]

How much extra logic would be needed to keep the current order for our current hybrids but also accommodate the reversed order for the one new hybrid?

I'm not sure that is a fair question to ask: We currently have absolutely no algorithm-specific code in oqsprovider exactly for the reason to make the code easy(er) to defend, understand, e.g., by third parties assessing it, and test.

Could we accomplish this without algorithm-specific code? For example by extending the mix_with data structure in generate.yml to allow the order of hybridization to be specified?

Does the spec prohibit this?

draft-ietf-tls-hybrid-design doesn't prohibit this.

draft-kwiatkowski-tls-ecdhe-mlkem will require that X25519MLKEM768 has ML-KEM first, but that SecP256r1MLKEM768 has ECC first.

[dstebila]

Code points for TLS have now been defined by IANA for SecP256r1MLKEM768 and X25519MLKEM768

[baentsch]

open-quantum-safe/liboqs#1915 (comment) indicates an entity's interest to implement X25519MLKEM768 -- which according to the logic above should already work with the current code base as soon as we simply update the code point(s) in configure.yml:

oqs-provider/oqs-template/generate.yml

Line 171 in 2cdbc17

nid: '0x2FB4'

with the value 4588 from https://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8

[baentsch]

which according to the logic above should already work with the current code base

oops -- my bad: x25519-mlkem768 exactly requires a change of order while p256-mlkem768 should be OK with the current code base, right?

[dstebila]

which according to the logic above should already work with the current code base

oops -- my bad: x25519-mlkem768 exactly requires a change of order while p256-mlkem768 should be OK with the current code base, right?

Right.

[baentsch]

@dstebila if I'm not totally mistaken, @bhess agreed to take this algorithm-specific order reversal on, right?

[dstebila]

@dstebila if I'm not totally mistaken, @bhess agreed to take this algorithm-specific order reversal on, right?

Yes, I just assigned this issue to him in Github.

[baentsch]

Yes, I just assigned this issue to him in Github.

No, you assigned it to me. I switched it over. This just to check I didn't misunderstand.

[dstebila]

Yes, I just assigned this issue to him in Github.

No, you assigned it to me. I switched it over. This just to check I didn't misunderstand.

Oh gosh, you're right. Sorry. Apparently I can only handle one "b" username.

[ghen2]

x25519-mlkem768 exactly requires a change of order while p256-mlkem768 should be OK with the current code base, right?

Does it make sense to reverse the name then, like Mozilla did: mlkem768x25519 ?

Perhaps also the to-be standard naming in draft-kwiatkowski-tls-ecdhe-mlkem.

[baentsch]

x25519-mlkem768 exactly requires a change of order while p256-mlkem768 should be OK with the current code base, right?

Does it make sense to reverse the name then, like Mozilla did: mlkem768x25519 ?

Perhaps also the to-be standard naming in draft-kwiatkowski-tls-ecdhe-mlkem.

That's actually a good idea, @ghen2 -- the only "risk" I see in this is a bit of confusion: We currently use "postfix classic crypto" naming for composite algs and prefix for hybrid. But then again, if Mozilla does this, that'd be a very good rationale to follow suit. Objections anyone?

[t-j-h]

I'd tend to stick with the actual naming used in the specification at https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-mlkem/ rather than reflecting the field ordering in the naming which is more of an implementation detail.

For this reason we put the ML-KEM-768 shared secret first in X25519MLKEM768, and the secp256r1 shared secret first in SecP256r1MLKEM768.

[bwesterb]

Both orders are confusing

• The present order is confusing for those that implement the key agreement..
• The reverse order is confusing to those that need to pick which key agreement to us, as it doesn't align with the existing X25519Kyber768, SecP256r1MLKEM768, and SecP256r1MLKEM768.

As there are many more of the latter than the former, the present order makes more sense.

Google/Chrome uses the present order.

[pi-314159]

@bhess @dstebila

I think we also need to update x25519_mlkem512 and x448_mlkem768. It might be easier to revise the order of all hybrids involving x25519 or x448 (such as x25519_bikel1) rather than focusing solely on the mlkem variants. This approach simplifies the implementation: we can simply check if the classical algorithm is x25519 or x448. If it is, we place pq-algs first; otherwise, x25519/x448 comes first. This method eliminates the need to modify generate.yml or add algorithm-specific code (like mlkem).

[baentsch]

Changing the order of all 'x' hybrids sounds sensible given that CF and Google seem to terminate support for the Kyber x-hybrid... So why should oqsprovider keep supporting this?

[t-j-h]

The updated openssl code for tracing that is in master shows the new allocated ids as X25519MLKEM768 and SecP256r1MLKEM768 which matches the specification wording (and remains consistent with the Kyber draft naming usage) so leaving the order matching rather than changing it seems consistent and logical.

An outcome where oqs_provider has a different name than what the trace in openssl itself uses would be confusing.

[baentsch]

@t-j-h my suggestion above only pertained to the implementation as per suggestion by @pi-314159 , not the name. Keeping the order in naming is majority agreed, I'd say.

[baentsch]

@bhess fwiw, we should then also follow the names verbatim (capitalization, no dashes)--which requires significant changes to the jinja2 logic I'm afraid...

[pi-314159]

@baentsch @bhess

I've made a commit that reverses the order of all hybrids involving X25519 in a new BoringSSL branch (note that BoringSSL doesn’t support X448). You can view the commit here: open-quantum-safe/boringssl@c1a84f7.
I tested it with Google's implementation.

Regarding the naming: I didn't change the order in names.

[dstebila]

FYI here is Google's post describing their plan for transitioning hybrid to ML-KEM: https://security.googleblog.com/2024/09/a-new-path-for-kyber-on-web.html

[ghen2]

It might be easier to revise the order of all hybrids involving x25519 or x448 (such as x25519_bikel1) rather than focusing solely on the mlkem variants. This approach simplifies the implementation: we can simply check if the classical algorithm is x25519 or x448

But that means it will not be possible for servers to (temporarily) support both x25519_kyber768 (0x6399) and x25519_klkem768 (0x11ec) at the same time to ease client transition, as they need a different order?

(for clients it's more expensive to support both at the same time, so Chrome and Firefox will switch directly from one to the other.)

[pi-314159]

@ghen2 I don't think that's a problem because

1. there's no promise about stability of these releases
2. you can always use p256_kyber768
3. if you really need 0x6399 and 0x11ec, try OQS-BoringSSL (e.g., nginx-quic and curl-quic, they're built with OQS-BoringSSL). But keep in mind that 0x6399 in BoringSSL will be removed when Google removes them.

[ghen2]

It's only for the –most likely very short– transition period from kyber hybrids to mlkem hybrids. (I don't think anyone will still support x25519_kyber768 in 2025?)
But if it implies code complexity to support both, it's indeed better to just drop support for the deprecated drafts, and focus solely on the standard variants.

[baentsch]

if it implies code complexity to support both, it's indeed better to just drop support for the deprecated drafts, and focus solely on the standard variants.

fwiw, that's indeed my preference.

[baentsch]

Reopening as we only updated some code points in #511 but not the x-hybrid ones (let alone implement it).

[baentsch]

@bhess what's your time availability to close this out for good? I personally think we cannot do a new oqsprovider release following the liboqs release without including this: I'd think it'd confuse people significantly: If the final MLKEM is supported why does one corresponding (x25519-)hybrid fail to interoperate? Other opinions (or helping hands) welcome!

[bhess]

I started working on it and plan to do a PR this week.

[baentsch]

Again incorrectly closed.

[baentsch]

Reminder to re-activate interop testing with CF as part of PR as per https://github.com/open-quantum-safe/oqs-provider/blob/main/scripts%2Foqsprovider-externalinterop.sh#L31-L32