TLS 1.3 client and server both performing crypto_kem_keypair()

[rubiogarcia465179]

Hey everyone,

I've been working with the latest OQS library, specifically with OpenSSL (3.2 -dev) + liboqs (0.8.1-dev) + oqs-provider (0.5.1-dev). For my current testing scenario, I am implementing a non-hybrid PQ-based scenario (Dilithium3 + Kyber768). I expected the behavior for PQ TLS 1.3 to be something like the following (simplified) in terms of generating a shared secret (ss):

TLS Client: Generate keypair (pk, sk) -> Send pk to server
TLS Server: Encapsulate (ct, ss, pk) -> Generate ss and send corresponding ct to client
TLS Client: Decapsulate (ss, ct, sk) -> Use ct and pk to generate ss.

In this way, both client and server ** can achieve the same shared secret (ss)**.

However, I noticed an additional keypair generation call done by the TLS Server in the logs. This happens on the server side sometime after the Client Hello is processed and before sending back the Server Hello. For testing purposes, I modified the Kyber768 crypto_kem_keypair() function and added some debug logs (Function attached below).

Is this an intended behavior? Why might the server generate another keypair and what would that keypair be used for? Can anyone point me to documentation or discussions that detail the flow of a standard PQ TLS session, especially with configurations like Dilithium3 + Kyber768?

Thanks for the insights!!

Find below the modified crypto_kem_keypair:
int crypto_kem_keypair(uint8_t *pk,
uint8_t *sk)
{

indcpa_keypair(pk, sk);
printf("\nEntering the crypto kem keypair function within pqcrystals-kyber_kyber768_avx2\n");
//print_stack_trace();
memcpy(sk+KYBER_INDCPA_SECRETKEYBYTES, pk, KYBER_INDCPA_PUBLICKEYBYTES);
hash_h(sk+KYBER_SECRETKEYBYTES-2KYBER_SYMBYTES, pk, KYBER_PUBLICKEYBYTES);
/ Value z for pseudo-random output on reject */
randombytes(sk+KYBER_SECRETKEYBYTES-KYBER_SYMBYTES, KYBER_SYMBYTES);
return 0;
}

Short_logs_PQ_TLS13_client.txt
Short_logs_PQ_TLS13_server.txt

[dstebila]

That is weird, I agree that it shouldn't be necessary.

We'll have to ask @baentsch who wrote the oqs-provider code. Michael, I wonder if it has something to do with https://github.com/open-quantum-safe/oqs-provider/blob/main/oqsprov/oqs_kem.c#L193 which appears to me to be doing a keygen inside the encaps?

[baentsch]

I wonder if it has something to do with https://github.com/open-quantum-safe/oqs-provider/blob/main/oqsprov/oqs_kem.c#L193 which appears to me to be doing a keygen inside the encaps?

That indeed seems "surprising". Two thoughts, though: a) This code is only run when doing hybrid KEMs; b) @bhess added this code and may explain the rationale of doing a keygen so late in the game. I personally think this has nothing to do with the observation:

Why might the server generate another keypair and what would that keypair be used for?

I am aware of OpenSSL creating copies of data structures and as part of this a "surprising" keygen op may be performed (and/or oqsprovider has an implementation error when called in consequence of this).

@rubiogarcia465179 You may want to build oqsprovider as Debug release and activate full API call logging, most notably by setting the OQSKM, OQSKEY and OQSKEM environment variables (to "1"): This will create traces showing all calls from OpenSSL into oqsprovider (incl. keygens) and thus allow you to determine the root cause for your observation (bug in openssl, oqsprovider or unintended interaction between the two).

[rubiogarcia465179]

Hi @dstebila and @baentsch! Thank for very much for your comments. Following @baentsch's advice, I activated the full API logs and I managed to find out the issue within the code. Sometime after the client hello is received on the server's side, and before encapsulating, the server generates another keypair that (I believe) is not used (Please find attached the workflow that is happening on client and server side's regarding key generation).

I suspect (not certain) this might be happening because, although I am implementing a non hybrid PQ handshake based on a KEM mechanism (Kyber768), the current OQS provider seems to be imitating the behavior of ECDH (Generating a keypair in both client and server) as it happens in KEX mechanisms. Could that be the "issue"?

In my personal scenario, the solution was to add an environmental variable (e.g., OQSCLIENT) and a conditional statement in which the OQSProvider can differentiate between client and server operations, and avoid the keypair generation in the server's side.

However, this is not a very scalable/adequate solution. For that, I would like to ask: Are you aware if there is any logic currently implemented into the OQSProvider (or default OpenSSL provider) so that the provider can differentiate among client and server operations? I searched for such feature but I could not find nothing :(

Once again, thank you very much for your time!

[bhess]

I wonder if it has something to do with https://github.com/open-quantum-safe/oqs-provider/blob/main/oqsprov/oqs_kem.c#L193 which appears to me to be doing a keygen inside the encaps?

That indeed seems "surprising". Two thoughts, though: a) This code is only run when doing hybrid KEMs; b) @bhess added this code and may explain the rationale of doing a keygen so late in the game. I personally think this has nothing to do with the observation:

