Network Working Group A. Harrison
Internet-Draft Cisco
Intended status: Informational 18 February 2025
Expires: 22 August 2025
Module-Lattice Key Exchange in SSH
draft-harrison-mlkem-ssh-01
Abstract
This document defines Post-Quantum key exchange methods based on
Module-lattice post-quantum key encapsulation schemes. These methods
are defined for use in the SSH Transport Layer Protocol.
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://alharrison.github.io/ssh_mlkem_draft/draft-harrison-mlkem-
ssh.html. Status information for this document may be found at
https://datatracker.ietf.org/doc/draft-harrison-mlkem-ssh/.
Source for this draft and an issue tracker can be found at
https://github.com/alharrison/ssh_mlkem_draft.
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 22 August 2025.
Copyright Notice
Copyright (c) 2025 IETF Trust and the persons identified as the
document authors. All rights reserved.
Harrison Expires 22 August 2025 [Page 1]
Internet-Draft TODO - Abbreviation February 2025
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. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3
3. Key Exchange Method: ML-KEM . . . . . . . . . . . . . . . . . 3
3.1. ML-KEM Key Exchange Message Numbers . . . . . . . . . . . 4
3.2. ML-KEM Key Exchange Method Names . . . . . . . . . . . . 4
3.2.1. ml-kem-512-sha256 . . . . . . . . . . . . . . . . . . 4
3.2.2. ml-kem-768-sha256 . . . . . . . . . . . . . . . . . . 5
3.2.3. ml-kem-1024-sha384 . . . . . . . . . . . . . . . . . 5
4. Security Considerations . . . . . . . . . . . . . . . . . . . 5
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5
6. References . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.1. Normative References . . . . . . . . . . . . . . . . . . 5
6.2. Informative References . . . . . . . . . . . . . . . . . 6
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 6
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 6
1. Introduction
Secure Shell (SSH) [RFC4251] is a secure remote login protocol. The
key exchange protocol described in [RFC4253] supports an extensible
set of methods. The security of traditional key exchange methods
used in Secure Shell (SSH) [RFC4251] relies on the algorithms being
too computationally complex to be broken. The development of quantum
computers poses a threat to the complexity of these algorithms.
Given sufficiently powerful quantum computers, these traditional
algorithms would be vulnerable to attack.
Additionally, the threat of "harvest-now-decrypt-later" attacks could
creates a risk in the current landscape before sufficiently powerful
quantum computers are available. In this attack, the data would be
collected and decrypted by these quantum computers at a later date.
This document addresses the problem by proposing the use of post-
quantum key encapsulation mechanisms (KEMs) to extend the SSH
[RFC4253] key exchange. In the context of the [NIST_PQ], key
exchange algorithms are formulated as key encapsulation mechanisms
(KEMs), which consist of three algorithms:
Harrison Expires 22 August 2025 [Page 2]
Internet-Draft TODO - Abbreviation February 2025
* 'KeyGen() -> (pk, sk)': A probabilistic key generation algorithm,
which generates a public key 'pk' and a secret key 'sk'.
* 'Encaps(pk) -> (ct, ss)': A probabilistic encapsulation algorithm,
which takes as input a public key 'pk' and outputs a ciphertext
'ct' and shared secret 'ss'.
* 'Decaps(sk, ct) -> ss': A decapsulation algorithm, which takes as
input a secret key 'sk' and ciphertext 'ct' and outputs a shared
secret 'ss', or in some cases a distinguished error value.
The main security property for KEMs is indistinguishability under
adaptive chosen ciphertext attack (IND-CCA2), which means that shared
secret values should be indistinguishable from random strings even
given the ability to have arbitrary ciphertexts decapsulated. IND-
CCA2 corresponds to security against an active attacker, and the
public key / secret key pair can be treated as a long-term key or
reused. A weaker security notion is indistinguishability under
chosen plaintext attack (IND-CPA), which means that the shared secret
values should be indistinguishable from random strings given a copy
of the public key. IND-CPA roughly corresponds to security against a
passive attacker, and sometimes corresponds to one-time key exchange.
The post-quantum KEM discussed in this document is ML-KEM which is
based on CRYSTALS-KYBER. [FIPS203] standardized the ML-KEM scheme in
2024 with three parameter variants, ML-KEM-512, ML-KEM-768, ML-KEM-
1024. ML-KEM is a NIST approved mechanism that is believed to be
secure against an attacker with a quantum computer.
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. Key Exchange Method: ML-KEM
The client sends SSH_MSG_KEXDH_INIT [RFC4253] or
SSH_MSG_KEX_ECDH_INIT [RFC5656]. With this, the client sends the
ephemeral client public key, C_PK. C_PK represents the 'pk' output
of the post-quantum KEM's 'KeyGen' at the client.
The server sends SSH_MSG_KEXDH_REPLY [RFC4253] or
SSH_MSG_KEX_ECDH_REPLY [RFC5656]. With this, the server sends
S_REPLY which is the concatenation of S_CT and S_PK. S_PK represents
the ephemeral server public key. S_CT is the ciphertext 'ct' output
Harrison Expires 22 August 2025 [Page 3]
Internet-Draft TODO - Abbreviation February 2025
of the 'Encaps' algorithm generated by the server which encapsulates
a secret to the client public key C_PK. Before producing S_CT, the
server MUST perform the encapsulation key checks defined in
Section 6.2 of [FIPS203], and abort using a disconnect message
(SSH_MSG_DISCONNECT) with a SSH_DISCONNECT_KEY_EXCHANGE_FAILED as the
reason, if they fail.
C_PK and S_CT are used to establish the shared secret, K_PQ. K_PQ is
the post-quantum shared secret decapsulated from S_CT. Before
decapsulating, the client MUST check if the ciphertext S_CT length
matches the selected ML-KEM variant. The client MUST abort using a
disconnect message (SSH_MSG_DISCONNECT) with a
SSH_DISCONNECT_KEY_EXCHANGE_FAILED as the reason if the S_CT length
does not match the ML-KEM variant or decapsulation fails for any
other reason.
3.1. ML-KEM Key Exchange Message Numbers
When using ML-KEM as the Key Exchange Method, the following existing
namespace message numbers MAY be used:
#define SSH_MSG_KEX_ECDH_INIT 30
#define SSH_MSG_KEX_ECDH_REPLY 31
3.2. ML-KEM Key Exchange Method Names
The ML-KEM key exchange method names defined in this document (to be
used in SSH_MSG_KEXINIT [RFC4253]) are
ml-kem-512-sha256
ml-kem-768-sha256
ml-kem-1024-sha384
3.2.1. ml-kem-512-sha256
ml-kem-512-sha256 defines the ml-kem-512 C_PK public key and
ciphertext S_CT from the client and server respectively which are
encoded as octet strings. The K_PQ shared secret is decapsulated
from the ciphertext S_CT using the client post-quantum KEM private
key as defined in [FIPS203].
The HASH function used in this key exchange [RFC4253] is SHA-256
nist-sha2 [RFC6234]
Harrison Expires 22 August 2025 [Page 4]
Internet-Draft TODO - Abbreviation February 2025
3.2.2. ml-kem-768-sha256
ml-kem-768-sha256 defines the ml-kem-768 C_PK public key and
ciphertext S_CT from the client and server respectively which are
encoded as octet strings. The K_PQ shared secret is decapsulated
from the ciphertext S_CT using the client post-quantum KEM private
key as defined in [FIPS203].
The HASH function used in this key exchange [RFC4253] is SHA-256
nist-sha2 [RFC6234]
3.2.3. ml-kem-1024-sha384
ml-kem-1024-sha384 defines the ml-kem-1024 C_PK public key and
ciphertext S_CT from the client and server respectively which are
encoded as octet strings. The K_PQ shared secret is decapsulated
from the ciphertext S_CT using the client post-quantum KEM private
key as defined in [FIPS203].
The HASH function used in this key exchange [RFC4253] is SHA-384
nist-sha2 [RFC6234]
4. Security Considerations
The security of ML-KEM is based on the presumed difficulty of solving
the Module Learning With Errors (MLWE) problem, based on the
computational problems in module lattices. [FIPS203]
5. IANA Considerations
IANA is requested to register new method names "mlkem512-sha256",
"mlkem768-sha256", "mlkem1024-sha384", and to be registered by IANA
in the "Key Exchange Method Names" registry for SSH [IANA-SSH] with a
reference field to this RFC and the "OK to implement" field of "May".
6. References
6.1. 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/rfc/rfc2119>.
[RFC4251] Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH)
Protocol Architecture", RFC 4251, DOI 10.17487/RFC4251,
January 2006, <https://www.rfc-editor.org/rfc/rfc4251>.
Harrison Expires 22 August 2025 [Page 5]
Internet-Draft TODO - Abbreviation February 2025
[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>.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011,
<https://www.rfc-editor.org/rfc/rfc6234>.
[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>.
6.2. Informative References
[FIPS203] National Institute of Standards and Technology (NIST),
"Module-Lattice-based Key-Encapsulation Mechanism
Standard", FIPS PUB 203, August 2024,
<https://doi.org/10.6028/NIST.FIPS.203>.
[IANA-SSH] IANA, "Secure Shell (SSH) Protocol Parameters", 2021,
<https://www.iana.org/assignments/ssh-parameters/ssh-
parameters.xhtml>.
[RFC5656] Stebila, D. and J. Green, "Elliptic Curve Algorithm
Integration in the Secure Shell Transport Layer",
DOI 10.17487/RFC5656, December 2009,
<https://www.rfc-editor.org/info/rfc5656>.
Acknowledgments
Open Quantum Safe has an existing implementation of ML-KEM based key
encapsulation methods in all three parameter variants. Their fork of
OpenSSH (OQS-SSH) contains an implementation using these algorithms
for SSH key exchange algorithms. The authors would like thank Open
Quantum Safe for their example implementations of postquantum
algorithms.
Author's Address
Alexander Harrison
Cisco
Email: aleharri@cisco.com
Harrison Expires 22 August 2025 [Page 6]