Skip to content

Latest commit

 

History

History
478 lines (369 loc) · 21.3 KB

draft-ounsworth-cfrg-kem-combiners.mkd

File metadata and controls

478 lines (369 loc) · 21.3 KB
Raw

title: Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs) abbrev: KEM Combiner docname: draft-ounsworth-cfrg-kem-combiners-05

ipr: trust200902 area: Security stream: IRTF wg: CFRG kw: Internet-Draft cat: info venue: group: "Crypto Forum Research Group (CFRG)" type: "Research Group" mail: "cfrg@ietf.org" arch: "https://mailarchive.ietf.org/arch/browse/cfrg/" repo: "https://github.com/EntrustCorporation/draft-ounsworth-cfrg-kem-combiners"

coding: utf-8 pi: # can use array (if all yes) or hash here toc: yes sortrefs: # defaults to yes symrefs: yes

author: - ins: M. Ounsworth name: Mike Ounsworth org: Entrust Limited abbrev: Entrust street: 2500 Solandt Road – Suite 100 city: Ottawa, Ontario country: Canada code: K2K 3G5 email: mike.ounsworth@entrust.com - ins: A. Wussler name: Aron Wussler org: Proton AG abbrev: Proton country: Switzerland email: aron@wussler.it - ins: S. Kousidis name: Stavros Kousidis org: BSI country: Germany email: kousidis.ietf@gmail.com

normative: RFC2119:

informative: RFC8174: RFC8411: RFC8784: RFC8696: RFC8784: I-D.ietf-lamps-cmp-updates: I-D.driscoll-pqt-hybrid-terminology: I-D.ietf-tls-hybrid-design: I-D.ietf-ipsecme-ikev2-multiple-ke: I-D.ounsworth-pq-composite-kem: I-D.wussler-openpgp-pqc: PQCAPI: title: "PQC - API notes" target: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/example-files/api-notes.pdf author: - name: NIST Post-Quantum Cryptography Project date: November 2022 SP800-56A: target: https://doi.org/10.6028/NIST.SP.800-56Ar3 title: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography author: - ins: E. Barker name: Elaine Barker - ins: L. Chen name: Lily Chen - ins: A. Roginsky name: Allen Roginsky - ins: A. Vassilev name: Apostol Vassilev - ins: R. Davis name: Richard Davis date: April 2018 seriesinfo: NIST Special Publication 800-56A SP800-56Cr2: target: https://doi.org/10.6028/NIST.SP.800-56Cr2 title: Recommendation for Key-Derivation Methods in Key-Establishment Schemes author: - ins: E. Barker name: Elaine Barker - ins: L. Chen name: Lily Chen - ins: R. Davis name: Richard Davis date: August 2020 seriesinfo: NIST Special Publication 800-56C SP800-185: target: https://doi.org/10.6028/NIST.SP.800-185 title: "SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash" author: - ins: J. Kelsey name: John Kelsey - ins: S. Chan name: Shu-jen Chan - ins: R. Perln name: Ray Perln date: 2016 seriesinfo: NIST Special Publication 800-185 FIPS202: target: https://doi.org/10.6028/NIST.FIPS.202 title: "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions" date: 2015 seriesinfo: Federal information Processing Standards Publication (FIPS) 202 BDPA08: target: "https://doi.org/10.1007/978-3-540-78967-3_11" title: On the Indifferentiability of the Sponge Construction author: - ins: G. Bertoni name: Guido Bertoni - ins: J. Daemen name: Joan Daemen - ins: M. Peters name: Michael Peters - ins: G. Assche name: Gilles van Assche date: 2008 GHP18: target: https://doi.org/10.1007/978-3-319-76578-5_7 title: KEM Combiners date: 2018 author: - ins: F. Giacon name: Federico Giacon - ins: F. Heuer name: Felix Heuer - ins: B. Poettering name: Bertram Poettering ETSI-QHKE: target: https://www.etsi.org/deliver/etsi_ts/103700_103799/103744/01.01.01_60/ts_103744v010101p.pdf title: Quantum-safe Hybrid Key Exchanges date: 2020-12 seriesinfo: ETSI TS 103 744 V1.1.1 ADKPRY22: title: "Practical (Post-Quantum) Key Combiners from One-Wayness and Applications to TLS." target: "https://eprint.iacr.org/2022/065" author: - ins: N. Aviram name: Nimrod Aviram - ins: B. Dowling name: Benjamin Dowling - ins: I. Komargodski name: Ilan Komargodski - ins: K.G. Paterson name: Kenneth G Paterson - ins: E. Ronen name: Eyal Ronen - ins: E. Yogev name: Eylon Yogev