Right, this code only runs when doing a hybrid KEM (actually an ECDH+QS-KEM as specified in draft-ietf-tls-hybrid-design). In this case, the hybrid "encaps" returns the ephemeral key share of ECDH (i.e. ECDH does a keygen), concatenated with the ciphertext of the QS-KEM. See also 3.2 in https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/06/.

For the server's share, the key_exchange value contains
concatenation of the ct outputs of the corresponding KEMs' Encaps
algorithms, if that algorithm corresponds to a KEM; or the (EC)DH
ephemeral key share, if that algorithm corresponds to an (EC)DH
group.`

I agree there should not be an additional keygen on the server side in a non-hybrid case.

[baentsch]

Are you aware if there is any logic currently implemented into the OQSProvider (or default OpenSSL provider) so that the provider can differentiate among client and server operations?

No. But I find it incorrect by the (openssl) server (code) to initiate the keygen in the first place. This should be completely OQS-independent, right? So can you reproduce this behaviour with a classic KEM? If so, what about opening a ticket with this in openssl?

[bhess]

I don't think we can do keygen in a single place in the hybrid case @baentsch (is this what you suggest?). Overall it looks something like this:

The (classic EC)DH case works differently than the KEM case. In DH, both parties generate their key-share (i.e. do a keygen), while in the KEM only the initiator generates the key-pair.
We still need to use the KEM API, where the responder should not need to explicitly generate a key-pair (which might mistakenly happen for some reason, as pointed to in this discussion). The "encaps" then seems to be the only place to fit the responder's DH-Keygen. Any opinion @dstebila?

I think we previously had SIDH in liboqs, which was the DH-style variant of SIKE fitted to the KEM API. There a SIDH-keygen was performed as well in "encaps".

More generally, I think that fitting everything to the KEM API isn't very nice. A dedicated "hybrid" API could be useful.

[baentsch]

we can do keygen in a single place in the hybrid case @baentsch (is this what you suggest?)

Yes: If oqsprovider gets a call to generate key material, I would have thought it logical to do that (at that moment) for PQ+classic components.

But then again, the flow diagram seems to indicate that no "plain" key-gen should have happened for the "KEM responder" in the first place (as it seems initiator data flows into the keygen). So back to the original question: Why is keygen requested in the first place?

There a SIDH-keygen was performed as well in "encaps".

Understood. But that API was pretty much different: OpenSSL111 didn't contain the clear create-gen-use pattern as is the case with provider-based keys now -- which may be the problem in this case....

A dedicated "hybrid" API could be useful.

This is a separate item to this, right? Could it be an item within #17 (if this is pursued)?

[dstebila]

Overall it looks something like this:

The diagram matches my understanding of how hybrid key exchange should work in TLS 1.3, with the TLS client being the initiator, the TLS server being the responder, the first message being transmitted in the ClientKeyShare extension of the ClientHello, and the second message being transmitted in the ServerKeyShare extension of the ServerHello.

Consequently, there should indeed not be a Kyber.KeyGen a.k.a. Kyber.crypto_kem_keypair done by the TLS server.

[baentsch]

Consequently, there should indeed not be a Kyber.KeyGen a.k.a. Kyber.crypto_kem_keypair done by the TLS server.

As that is initiated by OpenSSL core logic (via evp_keymgmt_gen_init), that then would really call for raising an issue in OpenSSL best with reproducer code (maybe with a classic KEM to avoid the OQS dependency): Would you be willing to take this on, @rubiogarcia465179 ?

[rubiogarcia465179]

I can take on that one @baentsch. It is taking a little bit longer than expected because TLS 1.3 does not offer support for any classical KEM (as far as I am aware) by default. Nevertheless, I did find some "deprecated" implementations of classical KEMs within the TLS 1.3 codebase, inside the default Openssl provider. I am currently trying to activate (Not sure yet if it will be possible) those and see if the same issue comes up.

For the sake of testing, I tried RSA KEM in TLS 1.2, and indeed it does not perform a key generation operation on the server side... (As I would expect). However, I believe TLS 1.2 implementation is very different to TLS 1.3, so not really "helpful" for the case that we want to test.

Either way, I will perform the tests, document everything and hopefully attach the reproducer code that indicates where the issue is. I will keep you posted!