Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs)

1.1. Key Encapsulation Mechanisms

For the purposes of this document, we consider a Key Encapsulation Mechanism (KEM) to be any asymmetric cryptographic scheme comprised of algorithms satisfying the following interfaces [PQCAPI].¶

def kemKeyGen() -> (pk, sk)
def kemEncaps(pk) -> (ct, ss)
def kemDecaps(ct, sk) -> ss

where pk is public key, sk is secret key, ct is ciphertext, and ss is shared secret.¶

KEMs are typically used in cases where two parties, hereby refereed to as the "encapsulater" and the "decapsulater", wish to establish a shared secret via public key cryptography, where the decapsulater has an asymmetric key pair and has previously shared the public key with the encapsulater.¶

2.1. KEM/PSK hybrids

As a post-quantum stop-gap, several IETF protocols have added extensions to allow for mixing a pre-shared key (PSK) into an (EC)DH based key exchange. Examples include CMS [RFC8696] and IKEv2 [RFC8784].¶

2.2. PQ/Traditional hybrid KEMs

A post-quantum / traditional hybrid key encapsulation mechanism (hybrid KEM) as defined in [I-D.driscoll-pqt-hybrid-terminology] as¶

PQ/T Hybrid Key Encapsulation Mechanism:

A Key Encapsulation Mechanism (KEM) made up of two or more component KEM algorithms where at least one is a post-quantum algorithm and at least one is a traditional algorithm.¶

Building a PQ/T hybrid KEM requires a secure function which combines the output of both component KEMs to form a single output. Several IETF protocols are adding PQ/T hybrid KEM mechanisms as part of their overall post-quantum migration strategies, examples include TLS 1.3 [I-D.ietf-tls-hybrid-design], IKEv2 [I-D.ietf-ipsecme-ikev2-multiple-ke], X.509; PKIX; CMS [I-D.ounsworth-pq-composite-kem], OpenPGP (CITE once Aron's draft is up), JOSE / COSE (CITE once Orie's drafts are up).¶

2.3. KEM-based AKE

The need for a KEM-based authenticated key establishment arises, for example, when two communicating parties each have long-term KEM keys (for example in X.509 certificates), and wish to involve both KEM keys in deriving a mutually-authenticated shared secret. In particular this will arise for any protocol that needs to provide post-quantum replacements for static-static (elliptic curve) Diffie-Hellman mechanisms. Examples include a KEM replacement for CMP's DHBasedMac [I-D.ietf-lamps-cmp-updates], .. TODO: cite others.¶

A.1. Dual PRF

Dual PRFs are a active area of research. A dual PRF is a function which is a PRF when keyed by either of its two inputs - guaranteeing pseudo-randomness if one of the keys is compromised or even maliciously chosen by an adversary [Aviram2022]. As of publication of this document, no dual PRFs have been standardized for use. In practice we often use HMACs or HKDFs to serve the role of a dual PRF even though they have never been proved to be dual PRFs [Bellare2015], [Aviram2022].¶

In essence, this document assumes that KDF( H(input1) || H(input2)) is a dual PRF in practice, for suitable choices of key derivation function KDF and hash function H, despite not having formal security proofs. It has been proposed as a KEM combiner, for example in [I-D.ietf-tls-hybrid-design]. As the academic literature evolves, it may become appropriate to obsolete this document with a KEM combiner based on a provably secure dual PRF.¶

A.2. KEM primitives

In modern cryptographic design, KEM algorithms seek to have indistinguishability under adaptive chosen ciphertext attack (IND-CCA2). FFor hybrid KEMs we desire the additional property that even if one input is controlled by an attacker, then combiner leaks no information about the other input.¶

There are two ways to achieve such a hybrid KEM combiner; either by designing a combiner that is robust to one of the inputs being maliciously-chosen, called a dual PRF. See Appendix A.1 for a discussion about the current state of dual PRF research. Or alternatively by only allowing the hybridization of KEMs where a malicious kemEncaps() algorithm cannot control the shared secret derived by the victim's kemDecaps() algorithm and then combining the shared secrets in a trivial way.¶

