A Generic Way to use KEX keys as KEMs

[reneme]

Introduction

Key Encapsulation Mechanisms are undoubtedly becoming more popular (esp. in PQC algorithms) and protocols started to model KEMs based on Diffie-Hellman style Key Exchange algorithms (HPKE, Hybrid Key Exchange in TLS 1.3). Therefore, KEMs seem to be the model of choice going forward and I believe we should think about how their mapping onto KEX algorithms could be supported conveniently in Botan.

Mapping KEM interface onto KEX mechanism

The mapping from the KEM interface to KEX interface looks roughly like this:

def KEM-KeyGen(rng) -> Tuple[Public_Value, Private_Key]:
  return KEX-KeyGen(rng) # `public_value_1` and associated private `kex_key_1`

def KEM-Encaps(rng, public_value_1 : Public_Value) -> Tuple[Public_Value, Shared_Secret]:
  kex_key_2 = KEX-KeyGen(rng)
  return kex_key_2.public_value(), kex_key_2.exchange(public_value_1)

def KEM-Decaps(public_value_2 : Public_Value) -> Shared_Secret
  return kex_key_1.exchange(public_value_2)

Implementation Strategy in Botan

Botan provides PK_KEM_Encryptor and PK_KEM_Decryptor to model the KEM functions "Encaps" and "Decaps". Internally they use the keys' create_kem_encryption_op() and create_kem_decryption_op() to implement the KEM functionality in a general way. However, those work solely with asymmetric keys that support KEM operations (e.g. "Kyber" or "RSA").

I could imagine several implementation strategies to conveniently allow KEX keys to be used as a KEM:

1. Provide KEX_KEM_Adapter_PublicKey and KEX_KEM_Adapter_PrivateKey wrapper classes

   Those could take hold of any KEX key and mimick KEM behavior by implementing create_kem_encryption_op() and create_kem_decryption_op() as described above. The generic mapping implementation would live inside their private PK_Ops::KEM_Encryption, PK_Ops::KEM_Decryption.

2. Allow PK_KEM_Encryptor and PK_KEM_Decryptor to consume KEX keys

   ... and implement the KEM-KEX translation there. That's likely much less boilerplate, as we could use the new Asymmetric_Key::supports_operation() to switch modes between verbatim KEM and translated KEX

3. All (or some) KEX keys provide create_kem_encryption_op() and create_kem_decryption_op()

   This would probably provide the best implementation flexibility but might force us to re-implement the KEM-KEX mapping over and over again for each key type.

Off the top of my hat, I'm in favor of option (2), although it might be a bit surprising for the general reader that the KEM_Encryptor can consume KEX keys. Being a full-scale wrapper, option (1) comes with some boiler plate but might be more "explicit" and avoid inadvertent applications of KEM.

Required Additional Machinery

The Asymmetric_Key class hierarchy provides most building blocks to implement the generic approaches (1) and (2). Except, we would need a generic way to generate another key pair from a given Public_Key to implement "KEM-Encaps". The generic Public_Key interface currently does not provide enough information to bootstrap another key pair generically without clumsy down casts onto concrete Public_Key implementations and probably some more getters everywhere.

I'm envisioning a simple Public_Key::generate_another_keypair() method that is implemented for all (or for at least all KEX) public keys. Let me try to sketch my idea in code (assuming implementation strategy (2)):

std::unique_ptr<ECDH_PublicKey> pubkey = received_from_peer();
PK_KEM_Encryptor kem(*pubkey, rng, ...);
auto [ciphertxt, sharedkey] = kem.encrypt_using_kex();

where encrypt_using_kex() would look (roughly) like this:

class PK_KEM_Encryptor {
private:
    const Public_Key& m_pubkey;

public:
    std::tuple<std::vector<uint8_t>, secure_vector<uint8_t>>
    PK_KEM_Encryptor::encrypt_using_kex(RNG& rng) {
        const auto privkey = pubkey.generate_another_keypair(rng);
        PK_Key_Agreement agree(*privkey, rng, "Raw");
        auto sharedkey = agree.derive_key(m_pubkey.public_key_bits());
        return {privkey->public_key_bits(), sharedkey};
    }
};

First of all: Thanks for reading this far! Before heading out and building all this machinery, I'd like to get your opinion on the design space. The first use case will be the continued development of #2983 that has been dormant for a year now.

[randombit]

My concern with approaches (1) and (2) is that while they are generic - they are generic.

To be concrete, at the moment we have 3 key exchange algorithms available, all based around Diffie-Hellman key exchange - FFDHE, ECDH, and X25519.

It is not at all clear that

• a) KEM based exchanges will be standardized for all three algorithm types - FFDHE in particular is somewhat out of fashion these days.
• b) If KEM oriented operations are standardized, that they will be very similar for all three types, such that a generic adaptor works easily without a lot of policy configuration. Especially if they end up being standardized by different IETF working groups (or even different national standards bodies!) we might easily end up in a situation where FFDHE uses SHA-512 and ECDH uses SHAKE and the formatting is different and .... [DLIES/ECIES is a great example of what kind a mess this can become]

Given that any KEM<->KEX layer has to support at most 3 algorithms - and it's hard to imagine what additional KEX schemes we might ever implement, considering the very pronounced move to KEM in new designs - I would instead advocate for your approach (3) for these reasons

1. We can choose not to implement the mapping for specific key types (FFDHE in particular comes to mind here)
2. The exact mechanisms/formatting used can be made specific to the algorithm

Now backing out yet further from here, you link to the HPKE spec. HPKE has many more features than just a plain KEM, including PSK modes, authenticated encryption with a variety of ciphers, associated data, and so on. But HPKE is also notably non-generic itself, in that for generic EC curves it only supports P-256, P-384, and P-521. Also the KEM output is hashed using a specific HKDF, using HPKE specific labels. This would box us in, with regards to supporting any other KEM format in the future.

TBH if the goal is specifically to support HPKE, it would be better to skip the mapping entirely because for HPKE we can't handle anything generically anyway - we'll have to detect exactly which curve the input key is on and choose a ciphersuite on that basis. And we'll need new dedicated APIs, since the KEM interface doesn't expose what HPKE offers. At that point we might as well implement HPKE directly in terms of the KEX API.

[reneme]

TBH if the goal is specifically to support HPKE, it would be better to skip the mapping entirely because for HPKE we can't handle anything generically anyway - we'll have to detect exactly which curve the input key is on and choose a ciphersuite on that basis.

Frankly, I didn't look into HPKE that deeply so far. My short-term objective is to move the hybrid Key Exchange for TLS 1.3 forward. On a high level this has the similar requirement to combine KEMs and KEXes into a common exchange. In the hope to make this reusable, I started fiddling with the idea outlined above.

Given that any KEM<->KEX layer has to support at most 3 algorithms - and it's hard to imagine what additional KEX schemes we might ever implement, considering the very pronounced move to KEM in new designs - I would instead advocate for your approach (3)

Given your points, I believe, even that might be too generic to be useful across protocols.

At that point we might as well implement HPKE directly in terms of the KEX API.

It's a mess, but it seems its just best to implement the hybrid TLS 1.3 combiner based on the KEX API as well. That keeps maximum flexibility in each protocol that might need something like this.

[reneme]

Short answer: The proposed generic approach clashes with reality. For the time being: Let's instead integrate KEX-KEM mappings in the individual protocol implementations that require it. The subtle (and not so subtle) differences in these mappings will stand in the way of a generic approach.

See #3581 (comment) for a detailed discussion.