Post-quantum Hybrid Key Exchange in the IKEv2 with FrodoKEM

Abstract

RFC 9370 specifies a framework that supports mulitple key encapsulation mechanisms (KEMs) in the Internet Key Exchange Protocol Version 2 (IKEv2) by allowing up to 7 layers of additiona KEMs employed with the oringal ECDH to derive the final shared secret keys for IPsec protocols. The primitive goal is to mitigate the security threat against quantum computers by hybriding additional post-quantum (PQ) KEMs with the orinigal ECDH key exchange. This draft specifies how one QP KEMs, FrodoKEM, is instantiated in the IKEv2 as the additional KEMs with the main ECDH to achieve hybrid key agreement.¶

[EDNOTE: IANA KE code points for FrodoKEM may need to be assigned, as the code points for ML-KEM has been considered in [I-D.D24]. ]¶

1. Introduction

To mitigate the security threats on key exchanges again quantum computers, especialy the harvest-now-and-decrypt-later (HNDL) attack, the approach of hybrid key encapsulation mechanisms (KEMs) has been proposed to achieve secure key exchange if at least one of KEMs is still secure. In particular, hybrid KEMs is supposed to be used in the scenarios where one or multiple traditional KEMs are used together with one or multiple post-quantum KEMs [I-D.D24]. The Internet Key Exchange Protocol Version 2 (IKEv2), which sepecifies the key exchange procedures of IPSec, has to be updated for quantum resistant security. For this purpose, RFC 9370 [RFC9370] describes a framework to hybrid mulitple key encapsulation mechanisms (KEMs), which extends the IKEv2 by allowing multiple key exchanges to take place for deriving shared secret keys during a Security Association (SA) setup. Essentially, this speficiation employs the IKE_INTERMEDIATE exchange, which is a new IKE message introduced in [RFC9242] so that multiple key exchanges can be run to establish an IKE SA via exchanging additional PQ public keys and ciphertexts between a client and a server. RFC 9370 also introduces IKE_FOLLOWUP_KE, a new IKEv2 exchange for realizing the same purpose when the IKE SA is being rekeyed or is creating additional Child SAs.¶

However, RFC 9370 just specifies the framework of hybrid KEMS but it has not been instantiated for concrete multiple KEMS. [I-D.KR24] desribes how the framework given by RFC 9370 can be run with the post-quantum (PQ) ML-KEM [FIPS203], previously called Kyber, which is the standard published by NIST in August of 2024. However, on the one hand, FRC 9350 allows up to 7 layers of additiona KEMs employed with the oringal ECDH to derive final shared secret keys for the IKEv2. On the other hand, for some applications (e.g. financial services) demanding high security level, additional PQ KEMs may be desired for completing the hybrid KEMs for the IKEv2. Currently, ISO is now standardizing three PQ KEM aglorithms: Kyber, FrodoKEM, and classic McElliece. Note that Frodo [Frodo] is unstructured lattice based KEM, whose security is more conservative compared to ML-KEM, which is based on structured lattice. Therefore, this draft is motivated to describe concretely how the frame of hybrid KEMs for the IKEv2 specified in RFC 9370 can be run via hybriding the ogirinal ECDH and FrodoKEM, even with ML-KEM together, if necessary.¶

Here are a few reasons for explaining why such diversity of KEMs is important for the IKEv2 (and also other security protocols).¶

• The availability of various PQC algorithms is beneficial to applications as different PQC algorithms could be selected according to practical performance requirements and security requirements.¶
• Generally speaking, post-quantum algorithms are still not mature yet. Some algorithms may turn out to be insecure after a number of years’ study and/or standardization. An example is SIKE, which had been in the NIST standardization progres for several years until it was totally broken in Aug. of 2022.¶
• Cryptographic agility shall play a crucial role in the PQ migration [OPM23]. To facilitate cryptographic agility, not only should the systems and protocols be engineered agile but also there should be a good size of standardized PQC algorithms available, which may be based on different hard problems.¶

However, the perfomace of Frodo is not as good as ML-KEM. In particular, the sizes of pulic key and ciphtertext of FrodoKEM are roughtly 10 times larger than those of ML-KEM. Consequently, this will almost unavoidably triger the issue of IKE fragmentation.¶

2. Requirements Language

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. Key Encapsulation Mechanism and FrodoKEM

Key encapsulation mechanism(KEM) is a kind of key exchange, which allows one entity to encapsulate a secret key under a (longterm or ephemeral) public key of another entity. By following the definiton given in [I-D.KR24], a KEM consists of three algorithms:¶

• KeyGen(k) -> (pk, sk): A probabilistic key generation algorithm, which generates a public encapsulation key pk and a secret decapsulation key sk, when a security parameter k is given.¶
• Encaps(pk) -> (ct, ss): A probabilistic encapsulation algorithm, which takes as input a public encapsulation key pk and outputs a ciphertext ct and shared secret ss.¶
• Decaps(sk, ct) -> ss: A decapsulation algorithm, which takes as input a secret decapsulation key sk and ciphertext ct and outputs a shared secret ss.¶