The following sections analyze commonly-used KEM algorithms to show that they have the following two properties, and are therefore suitable for use with the simplified KEM combiner presented in Section 3, Figure 2.¶

1. A malicious encapsulater cannot control the length of the KEM output (shared secret) that will be derived by the decapsulater.¶
2. A malicious encapsulater cannot control the value of the KEM output (shared secret) that will be derived by the decapsulater. We define a KEM output to be "controlled by an attacker" if a maliciously-written kemEncaps() function can cause the victim's kemDecaps() algorithm to produce a shared secret either of a length chosen by the attacker, or to take on a given value with higher probability than can be obtained via rejection sampling on the shared secret output of kemEncaps().¶

A.3. RSA-KEM

RSA encryption [RFC3447] can be promoted into a KEM as per [RFC5990] which defines a key transport based on RSA-KEM.¶

1. Generate a random integer z between 0 and n-1 (see note), and
  convert z to a byte string Z of length nLen, most significant byte
  first:

      z = RandomInteger (0, n-1)

      Z = IntegerToString (z, nLen)

2. Encrypt the random integer z using the recipient's public key
  (n,e), and convert the resulting integer c to a ciphertext C, a
  byte string of length nLen:

      c = z^e mod n

      C = IntegerToString (c, nLen)

3. Derive a key-encrypting key KEK of length kekLen bytes from the
  byte string Z using the underlying key derivation function:

      KEK = KDF (Z, kekLen)

4. Wrap the keying data K with the key-encrypting key KEK using the
  underlying key-wrapping scheme to obtain wrapped keying data WK:

      WK = Wrap (KEK, K)

5. Concatenate the ciphertext C and the wrapped keying data WK to
  obtain the encrypted keying data EK:

      EK = C || WK

6. Output the encrypted keying data EK.

where Steps 1 - 3 define "RSA-KEM", which is considered here. Steps 4 - 6 define "Key Transport based on RSA-KEM" and is out of scope for this analysis as we assume that any RSA-KEM construction intended for use in a hybrid KEM would use the KEK output from Step 3 as the final shared secret.¶

Here the transported symmetric key, KEK, is the KEM output (shared secret) ss as defined in Section 1.1. The encapsulater must choose a key derivation function KDF and declare it in the RSA-KEM parameters. The decapsulater may refuse to perform the the decapsulation if it does not like the encapsulater's choice of KDF, therefore it can be modeled as a random oracle producing an output of fixed length. The attacker is free to choose z, but assuming a strong choice of KDF, they cannot control either the length or the value KEK beyond what can be obtained by rejection sampling, thus satisfying properties 1 and 2 and defined in {.sec-kemprimitives}}.¶

Therefore RSA-KEM is considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶

Security note: This analysis applies to the specific RSA-KEM construction defined above. This result is not intended to generalize to all RSA-based key transport mechanisms, as they may not have the same cryptographic properties.¶

A.4. Elliptic Curve Diffie-Hellman (ECDH)

The elliptic curve Diffie-Hellman key exchange [SEC1] can be promoted into a KEM in a straightforward way by assuming an ephemeral-static (ES) mode where def kemEncaps(pk) -> (ct, ss) includes generation of an ephemeral key pair, the public key being included as part of the ciphertext ct and the private key being discarded upon completion of the encapsulation.¶

According to [SEC1] section 6.1.3:¶

1. Use one of the Diffie-Hellman primitives specified in Section 3.3 to
   derive a shared secret field element z ∈ Fq from U's secret key d_U
   established during the key deployment procedure and V's public key
   Q_V obtained during the key deployment procedure. If the Diffie-
   Hellman primitive outputs “invalid”, output “invalid” and stop.
   Decide whether to use the “standard” elliptic curve Diffie-Hellman
   primitive or the elliptic curve cofactor Diffie-Hellman primitive
   according to the convention established during the setup procedure.

