ML-KEM Security Considerations
draft-sfluhrer-cfrg-ml-kem-security-considerations-00
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Active".
|
|
|---|---|---|---|
| Authors | Scott Fluhrer , Quynh Dang , John Preuß Mattsson | ||
| Last updated | 2024-10-07 | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-sfluhrer-cfrg-ml-kem-security-considerations-00
Crypto Forum S. Fluhrer
Internet-Draft Cisco Systems
Intended status: Informational Q. Dang
Expires: 10 April 2025 NIST
J. Preuß Mattsson
Ericsson
October 2024
ML-KEM Security Considerations
draft-sfluhrer-cfrg-ml-kem-security-considerations-00
Abstract
NIST standardized ML-KEM as FIPS 203 in August 2024. This document
discusses how to use ML-KEM - that is, what problem it solves, and
how to use it securely.
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."
This Internet-Draft will expire on 4 April 2025.
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.
Fluhrer, et al. Expires 10 April 2025 [Page 1]
Internet-Draft ML-KEM Security October 2024
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Using ML-KEM . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. ML-KEM Key Generation . . . . . . . . . . . . . . . . . . 3
2.2. ML-KEM Encapsulation . . . . . . . . . . . . . . . . . . 4
2.3. ML-KEM Decapsulation . . . . . . . . . . . . . . . . . . 4
2.4. ML-KEM Parameter Sets . . . . . . . . . . . . . . . . . . 5
3. KEM Security Considerations . . . . . . . . . . . . . . . . . 5
4. ML-KEM Security Considerations . . . . . . . . . . . . . . . 6
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
6. References . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1. Normative References . . . . . . . . . . . . . . . . . . 7
6.2. Informative References . . . . . . . . . . . . . . . . . 7
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 8
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8
1. Introduction
A large reliable quantum computer (often termed a Cryptographically
Relevant Quantum Computer or CRQC) would be able to break protocols
which rely on the traditional RSA, DH, or ECDH methods of securely
exchanging keys. Even though we do not believe, at the time of this
writing, there exists a CRQC, there still remains the possibility
that an adversary may record the protocol exchange, and then later
(when they have access to a CRQC) go ahead and read the traffic.
Because of this potential threat, NIST has standardized ML-KEM
(Module-Lattice-Based Key-Encapsulation Mechanism), which is
standardized in FIPS 203 [FIPS203]. ML-KEM is used to generate a
shared secret key between two parties. One party (Alice) generates a
public/private keypair, and sends the public key to the other party
(Bob). Bob uses the public key and some randomness to generate both
the shared secret key and a ciphertext. Bob then sends the
ciphertext to Alice, who uses her private key to generate the same
shared secret key. NIST plans to standardize one or more code-based
KEMs in the future.
The fundamental security property is that someone listening to the
exchanges (and thus obtains both the public key and the ciphertext)
cannot reconstruct the shared secret key and this is true even if the
adversary has access to a CRQC. ML-KEM is IND-CCA2 secure, that is,
it remains secure even if an adversary is able to submit arbitrary
ciphertexts and observe the resulting shared key. Submitting invalid
ciphertexts to a ML-KEM.Decaps does not help the attacker obtain
information about the decryption key of the PKE-Decrypt function
inside the ML-KEM.Decaps. Substituting the public key Alice sends
Bob by another public key chosen by the attacker will not help the
Fluhrer, et al. Expires 10 April 2025 [Page 2]
Internet-Draft ML-KEM Security October 2024
attacker get any information about Alice's private key, it would just
make Alice and Bob not have a same shared secret key. For practical
purposes, IND-CCA2 means that ML-KEM is secure to use with static
public keys.
ML-KEM is what is termed a Key Encapsulation Mechanism. One common
misunderstanding of that term is the expectation that Bob freely
chooses the shared secret, and encrypts that when sending to Alice.
What happens in ML-KEM is that randomness from both sides are used to
contribute to the shared secret. That is, ML-KEM internally
generates the shared secret in a way that Bob cannot select the
value. Now, Bob can generate a number of ciphertext/shared secret
pairs, and select the shared secret that he prefers, but he cannot
freely choose it or make secrets shared with two parties be equal.
This is different from RSA-KEM [RFC5990], where Bob cannot select the
value, but can encapsulate the same shared secret to many recipients.
A KEM (such as ML-KEM) sounds like it may be a drop-in replacement
for Diffie-Hellman, however this is not the case. In Diffie-Hellman,
the parties exchange two public keys, whereas in a KEM, the
ciphertext is necessarily a function of Alice's public key, and thus
can only be useful only with that specific public key. As long a the
application can handle larger public keys and ciphertexts, a KEM is a
drop-in replacement for 'ephemeral-ephemeral' key exchange in
protocols like TLS [RFC8446] and SSH [RFC4253] as well as 'static-
ephemeral' key exchange in protocols like ECIES/HPKE [RFC9180]. A
KEM is not a drop-in replacement in applications such as the Diffie-
Hellman ratchet in Signal [SIGNAL], implicit 'ephemeral-static' DH
authentication in Noise [NOISE], Wireguard [WIRE], and EDHOC
[RFC9528], and 'static-static' configurations in CMS [RFC6278] and
Group OSCORE [I-D.ietf-core-oscore-groupcomm], where both sides have
long-term public keys. Furthermore ML-KEM is not a drop-in
replacement for RSA-KEM as RSA-KEM can encapsulate the same shared
secret to many recipients whereas ML-KEM cannot.
2. Using ML-KEM
To use ML-KEM, there are three steps involved
2.1. ML-KEM Key Generation
The first step for Alice is to generate a public and private keypair.
In FIPS 203, this function is termed ML-KEM.KeyGen() (see section 7.1
of [FIPS203]). It internally calls the random number generator for a
seed and produces both a public key (termed an encapsulation key in
FIPS 203) and a private key (termed a decapsulation key).
Fluhrer, et al. Expires 10 April 2025 [Page 3]
Internet-Draft ML-KEM Security October 2024
The public key can be freely published (and Bob will need it for his
part of the process); this step may be performed simply by
transmitting the key to Bob. However, the private key must be kept
secret.
2.2. ML-KEM Encapsulation
The second step is for Bob to generate a ciphertext and a shared
secret key.
To perform this step, Bob would first run the Encapsulation Key Check
on Alice's public key as outlined at the beginning of section 7.2 of
[FIPS203]. If that test passes, then Bob would perform the what FIPS
203 terms as ML-KEM.Encaps() (see section 7.2 of [FIPS203]). This
step takes the validated public key, internally calls the random
number generator for a seed, and produces both a ciphertext and a
32-byte shared secret key.
The ciphertext can be transmitted back to Alice; if the exchange is
successful, the 32-byte shared secret key will be the key shared with
Alice.
It may be that some libraries combine the validation and the
encapsulation step; you should check whether the library you are
using does. For static public keys, the Encapsulation Key Check only
needs to be performed once.
2.3. ML-KEM Decapsulation
The third and final step is for Alice to take the ciphertext and
generate the shared secret key.
To perform this step, Alice would first run the Decapsulation Key
Check on Bob's ciphertext as outlined at the beginning of section 7.3
of [FIPS203]. If that test passes, then Bob would perform the what
FIPS 203 terms as ML-KEM.Decaps() (see section 7.3 of [FIPS203]).
This step takes the ciphertext from Bob and the private key that was
previously generated by Alice, and produces a 32-byte shared secret
key.
If the exchange is successful, the 32-byte key generated on both
sides will be the same.
It may be that some libraries combine the validation and the
decapsulation step; you should check whether the library you are
using does.
Fluhrer, et al. Expires 10 April 2025 [Page 4]
Internet-Draft ML-KEM Security October 2024
2.4. ML-KEM Parameter Sets
ML-KEM comes with three parameter sets; ML-KEM-512, ML-KEM-768 and
ML-KEM-1024. It is assumed that Alice and Bob both know which
parameter sets they use (either by negotiation or by having one
selection fixed in the protocol).
Table 1 shows a summary of how those parameter sets differ:
+=============+=========+=========+=========+=========+===========+
| | pk size | sk size | ct size | ss size | as strong |
| | | | | | as |
+=============+=========+=========+=========+=========+===========+
| ML-KEM-512 | 800 | 1632 | 768 | 32 | AES-128 |
+-------------+---------+---------+---------+---------+-----------+
| ML-KEM-768 | 1184 | 2400 | 1088 | 32 | AES-192 |
+-------------+---------+---------+---------+---------+-----------+
| ML-KEM-1024 | 1568 | 3168 | 1568 | 32 | AES-256 |
+-------------+---------+---------+---------+---------+-----------+
Table 1: pk = public key, sk = private key, ct = ciphertext,
ss = shared key, all lengths in bytes
Table 2 shows an example of ML-KEM performance [EBACS]:
+=============+================+===============+===============+
| | key generation | encapsulation | decapsulation |
+=============+================+===============+===============+
| ML-KEM-512 | 244000 | 153000 | 202000 |
+-------------+----------------+---------------+---------------+
| ML-KEM-768 | 142000 | 103000 | 134000 |
+-------------+----------------+---------------+---------------+
| ML-KEM-1024 | 109000 | 77000 | 99000 |
+-------------+----------------+---------------+---------------+
Table 2: Single-core performance in operation per second on
AMD Ryzen 7 7700
As can be seen from Table 1 and Table 1, ML-KEM has significantly
larger public keys and ciphertexts than ECDH but very good
performance.
3. KEM Security Considerations
This section pertains to KEM (Key Encapsulation Mechanisms) in
general, including ML-KEM
Fluhrer, et al. Expires 10 April 2025 [Page 5]
Internet-Draft ML-KEM Security October 2024
To use a KEM, you need to use a high-quality source of entropy during
both the key-pair generation and ciphertext generation steps. If an
adversary can recover the random bits used in either of these
processes, they can recover the shared secret. If an adversary can
recover the random bits used during key generation, they can recover
the secret key.
Alice needs to keep her private key secret. It is recommended that
she zeroize her private key when she will have no further need of it.
A KEM (including ML-KEM) provides no authentication of either
communicating party. If an adversary could replace either the public
key or the ciphertext with its own, it would generate a shared key
with Alice or Bob. Hence, it is important that the protocol that
uses a KEM lets Bob be able to verify that the public key he obtains
came from Alice and that the ciphertext that Alice receives came from
Bob (that is, an entity that Alice is willing to communicate with).
Such verification can be performed by cryptographic methods such as
digital signatures or a MAC to verify integrity of the protocol
exchange transcript.
4. ML-KEM Security Considerations
This section pertains specifically to ML-KEM, and may not be true of
KEMs in general.
To use ML-KEM, you need a source of random bits with security
strength equal to greater than the security strength of the KEM
during both key generation and encapsulation steps. The
cryptographic library that implements ML-KEM may access this source
of randomness internally.
Alice must keep her private key secret (both private and secure from
modification). It is recommended that she zeroizes her private key
when she will have no further need of it.
If the ciphertext that Alice receives from Bob is tampered with
(either by small modification or by replacing it with an entirely
different ciphertext), the shared secret key that Alice derives will
be uncorrelated with the shared secret key that Bob obtains. An
attacker will not be able to determine any information about the
correct shared secret key or Alice's private key, even if the
attacker obtains Alice's modified shared secret key which is the
output of the ML-KEM.Decaps function taking the modified ciphertext
as input.
Fluhrer, et al. Expires 10 April 2025 [Page 6]
Internet-Draft ML-KEM Security October 2024
It is secure to reuse a public key multiple times. That is, instead
of Alice generating a fresh public and private keypair for each
exchange, Alice may generate a public key once, and then publish that
public key, and use it for multiple incoming ciphertexts, generating
multiple shared secret keys. While this is safe, it is recommended
that if the protocol allows it (if Alice and Bob exchange messages
anyways) that Alice generates a fresh keypair each time (and zeroize
the private key immediately after) to obtain Perfect Forward Secrecy.
Be noted that generally key generation of ML-KEM is very fast, see
Table 2. That is, if Alice's system is subverted (either by a hacker
or a legal warrant), the previous communications remain secure
(because Alice no longer has the information needed to recover the
shared secret keys).
Alice and Bob must perform the Key Check steps (the Encapsulation Key
Check on the public key for Bob, the Decapsulation Key Check on the
ciphertext for Alice). The cryptographical libraries that Alice and
Bob use may automatically perform such checks; if so, that should be
verified.
The shared secret key for all three parameter sets, ML-KEM-512, ML-
KEM-768 and ML-KEM-1024 are 32 bytes which are indistinguishable from
32-byte pseudorandom byte-strings of 128, 192 and 256 bits of
strengths respectively. As such, it is suitable both to use directly
as a symmetric key (for use by a symmetric cipher such as AES or a
MAC), and for inserting into a Key Derivation Function. This is in
contrast to a Diffie-Hellman (or ECDH) operation, where the output is
distinguishable from random.
5. IANA Considerations
This document has no IANA actions.
6. References
6.1. Normative References
[FIPS203] "Module-Lattice-Based Key-Encapsulation Mechanism
Standard", NIST FIPS 203, August 2024,
<https://doi.org/10.6028/NIST.FIPS.203>.
6.2. Informative References
[EBACS] "eBACS: ECRYPT Benchmarking of Cryptographic Systems",
n.d.,
<https://bench.cr.yp.to/results-kem/amd64-hertz.html>.
Fluhrer, et al. Expires 10 April 2025 [Page 7]
Internet-Draft ML-KEM Security October 2024
[I-D.ietf-core-oscore-groupcomm]
Tiloca, M., Selander, G., Palombini, F., Mattsson, J. P.,
and R. Höglund, "Group Object Security for Constrained
RESTful Environments (Group OSCORE)", Work in Progress,
Internet-Draft, draft-ietf-core-oscore-groupcomm-23, 26
September 2024, <https://datatracker.ietf.org/doc/html/
draft-ietf-core-oscore-groupcomm-23>.
[NOISE] "Noise Protocol Framework", n.d.,
<http://www.noiseprotocol.org/>.
[RFC4253] Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH)
Transport Layer Protocol", RFC 4253, DOI 10.17487/RFC4253,
January 2006, <https://www.rfc-editor.org/rfc/rfc4253>.
[RFC5990] Randall, J., Kaliski, B., Brainard, J., and S. Turner,
"Use of the RSA-KEM Key Transport Algorithm in the
Cryptographic Message Syntax (CMS)", RFC 5990,
DOI 10.17487/RFC5990, September 2010,
<https://www.rfc-editor.org/rfc/rfc5990>.
[RFC6278] Herzog, J. and R. Khazan, "Use of Static-Static Elliptic
Curve Diffie-Hellman Key Agreement in Cryptographic
Message Syntax", RFC 6278, DOI 10.17487/RFC6278, June
2011, <https://www.rfc-editor.org/rfc/rfc6278>.
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/rfc/rfc8446>.
[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>.
[RFC9528] Selander, G., Preuß Mattsson, J., and F. Palombini,
"Ephemeral Diffie-Hellman Over COSE (EDHOC)", RFC 9528,
DOI 10.17487/RFC9528, March 2024,
<https://www.rfc-editor.org/rfc/rfc9528>.
[SIGNAL] "The Double Ratchet Algorithm", November 2011,
<https://signal.org/docs/specifications/doubleratchet/>.
[WIRE] "WireGuard", n.d., <https://www.wireguard.com/>.
Acknowledgments
Authors' Addresses
Fluhrer, et al. Expires 10 April 2025 [Page 8]
Internet-Draft ML-KEM Security October 2024
Scott Fluhrer
Cisco Systems
Email: sfluhrer@cisco.com
Quynh Dang
National Institute of Standards and Technology
Email: Quynh.Dang@nist.gov
John Preuß Mattsson
Ericsson
Email: john.mattsson@ericsson.com
Fluhrer, et al. Expires 10 April 2025 [Page 9]