--- abstract

The migration to post-quantum cryptography often calls for performing multiple key encapsulations in parallel and then combining their outputs to derive a single shared secret.

This document defines a comprehensible and easy to implement Keccak-based KEM combiner to join an arbitrary number of key shares, that is compatible with NIST SP 800-56Cr2 [SP800-56C] when viewed as a key derivation function. The combiners defined here are practical split-key PRFs and are CCA-secure as long as at least one of the ingredient KEMs is.

--- middle

Changes in this version

  • Re-structured {{sec-instantiation}} to clarify the dependence on the KDF defined in [SP800-56Cr2].

Terminology {#sec-terminology}

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 {{RFC2119}} {{RFC8174}} when, and only when, they appear in all capitals, as shown here.

This document is consistent with all terminology defined in {{I-D.driscoll-pqt-hybrid-terminology}}.

Key Encapsulation Mechanisms {#sec-kem-defn}

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.

Introduction {#sec-intro}

The need for a KEM combiner function arises in three different contexts within IETF security protocols:

  1. KEM / PSK hybrids where the output of a KEM is combined with a static pre-shared key.
  2. Post-quantum / traditional hybrid KEMs where output of a post-quantum KEM is combined with the output of a classical key transport or key exchange algorithm.
  3. KEM-based authenticated key exchanges (AKEs) where the output of two or more KEMs performed in different directions are combined.

This document normalizes a mechanism for combining the output of two or more KEMs.

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

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 {{sec-kem-defn}}.

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}}.

KEM Combiner construction {#sec-kem-combiner}

TODO: as per https://www.enisa.europa.eu/publications/post-quantum-cryptography-integration-study section 4.2, might need to specify behaviour in light of KEMs with a non-zero failure probability.

A KEM combiner is a function that takes the output of two or more KEM encapsulations and combines them to produce a single shared secret.

This document assumes that shared secrets are the output of a KEM, but without loss of generality they MAY also be any other source of cryptographic key material, such as pre-shared keys (PSKs), with PQ/PSK being a quantum-safe migration strategy being made available by some protocols, see for example IKEv2 in [RFC8784].

In general it is desirable to use a split-key PRF as a KEM combiner, meaning that the combiner has the properties of a PRF when keyed by any of its single inputs. The following simple yet generic construction can be used in all IETF protocols that need to combine the output of two or more KEMs:

ss = KDF(k_1 || ... || k_n || fixedInfo, outputBits)

{: #tab-kemCombiner title="general KEM combiner construction" }

where:

  • KDF represents a suitable choice of a cryptographic key derivation function as defined in {{sec-instantiation}}.
  • k_i represent the constant-length input keys and is discussed in {{sec-k_i-construction}},
  • fixedInfo is some protocol-specific KDF binding,
  • outputBits determines the length of the output keying material
  • || represents concatenation.

In {{sec-instantiation}} several possible practical instantiations are listed that are in compliance with NIST SP-800 56Cr2 [SP800-56Cr2]. The shared secret ss MAY be used directly as a symmetric key, for example as a MAC key or as a Key Encryption Key (KEK).

The values k_i can be processed individually, without requiring to store intermediate values except for the hash state and the protocol binding information required for fixedInfo.

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.

k_i construction {#sec-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 {{tab-kemCombiner}}:

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.

Note on the order of parameters

For a two-KEM instantiation with length encoding, the construction is

KDF(ct_1 || rlen(ct_1) || ss_1 || rlen(ss_1) || 
    ct_2 || rlen(ct_2) || ss_2 || rlen(ss_2), fixedInfo)

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.

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}}.

Practical instantiations {#sec-instantiation}

The KDF must be instantiated with cryptographically-secure choices for KDF. The following are RECOMMENDED KDF constructions based on NIST SP800-56Cr2 [SP800-56Cr2] with Keccak-based instatiations, but other choices MAY be made for example to allow for future cryptographic agility. A protocol using a different instantiation MUST justify that it will behave as a split-key PRF, as required in {{GHP18}}.

Instantiation number KDF construction Auxiliary FunctionH(x) hashSize outputBits
1 {#sec-kmac-kdf} Option 3 with KMAC128 128 bit Variable
2 {#sec-kmac-kdf} Option 3 with KMAC256 256 bit Variable
3 {#sec-hash-kdf} Option 1 with SHA3-256 256 bit 256 bit
4 {#sec-hash-kdf} Option 1 with SHA3-512 512 bit 512 bit
{: #tab-kdfs title="KDF instantiations"}

As justified in the security considerations, we recommend only Keccak-based instantiations because assuming there are no weaknesses found in the Keccak permutation, it behaves as a split-key PRF that can be keyed by any input k_i. SHAKE is also not included in the list as it is not allowed by {{SP800-56A}} section 7, and does not provide any implementation advantage over KMAC.

KMAC constructions are RECOMMENDED over SHA-3, as KMAC offers a simple cSHAKE-based construction, with the advantage of returning an unrelated output when requesting a different outputBits KEK length.

KMAC based construction {#sec-kmac-kdf}

This section defines a KDF(Z, OtherInput, outputBits) as per [SP800-56Cr2] section 4.1 Option 3 using the KMAC primitive as specified in NIST SP 800-185 {{SP800-185}}. To instantiate KMAC#:

KMAC is defined in NIST SP 800-185 [SP800-185]. The KMAC#(K, X, L, S) parameters MUST be instantiated as follows:

  • KMAC# : either KMAC128 or KMAC256 as per {{tab-kdfs}}.
  • K: a context-specific string of which MAY be used as an additional option to perform context separation, in scenarios where OtherInput is not sufficient.
  • X: the message input to KDF(), as defined above.
  • L: integer representation of outputBits.
  • S: as specified in [SP800-56Cr2], it is the 8-bit ASCII string "KDF".

Since we are setting L = outputBits, Step 1 of the process in [SP800-56Cr2] section 4.1 will always be reps = ceil(L / H_outputBits) = 1. Also, since [SP800-56Cr2] allows SHA3-based constructions to take arbitrarily long inputs, we can skip step 4.

That means KDF(Z, OtherInput) reduces to:

KMAC#(K, 0x00000001 || Z || fixedInfo, L, S)

Hash-and-counter based construction {#sec-hash-kdf}

This section defines a KDF(Z, OtherInput) as per [SP800-56Cr2] section 4.1 Option 1 using the SHA3 primitive as specified in NIST FIPS 202 {{FIPS202}}.

This KDF construction requires the full KDF construction as specified in [SP800-56Cr2] section 4.1. No additional parameters are required.

IANA Considerations {#sec-iana}

None.

Security Considerations

The proposed instantiations in {{sec-instantiation}} are practical split-key PRFs since this specification limits to the use of Keccak-based constructions. The sponge construction was proven to be indifferentiable from a random oracle {{BDPA08}}. More precisely, for a given capacity c the indifferentiability proof shows that assuming there are no weaknesses found in the Keccak permutation, an attacker has to make an expected number of 2^(c/2) calls to the permutation to tell Keccak from a random oracle. For a random oracle, a difference in only a single bit gives an unrelated, uniformly random output. Hence, to be able to distinguish a key k, derived from shared keys k_i from a random bit string, an adversary has to correctly guess all key shares k_i entirely.

The proposed construction in {{sec-kem-combiner}} with the instantiations in {{sec-instantiation}} preserves IND-CCA2 of any of its ingredient KEMs, i.e. the newly formed combined KEM is IND-CCA2 secure as long as at least one of the ingredient KEMs is. Indeed, the above stated indifferentiability from a random oracle qualifies Keccak as a split-key pseudorandom function as defined in {{GHP18}}. That is, Keccak behaves like a random function if at least one input shared secret ss_i is picked uniformly at random. Our construction can thus be seen as an instantiation of the IND-CCA2 preserving Example 3 in Figure 1 of {{GHP18}}, up to some reordering of input shared secrets ss_i and ciphertexts ct_i and their potential compression H(ss_i || ct_i) by a cryptographic hash function.

--- back

Acknowledgements

{:numbered="false"}

This document incorporates contributions and comments from a large group of experts. The authors would especially like to acknowledge the expertise and tireless dedication of the following people, who attended many long meetings and generated millions of bytes of electronic mail and VOIP traffic over the past years in pursuit of this document:

Serge Mister, Douglas Stebila, Nimrod Aviram, and Andreas Huelsing.

We are grateful to all, including any contributors who may have been inadvertently omitted from this list.

This document borrows text from similar documents, including those referenced below. Thanks go to the authors of those documents. "Copying always makes things easier and less error prone" - [RFC8411].