ML-KEM and FrodoKEM are two well-known post-quantum KEMs from lattice. More specifically, ML-KEM [FIPS203], orignially called Kyber, has been published as the only one KEM scheme by NIST in August of 2024. It is a Module-Lattice based Key-Encapsulation Mechanism, so called ML-KEM. ML-KEM is also specified as an Internet Draft in IETF [I-D.Kyber24].¶

FrodoKEM [Frodo] is one of three KEMS in the process of ISO stardandization, which is based on unstructured lattice problem. However, the perfomace of Frodo is not as good as ML-KEM. Specifically, as showen in Table 1, the sizes of pulic key and ciphtertext of FrodoKEM are roughtly 10 times larger than those of ML-KEM. Consequently, this will almost unavoidably triger the issue of IKE fragmentation [RFC7383] [RFC9242].¶

  +===============+============+============+============+===============+
  |   Algorithms  | secret key | public key | ciphterext | shared secret |
  |               |    sk      |    pk      |     ct     |      ss       |
  +===============+============+============+============+===============+
  | ML-KEM-512    |    800     |   1,632    |    768     |      32       |
  +---------------+------------+------------+------------+---------------+
  | ML-KEM-768    |    1,184   |   2,400    |    1,088   |      32       |
  +---------------+------------+------------+------------+---------------+
  | ML-KEM-1024   |    1,568   |   3,168    |    1,568   |      32       |
  +---------------+------------+------------+------------+---------------+
  | FrodoKEM-640  |    19,888  |   9,616    |    9,752   |      16       |
  +---------------+------------+------------+------------+---------------+
  | FrodoKEM-976  |    31,296  |   15,632   |    15,792  |      24       |
  +---------------+------------+------------+------------+---------------+
  | FrodoKEM-1344 |    43,088  |   21,520   |    21,696  |      32       |
  +---------------+------------+------------+---------------+------------+
  Table 1: Size (in bytes) of keys and ciphertexts of ML-KEM and FrodoKEM

8. Normative References

[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/info/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/info/rfc8174>.

[RFC7296]

Kaufman, C., Hoffman, P., Nir, Y., Eronen, P., and T. Kivinen, "Internet Key Exchange Protocol Version 2 (IKEv2)", STD 79, RFC 7296, DOI 10.17487/RFC7296, October 2014, <https://www.rfc-editor.org/info/rfc7296>.

[RFC7383]

Smyslov, V., "Internet Key Exchange Protocol Version 2 (IKEv2) Message Fragmentation", RFC 7383, DOI 10.17487/RFC7383, November 2014, <https://www.rfc-editor.org/info/rfc7383>.

[RFC9242]

Smyslov, V., "Intermediate Exchange in the Internet Key Exchange Protocol Version 2 (IKEv2)", RFC 9242, DOI 10.17487/RFC9242, May 2022, <https://www.rfc-editor.org/info/rfc9242>.

[RFC9370]

Tjhai, CJ., Tomlinson, M., Bartlett, G., Fluhrer, S., Van Geest, D., Garcia-Morchon, O., and V. Smyslov, "Multiple Key Exchanges in the Internet Key Exchange Protocol Version 2 (IKEv2)", RFC 9370, DOI 10.17487/RFC9370, May 2023, <https://www.rfc-editor.org/info/rfc9370>.

9. Informative References

[I-D.D24]

F. Driscoll, F., "Terminology for Post-Quantum Traditional Hybrid Schemes", Work in Progress, Internet-Draft,, February 2024, <https://datatracker.ietf.org/doc/draft-ietf-pquip-pqt-hybrid-terminology/>.

[I-D.KR24]

Kampanakis, K. and G. Ravago, "Post-quantum Hybrid Key Exchange with ML-KEM in the Internet Key Exchange Protocol Version 2 (IKEv2)", Work in Progress, Internet-Draft,, February 2024, <https://datatracker.ietf.org/doc/draft-kampanakis-ml-kem-ikev2/>.

[I-D.Kyber24]

Schwabe, P. and B. Westerbaan, "Kyber Post-Quantum KEM", Work in Progress, Internet-Draft,, January 2024, <https://datatracker.ietf.org/doc/draft-cfrg-schwabe-kyber/>.

[OPM23]

Ott, D., Paterson, K., and D. Moreau, "Where Is the Research on Cryptographic Transition and Agility?", Communications of the ACM, 66(4): 29-32, January 2023.

[Frodo]

Alkim, E., Bos, J. W., Ducas, L., Longa, P., Mironov, I., Naehrig, N., Nikolaenko, V., Peikert, C., Raghunathan, A., and D. Stebila, "FrodoKEM: Learning With Errors Key Encapsulation", Preliminary Standardization Proposal submitted to ISO , March 2023, <https://frodokem.org/files/FrodoKEM-standard_proposal-20230314.pdf>.

[FIPS203]

National Institute of Standards and Technology, "FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard", Federal Information Processing Standards Publication , August 2024, <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf>.