Post-quantum Hybrid Key Exchange in the IKEv2 with FrodoKEM

1.1. Notes of Change

Two main changes have been made in version 01, as a response to comments received at 122 meeting:¶

• Restructured the draft.¶
• Reduced the point codes from 12 to 6 (eFrodoKEM).¶

1.2. Introduction

Cryptographically-relevant quantum computers (CRQC) pose a threat to cryptographically protected data. In particular, the so-called harvest-now-and-decrypt-later (HNDL) attack is considered an imminent threat. To mitigate this threat the concept of hybrid key encapsulation mechanisms (KEMs) has been proposed to achieve secure key exchange if at least one of the KEMs is still secure. “Multiple key exchanges in the Internet Key Exchange Protocol Version 2 (IKEv2) [RFC9370] specifies a framework to perform hybrid key encapsulation in the IKEv2 by allowing multiple key exchanges to take place for deriving shared secret keys during a Security Association (SA) setup. Essentially, this specification employs the IKE_INTERMEDIATE exchange, which is a new IKEv2 message introduced in “Intermediate Exchange in the Internet Key Exchange Protocol Version 2 (IKEv2)” [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 additional Child SAs are created.¶

However, [RFC9370] just specifies the framework of hybrid KEMs and has to be been instantiated for concrete KEMs by separate documents. [I-D.KR24] describes how the framework given by [RFC9370] can be run with the ML-KEM [FIPS203], previously called Kyber, which has been standardized by NIST in August 2024. However, on the one hand, [RFC9370] allows up to 7 layers of additional KEMs 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 use with [RFC9370]. Currently, ISO is standardizing three PQ KEM algorithms (EDNOTE: we may want to change the wording since the ISO standard will be finished eventually): Kyber, FrodoKEM, and Classic McEliece. Note that FrodoKEM [FrodoKEM] [I-D.LBES25] 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 instantiated with FrodoKEM. FrodoKEM should be used together with a traditional key exchange mechanism such as ECDH and in addition, may be used with further KEMs, e.g. ML-KEM.¶

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 PQ algorithms is beneficial to applications as different PQ algorithms could be selected according to practical performance 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 July of 2022 [CD22].¶
• 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 number of standardized PQC algorithms available, which may be based on different hard problems.¶

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

3.1. KEMs

Key encapsulation mechanism (KEM) is a kind of key exchange, which allows one entity to encapsulate a secret key under a (long-term 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.¶

3.3. Comparison to ML-KEM

ML-KEM and FrodoKEM are two well-known post-quantum KEMs based on lattices. More specifically, ML-KEM [FIPS203], originally called Kyber, has been standardized 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].¶

However, the perfomace of FrodoKEM is not as good as ML-KEM. Specifically, as shown in Table 1, the sizes of pulic key and ciphtertext of FrodoKEM are roughly 10 times larger than those of ML-KEM. Consequently, this will almost unavoidably trigger IKE fragmentation [RFC7383] [RFC9242], when FrodoKEM is used in the IKEv2.¶

  +===============+============+============+============+===============+
  |   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       |
  +---------------+------------+------------+------------+---------------+
  | eFrodoKEM-640 |    19,888  |   9,616    |    9,750   |      16       |
  +---------------+------------+------------+------------+---------------+
  | eFrodoKEM-976 |    31,296  |   15,632   |    15,744  |      24       |
  +---------------+------------+------------+------------+---------------+
  | eFrodoKEM-1344|    43,088  |   21,520   |    21,632  |      32       |
  +---------------+------------+------------+---------------+------------+
  Table 1: Size (in bytes) of keys and ciphertexts of ML-KEM and eFrodoKEM