Figure out how to integrate KEMs into EVP layer

[thomwiggers]

For much easier use, KEMs should probably be integrated in the EVP framework. I did some experiments, and I now do have a certified Kyber 512 public key.

This should then be useful to consider OPTLS-like setups.

The challenge of course is EVP_PKEY_derive being almost but not quite suitable for this task. I have not tackled this problem yet, but it may be possible to slightly extend the API to obtain a ciphertext instead of the public key. That seems the main challenge, I think it should be possible to override the derive function such that it conditionally encapsulates or decapsulates:

static int pkey_oqs_derive(EVP_PKEY_CTX *ctx, unsigned char *key, size_t *keylen) {
    OQS_KEY *oqs_key = (OQS_KEY*) ctx->pkey->pkey.ptr;
    OQS_KEY *oqs_peer = (OQS_KEY*) ctx->peerkey->pkey.ptr;

    *keylen = oqs_size(ctx->pkey);
    if (key == NULL) {
        return 1;
    }
    if (oqs_peer->ciphertext) {
        if (OQS_KEM_decaps(oqs_key->k, key, oqs_peer->ciphertext, oqs_key->privkey) == OQS_SUCCESS) {
            return 1;
        }
    } else {
        oqs_peer->ciphertext = OPENSSL_malloc(*keylen);
        if (OQS_KEM_encaps(oqs_key->k, key, oqs_peer->ciphertext, oqs_peer->pubkey) == OQS_SUCCESS) {
            return 1;
        }
    }

    return 0;
}

Obviously, that does mean that the users of the EVP API need to do some detection "is this method a KEM" and obtain and/or set the ciphertext if needed.

[thomwiggers]

See https://github.com/thomwiggers/openssl/tree/KEM-cert by the way.

[dstebila]

Hi Thom,

Very interesting approach. Indeed having KEMs in EVP would make it easier for OPTLS and static DH like approaches. But TLS 1.3 dropped both of those in favour of signatures+ephemeral-DH, so would you then want to add that back in to TLS 1.3?

[thomwiggers]

Well, it should be possible to use KEMs with HelloRetryRequest and the OPTLS extension internet draft. I'd also like to look into what a TLS 1.2-like 1.5-RTT OPTLS protocol with pq KEMs would behave like.

[thomwiggers]

On the OpenSSL side I opened an issue (https://github.com/openssl/openssl/issues/7616) to discuss if they are interested in specifying a proper EVP API which would allow OQS to implement KEMs without too many hacks.

[thomwiggers]

FYI: In my branch I've since added EVP_PKEY_encapsulate and EVP_PKEY_decapsulate.

[dstebila]

I looked at your last few commits and see that you've added the EVP_PKEY_encapsulate and EVP_PKEY_decapsulate methods, and that you've started to put them into the ClientKeyExchange messages. How's that going? Have you successfully done a key exchange with that yet?

In the long term, will those be raw KEM public keys, or will they be certified? If so I guess we'd need a mechanism to generate X.509 certs with KEM public keys in them.

[thomwiggers]

I've not yet had time to check how and to what extent things will burst into flames when I first run it, but that is one of the things that I was hoping to pick up today. The plan is to have the client encapsulate to the public key that's in the certificate, and then do HMAC instead of a signature (like OPTLS).

"A mechanism to generate X.509 keys" turned out to be easier than I'd first thought: I basically implemented the same API that DH supports (crypto/dh/ameth.c) for KEMs and then I could create a certificate request in much the same way you'd do that for DH parameters.

The certificate I linked in the first post in this issue has an RSA signature, which is of course silly in a post-quantum setting, but it illustrates that it is possible. The idea we had was that if anyone were to be somewhat trustworthy in keeping state, it would be CAs with HSMs, so we could for example have them issue e.g. XMSS-signed certificates to keep the signature size small. Anyone deploying these certificates should be doing authentication with symmetric primitives.¹

¹) OpenSSH has experimental XMSS support, and I should write down my rant some time why that is a bad idea: for one, we just spent decades of teaching people to back up keys – so they'll back up it including the statefile and then end up reusing states....

[romen]

https://github.com/openssl/openssl/pull/13018 is extending the work done in changes recently merged for OpenSSL 3.0:

• https://github.com/openssl/openssl/pull/12750 added support for KEM at the EVP layer, backed by implementations provided by internal or external OpenSSL Providers
• https://github.com/openssl/openssl/pull/11914 allowed OpenSSL Providers to "plug in" groups (even custom ones) to be used by libssl for key exchange in TLSv1.3

https://github.com/openssl/openssl/pull/13018 would extend https://github.com/openssl/openssl/pull/11914 to:

• add an extra capability to allow providers to optionally signal that a "plugged-in" group behaves as a KEM (key encapsulation method),
• include minimal changes in libssl to act on this optional capability:
  • handling of the Key Share extension on the client and the server checks the new capability so that, if set to true, the API introduced in https://github.com/openssl/openssl/pull/12750 is called, as an alternative to the traditional "DH-like scheme", that remains unchanged.

The combination of these 2 items would allow OpenSSL Providers to model the "plugged-in" groups either under the key exchange scheme (both sides do a Diffie-Hellman-like exchange) or the key encapsulation method scheme (client sends KEM pubkey in Key Share, server encapsulates under given pubkey and send back the ciphertext as its Key Share, client decapsulates the received ciphertext using the paired privkey). Given that a key exchange scheme can trivially be described as a KEM scheme, this also allows the authors of OpenSSL Providers to optionally describe DH-like primitives in terms of KEM, which also simplifies the design and deployment of hybrid schemes composing traditional-computing-resistant and quantum-computing-resistant primitives.

https://github.com/openssl/openssl/pull/13018 is currently held back, because it is coming quite late in the development cycle of the OpenSSL 3.0 release and because we all want to avoid "feature creep".

I presented my argument for inclusion nonetheless and I am looking for endorsement by members of the community to build support for it: please consider participating in the https://github.com/openssl/openssl/pull/13018 discussion if you want to show your support on the matter, caution against inclusion, or share any relevant feedback.

[dstebila]

Closing this in OQS-OpenSSL since it looks like this will be available to us once we move to OpenSSL 3.0.