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 the ciphertext representing an encapsulated key, and ss is the shared secret.¶

KEMs are typically used in cases where two parties, hereby referred 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 [I-D.wussler-openpgp-pqc], JOSE / COSE (CITE once Orie's drafts are up).¶

The traditional algorithm may in fact be a key transport or key agreement scheme, but since simple transformations exist to turn both of those schemes into KEMs, this document assumes that all cryptograhpic algorithms satisfy the KEM interface described in Section 1.1.¶

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].¶

3.1. Length encoding

All variable length string inputs s MUST be suffixed with the length, right-encoded using the rlen function, having the following construction:¶

Validity Conditions: 0 <= len(s) < 2^{2040}
1. Let x = len(s)
1. Let n be the smallest positive integer for which 2^{8n} > x
2. Let x_1, x_2, ..., x_n be the base-256 encoding of x satisfying:
    x = sum 28(n-i)x i, for i = 1 to n
3. Let O_i = uint8(x_i), for i = 1 to n
4. Let O_{n+1} = uint8(n)
5. rlen(s) = O_1 || O_2 || ... || O_n || O_{n+1}

This is compatible with the right_encode construction presented in [SP800-185], and encodes the length of the string s as a byte string in a way that can be unambiguously parsed from the end.¶

Right encoding is preferred to left encoding, since it provides the same security guarantees but allows encoding ciphertext where length is a priori unknown.¶

3.2. k_i construction

Following the guidance of Giacon et al. [GHP18], we wish for a KEM combiner that is CCA-secure as long as at least one of the ingredient KEMs is. In order to protect against chosen ciphertext attacks, it is necessary to include both the shared secret ss_i and its corresponding ciphertext ct_i. If both the secret share ss_i and the ciphertext ct_i are constant length, then k_i MAY be constructed concatenating the two values:¶

k_i = ct_i || ss_i

If ss_i or ct_i are not guaranteed to have constant length, it is REQUIRED to append the rlen encoded length when concatenating, prior to inclusion in the overall construction described in Figure 1:¶

k_i = ct_i || rlen(ct_i) || ss_i || rlen(ss_i)

Any protocols making use of this construction MUST either right-encode the length of all inputs ss_i and ct_i, or justify that any inputs will always be fixed length. In the case of a PSK the associated ciphertext is the empty string.¶

Including the ciphertext guarantees that the combined kem is IND-CCA2 secure as long as one of the ingredient KEMs is, as stated by [GHP18].¶

The ciphertext precedes the secret share, as memory-constrained devices can write c_i into the hash state and no further caching is required when streaming.¶

3.3. Note on the order of parameters

For a two-KEM instantiation, the construction is¶

KDF(counter || ct_1 || rlen(ct_1) || ss_1 || rlen(ss_1) || ct_2 || rlen(ct_2) || ss_2 || rlen(ss_2) || fixedInfo, outputBits) ¶

The order of parameters is chosen intentionally to facilitate streaming implementations on devices that lack sufficient memory to hold the entirety of ct_1 or ct_2.¶

This construction aims to have two streaming-friendly properties. First, ct_i can be written to KDF's update interface as it is received and does not need to be stored, finally adding its corresponding ss_i once it is available. And second, the first KEM can be processed in its entirety and written to KDF's update interface before beginning to process the second KEM.¶

3.4. Protocol binding

The fixedInfo parameter is a fixed-format string containing some context-specific information. This serves to prevent cross-context attacks by making this key derivation unique to its protocol context.¶

The fixedInfo string MUST have a definite structure depending on the protocol where all parts strictly defined by the protocol specification.¶

fixedInfo = fixedInfo || s

Each fixed-length input string f MAY be directly used as input:¶

s = f ; f is guaranteed to have fixed length

Each variable-length input string v MUST be suffixed with a right-encoding of the length:¶

s = v || rlen(v) ; v may have variable length

fixedInfo MUST NOT include the shared secrets and ciphertexts, as they are already represented in the KDF input.¶

The parameter fixedInfo MAY contain any of the following information:¶

• Public information about the communication parties, such as their identifiers.¶
• The public keys or certificates contributed by each party to the key-agreement transaction.¶
• Other public information shared between communication parties before or during the transaction, such as nonces.¶
• An indication of the protocol or application employing the key-derivation method.¶
• Protocol-related information, such as a label or session identifier.¶
• An indication of the key-agreement scheme and/or key-derivation method used.¶
• An indication of the domain parameters associated with the asymmetric key pairs employed for key establishment.¶
• An indication of other parameter or primitive choices.¶
• An indication of how the derived keying material should be parsed, including an indication of which algorithm(s) will use the (parsed) keying material.¶

This is a non-comprehensive list, further information can be found in paragraph 5.8.2 of NIST SP800-56Ar3 [SP800-56A].¶

4.1. KMAC based construction

Options 1 and 2 are KMAC-based, as specified in NIST SP 800-185 [SP800-185]. To instantiate the function:¶

• The context S MUST be the utf-8 string "KDF".¶
• The key K MUST be a context-specific string of at least hashSize bits, and it MAY be used as an additional option to perform context separation, in scenarios where fixedInfo is not sufficient.¶
• The parameter counter MUST be the fixed value 0x00000001.¶

To derive a shared secret ss of desired length, KMAC is called a single time with the input string X defined in Section 3 and length L being outputBits. This is compatible with the one-step KDF definition given in NIST SP800-56Cr2 [SP800-56C], Section 4.¶

4.2. Hash-and-counter based construction

Options 3 and 4 instantiate the KDF using SHA3, specified in NIST FIPS 202 [FIPS202]. To generate an outputBits long secret share ss:¶

• the counter MUST be initialized with the value 0x00000001.¶
• The hash is performed over the string defined in Section 3, and repeated ceil(outputBits/hashSize) times. For each iteration the counter MUST be increased by 0x01.¶
• The strings are concatenated ordered by counter.¶
• The leftmost outputBits are returned as ss.¶

An implementation MUST NOT overflow and reuse the counter and an error MUST be returned when producing more than 2^32 consecutive hashes.¶