ML-KEM for HPKE
draft-connolly-cfrg-hpke-mlkem-00

Crypto Forum                                                 D. Connolly
Internet-Draft                                                 SandboxAQ
Intended status: Informational                          28 February 2024
Expires: 31 August 2024

                            ML-KEM for HPKE
                   draft-connolly-cfrg-hpke-mlkem-00

Abstract

   This memo defines the ML-KEM-768-based and ML-KEM-1024-based
   ciphersuites for HPKE (RFC9180).  ML-KEM is believed to be secure
   even against adversaries who possess a quantum computer.

About This Document

   This note is to be removed before publishing as an RFC.

   The latest revision of this draft can be found at
   https://dconnolly.github.io/draft-connolly-cfrg-xwing-kem/draft-
   connolly-cfrg-xwing-kem.html.  Status information for this document
   may be found at https://datatracker.ietf.org/doc/draft-connolly-cfrg-
   hpke-mlkem/.

   Discussion of this document takes place on the Crypto Forum Research
   Group mailing list (mailto:cfrg@ietf.org), which is archived at
   https://mailarchive.ietf.org/arch/search/?email_list=cfrg.  Subscribe
   at https://www.ietf.org/mailman/listinfo/cfrg/.

   Source for this draft and an issue tracker can be found at
   https://github.com/dconnolly/draft-connolly-cfrg-xwing-kem.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

Connolly                 Expires 31 August 2024                 [Page 1]
Internet-Draft                 hpke-mlkem                  February 2024

   This Internet-Draft will expire on 31 August 2024.

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Motivation  . . . . . . . . . . . . . . . . . . . . . . .   2
     1.2.  Not an authenticated KEM  . . . . . . . . . . . . . . . .   3
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   3
   3.  Construction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     3.1.  Encap and Decap . . . . . . . . . . . . . . . . . . . . .   3
     3.2.  AuthEncap and AuthDecap . . . . . . . . . . . . . . . . .   3
   4.  Security Considerations . . . . . . . . . . . . . . . . . . .   4
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   4
   6.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   5
     6.1.  Normative References  . . . . . . . . . . . . . . . . . .   5
     6.2.  Informative References  . . . . . . . . . . . . . . . . .   6
   Appendix A.  Acknowledgments  . . . . . . . . . . . . . . . . . .   6
   Appendix B.  Change log . . . . . . . . . . . . . . . . . . . . .   6
     B.1.  Since draft-connolly-cfrg-hpke-mlkem-00 . . . . . . . . .   6
   Appendix C.  Test Vectors . . . . . . . . . . . . . . . . . . . .   6
     C.1.  ML-KEM-768, HKDF-SHA256, AES-128-GCM  . . . . . . . . . .   6
     C.2.  ML-KEM-1024, HKDF-SHA512, AES-256-GCM . . . . . . . . . .   6
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .   6

1.  Introduction

1.1.  Motivation

   The final draft for ML-KEM is expected in 2024.  For parties that
   must move to exclusively post-quantum algorithms, having a pure PQ
   choice for public-key hybrid encryption is desireable.  HPKE is the
   leading modern protocol for public-key encryption, and ML-KEM as a
   post-quantum IND-CCA2-secure KEM fits nicely into HPKE's design.
   Supporting multiple security levels for ML-KEM allow a spectrum of
   use cases including settings where NIST PQ security category 5 is
   required.

Connolly                 Expires 31 August 2024                 [Page 2]
Internet-Draft                 hpke-mlkem                  February 2024

1.2.  Not an authenticated KEM

   ML-KEM is a plain KEM that does not support the static-ephemeral key
   exchange that allows HPKE based on Diffie-Hellman based KEMs its
   (optional) authenticated modes.

2.  Conventions and Definitions

   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.

3.  Construction

   We construct 'wrapper' KEMs based on ML-KEM to bind the encapsulated
   shared secret ciphertext into the shared secret value, such that the
   final KEM has similar binding security properties as the original
   DHKEM HPKE was designed around.

   The encapsulation and decapsulation keys are computed, serialized,
   and deserialized the same as in [FIPS203].

   We use HKDF-SHA256 and HKDF-SHA512 as the HPKE KDFs and AES-128-GCM
   and AES-256-GCM as the AEADs for ML-KEM-768 and ML-KEM-1024
   respectively.

3.1.  Encap and Decap

   ~~ def Encap(pkR): ss, ct = MLKEM.Encaps(pkR)

   shared_secret = ExtractAndExpand(ss, ct)

   return shared_secret, ct ~~

   ~~ def Decap(enc, skR): ss, ct = MLKEM.Decaps(enc, skR)

   shared_secret = ExtractAndExpand(ss, ct)

   return shared_secret, ct ~~

3.2.  AuthEncap and AuthDecap

   HPKE-ML-KEM is not an authenticeted KEM and does not support
   AuthEncap() or AuthDecap(), see Section 1.2.