2. Convert z ∈ Fq to an octet string Z using the conversion routine
   specified in Section 2.3.5.

3. Use the key derivation function KDF established during the setup
   procedure to generate keying data K of length keydatalen octets
   from Z and [SharedInfo]. If the key derivation function outputs
   “invalid”, output “invalid” and stop.

4. Output K.

Other key exchange methods defined in [SEC1] follow a similar construction.¶

The attacker is free to choose a private key d_U which yields a shared secret Z, but cannot force Z to take on a chosen value without solving the elliptic curve discrete logarithm problem or performing rejection sampling. Assuming a strong choice of KDF, the attacker cannot control either the length or the value of KEK beyond what can be obtained by rejection sampling, thus satisfying properties 1 and 2 and defined in Appendix A.2.¶

Therefore elliptic curve Diffie-Hellman is considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶

A.5. Edwards Curve Diffie-Hellman (X25519 / X448)

The elliptic curve Diffie-Hellman key exchange [SEC1] can be promoted into a KEM in a straightforward way by assuming an ephemeral-static (ES) mode where def kemEncaps(pk) -> (ct, ss) includes generation of an ephemeral key pair, the public key being included as part of the ciphertext ct and the private key being discarded upon completion of the encapsulation.¶

According to [RFC7748] section 6.1, the X25519 key exchange is defined as:¶

Alice generates 32 random bytes in a[0] to a[31] and transmits K_A =
X25519(a, 9) to Bob, where 9 is the u-coordinate of the base point
and is encoded as a byte with value 9, followed by 31 zero bytes.

Bob similarly generates 32 random bytes in b[0] to b[31], computes
K_B = X25519(b, 9), and transmits it to Alice.

Using their generated values and the received input, Alice computes
X25519(a, K_B) and Bob computes X25519(b, K_A).

Both now share K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9))
as a shared secret.  Both MAY check, without leaking extra
information about the value of K, whether K is the all-zero value and
abort if so (see below).  Alice and Bob can then use a key-derivation
function that includes K, K_A, and K_B to derive a symmetric key.

The X448 key exchange follows a similar construction.¶

The attacker is free to choose a private key b which yields a shared secret K, but cannot force K to take on a chosen value without solving the elliptic curve discrete logarithm problem or performing rejection sampling. Assuming a strong choice of KDF, the attacker cannot control either the length or the value of the derived symmetric key beyond what can be obtained by rejection sampling, thus satisfying properties 1 and 2 and defined in Appendix A.2.¶

Therefore Edwards curve Diffie-Hellman, X25519 and X448, are considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶

A.6. CRYSTALS-Kyber

The CRYSTALS-Kyber kemEncaps() is defined as follows [I-D.cfrg-schwabe-kyber]:¶

1.Compute
  1. m = H(seed)
  2. (Kbar, cpaSeed) = G(m || H(pk))
  3. cpaCipherText = InnerEnc(m, publicKey, cpaSeed)
2.Return
  1. cipherText = cpaCipherText
  2. sharedSecret = KDF(KBar || H(cpaCipherText))

with definitions as per [I-D.cfrg-schwabe-kyber].¶

Here the hash functions G, H and the key derivation function KDF are in theory chosen by the encapsulater, but in practice are fixed by the Kyber specification to be H: SHA3-256, G: SHA3-512, and KDF: SHAKE-256, which can be modeled as random oracles. The attacker is free to choose m, but not the decapsulater's public key pk, nor do they have control of cpaCipherText so long as InnerEnc remains IND-CPA secure. Therefore the attacker cannot control the value or length of K beyond what can be obtained by rejection sampling.¶

Therefore CRYSTALS-Kyber is considered to be suitable for use with the simplified KEM combiner defined in Section 3, Figure 2.¶

C.1. Making contributions

To be removed before publication.¶

Additional contributions to this draft are welcome. Please see the working copy of this draft at, as well as open issues at:¶

https://github.com/EntrustCorporation/draft-ounsworth-cfrg-kem-combiners¶