Broken implementation of kyber512, kyber768 and kyber1024 as KEX.

[ReverseControl]

I tested kyber512, kyber768 and kyber1024. The test is simple:

1. Establish a VPN using each of those algorithms as KEX.
2. Observe the raw network traffic.
3. Confirm both parties exchange the keys.
4. Confirm the number of bytes for said keys are correct.

Kyber512 ( click to see the Kyber NIST submission paper for round 2 with the Kyber specs):

1. Here is what happens with openssl s_server/s_client testing.

• Private kyber512 Key: 768 bytes
• Public kyber512 Key: 800 bytes -Kyber is designed for KEM, although it is being used as a KEX. I haven't looked at the KEX mechanism for it, but the private key being sent in the clear probably makes sense in this use case.
• Everything checks out.

2. Here is what happens with openvpn --config server/client(.ovpn):

• client.ovpn has ecdh-curve kyber512
• server.ovpn has ecdh-curve kyber512 and tls-version-min 1.3 :
• Observation 1: Keys exchanged are from a different "ec-groups'; mismatch.
• Observation 2: Client does not choose kyber512 "ec-curve", but instead ec-curve x25519.
• Observation 3: Client does not send its key kyber512 key, but instead the x25519 key.
• Observation 4: server chooses kyber512 and returns its kyber512 key.
• Observation 5: This establishes a valid connection, but the crypto is utterly incorrect/broken just from glancing at the observations above.
• Observation 2 means the client is never setting the ecdh-curve parameter found in the configuration file, but it seems the server does set it.

Kyber768:

• Same configuration as above except ecdh-curve kyber768.
• Observation 1: Observation 1, 2 and 3 in kyber512 hold true here as well.
• Observation 2: The server responds with Change Cipher Spec and specifies the kyber768 group, but does not send its key.

kyber1024:

• Observations are the same as kyber768.

[kevinmkane]

I'm seeing what you're seeing in my repro. We'll investigate. Thanks for the report.

[kevinmkane]

I think I see what's going on here. There are two issues:

1. It turns out the ecdh-curve configuration directive in OpenVPN is only respected server-side. It's ignored on the client. In the normal case this makes sense: the client offers up all the groups it supports and the server picks (based on the ecdh-curve directive if provided, or its own default list if not). So the client has x25519 at the top of its list, and starts offering that. In our case, it might make sense to have the client also process the directive, so it sends a supported group list of exactly one element. OpenVPN's options interface doesn't currently support providing more than one curve; we could extend this to allow the client to set a list of supported groups, much as we allowed for a list of supported TLS 1.2 ciphersuites in the previous version.

2. Wireshark is leading us astray by not actually parsing everything correctly. There's a Change Cipher Spec, and then there's Continuation Data. The data being split up like this is confusing Wireshark. In my trace, the Change Cipher Spec's size shows as 1242 bytes, which is absurdly oversized for that type. That type is 6 bytes. What follows in that packet and the Continuation Data is another Client Hello, and this time its Key Share extension has the correct group and key exchange data. Wireshark just isn't picking this apart, probably because the Kyber keys are bigger than sikep434. The key exchange data for sikep434 in my trace is 330 bytes, whereas kyber768 is 1008 bytes. Between this and OpenVPN's protocol I think Wireshark is losing track. But, going through the bytes by hand I can pick out the second ClientHello. The rest of my trace is showing as more Continuation Data, but I expect if I pick it apart I'll find another Server Hello to complete the negotiation.

So what's actually happening is:

• Client sends ClientHello with all of its supported groups, but optimistically offers a x25519 key share (because OpenVPN ignores the ecdh-curve on the client).
• Server replies back with a HelloRetryRequest and says, "No, sikep434 (or kyber768) please" with a key share extension that only states the group. The key exchange data vector can be empty when this extension is used in a HelloRetryRequest. (See 4.2.8 in RFC 8446). Server also sends a ChangeCipherSpec.
• Client sends a ChangeCipherSpec and another ClientHello, in which it offers sikep434 (or kyber768) with new key share.
• Server replies with a ServerHello with its key share.
• And now application data can pass.

If I look at a trace where sikep434 is selected, the same thing is happening: the client first offers an x25519 key share, and the server comes back with a Hello Retry Request with another key share extension that only has the group it wants. In this case, Wireshark manages to see and parse the second Client Hello that comes back with sikep434 group and key exchange data. It's just not seeing it in the Kyber case.

So in summary: Everything looks like it's working as it should, and we are getting a key negotiated with the desired algorithm. Wireshark just seems to be getting confused and isn't parsing all the pieces of the TLS 1.3 negotiation, possibly as a consequence of them being fragmented and/or encapsulated in OpenVPN's protocol.

[ReverseControl]

I think allowing the client to set group for KEX from the ecdh-curve directive would be helpful; even one choice is fine with the goal of extending it to more than one.

Is there any way you could write a plugin, or modify the wireshark TLS decoder, to handle this? :D

[kevinmkane]

It looks like making the client respect the ecdh-curve directive is pretty straightforward, so I'll look into doing that.

I don't think I'm up for trying to fix Wireshark's bugs, though. :) Have you considered opening a bug in their bug tracker, and supplying one of these captures to show what's going on? They'd be much better equipped to fix the parsing than me.

[ReverseControl]

I tested ecdh-curve on the client side and it works; kyber512 shows up as expected from looking at the s_client/s_server. However, for kyber768 wireshark cannot parse it at all. Could you please confirm that for kyber768 the keys are exchanged and that they are of the right size?

[kevinmkane]

That was what I tracked down before the analysis I posted yesterday, with Wireshark missing the second ClientHello. The key share extension in there had the kyber768 group number and a key share of the right size.