Connolly                 Expires 31 August 2024                 [Page 3]
Internet-Draft                 hpke-mlkem                  February 2024

4.  Security Considerations

   HPKE's IND-CCA2 security relies upon the IND-CCA2 security of the
   underlying KEM and AEAD schemes.  ML-KEM is believed to be IND-CCA
   secure via multiple analyses.

   The HPKE key schedule is independent of the encapsulated KEM shared
   secret ciphertext of the ciphersuite KEM, and dependent on the shared
   secret produced by the KEM.  If HPKE had committed to the
   encapsulated shared secret ciphertext, we wouldn't have to worry
   about the binding properties of the ciphersuite KEM's X-BIND-K-CT
   properties.  These computational binding properties for KEMs were
   formalized in [CDM23].

   ML-KEM, unlike DHKEM, is also an implicitly-rejecting instantiation
   of the Fujisaki-Okamoto transform, meaning the ML-KEM output shared
   secret may be computed differently in case of decryption failure,
   that reults in different binding properties, such as the lack of X-
   BIND-CT-PK and X-BIND-CT-K completely.

   The DHKEM construction in HPKE provides MAL-BIND-K-PK and MAL-BIND-
   K-CT security (the shared secret 'binds' or uniquely determines the
   encapsulation key and the encapsualted shared secret ciphertext),
   where the adversary is able to create the key pairs any way they like
   in addition to the key generation.  ML-KEM as specified provides
   LEAK-BIND-PK,K-CT security, where the involved key pairs are output
   by the key generation algorithm of the KEM and then leaked to the
   adversary.  LEAK-BIND-PK,K-CT is a weaker property than the DHKEM
   properties as it is not resistant in the presence of an actively
   malicious adversary, and requires both the shared secret _and_the
   public key together to uniquely bind the ciphertext, so its shared
   secret alone is insufficient.

   This results in a wrapper construction around ML-KEM to bind to the
   encapsulated shared secret ciphertext as the kem_context provided to
   ExtractAndExpand().  This binds the final shared_secret (K) to the
   encapsulated shared secret ciphertext (CT), achieving MAL-BIND-K-CT.
   ML-KEM already is MAL-BIND-K-PK as the hash of the encapsulation key
   (PK) is an input the computation of the shared secret (K).  Together
   this wrapper KEM matches the binding properties of HPKE's default KEM
   construction DHKEM in being MAL-BIND-K-CT and MAL-BIND-K-PK.

5.  IANA Considerations

   This document requests/registers two new entries to the "HPKE KEM
   Identifiers" registry.

   Value:  0x0070 (please)

Connolly                 Expires 31 August 2024                 [Page 4]
Internet-Draft                 hpke-mlkem                  February 2024

   KEM:  ML-KEM-768

   Nsecret:  32

   Nenc:  1088

   Npk:  1184

   Nsk:  2400

   Auth:  no

   Reference:  This document

   Value:  0x0080 (please)

   KEM:  ML-KEM-1024

   Nsecret:  32

   Nenc:  1568

   Npk:  1568

   Nsk:  3168

   Auth:  no

   Reference:  This document

6.  References

6.1.  Normative References

   [FIPS203]  "*** BROKEN REFERENCE ***".

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [RFC9180]  Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid
              Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180,
              February 2022, <https://www.rfc-editor.org/rfc/rfc9180>.

Connolly                 Expires 31 August 2024                 [Page 5]
Internet-Draft                 hpke-mlkem                  February 2024

6.2.  Informative References

   [CDM23]    Cremers, C., Dax, A., and N. Medinger, "Keeping Up with
              the KEMs: Stronger Security Notions for KEMs and automated
              analysis of KEM-based protocols", 2023,
              <https://eprint.iacr.org/2023/1933.pdf>.

Appendix A.  Acknowledgments

   The authors would like to thank Cas Cremers for their input.

Appendix B.  Change log

      *RFC Editor's Note:* Please remove this section prior to
      publication of a final version of this document.

   TODO

B.1.  Since draft-connolly-cfrg-hpke-mlkem-00

   TODO

Appendix C.  Test Vectors

   This section contains test vectors formatted similary to that which
   are found in [RFC9180], with two changes.  First, we only provide
   vectors for the non-authenticated modes of operation.  Secondly, as
   ML-KEM encapsulation does not involve an ephemeral keypair, we omit
   the ikmE, skEm, pkEm entries and provide an ier entry instead.  The
   value of ier is the randomness used to encapsulate, so ier[0:32] is
   the seed that is fed to H in the first step of ML-KEM encapsulation
   in [FIPS203].

C.1.  ML-KEM-768, HKDF-SHA256, AES-128-GCM

   TODO

C.2.  ML-KEM-1024, HKDF-SHA512, AES-256-GCM

   TODO

Author's Address

   Deirdre Connolly
   SandboxAQ
   Email: durumcrustulum@gmail.com

Connolly                 Expires 31 August 2024                 [Page 6]