This document describe a widely deployed hybrid key exchange
method in the Secure Shell (SSH) protocol that is based on
Streamlined NTRU Prime sntrup761 and X25519 with SHA-512.¶
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."¶
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. 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.¶
Secure Shell (SSH) [RFC4251] is a secure
remote login protocol. The key exchange protocol described in
[RFC4253] supports an extensible set of
methods. [RFC5656] defines how
elliptic curves are integrated into this extensible SSH
framework, and [RFC8731] adds curve25519-sha256
to support the pre-quantum elliptic-curve Diffie-Hellman
X25519 function [RFC7748].¶
Streamlined NTRU Prime [NTRUPrimePQCS][NTRUPrime][NTRUPrimeWeb] provides
post-quantum small lattice-based key-encapsulation mechanisms.
The variant sntrup761 instance has been implemented widely.¶
To hedge against attacks on either of sntrup761 or X25519 a
hybrid construction may be used, with the intention that the
hybrid would be secure if either of the involved algorithms
are flawed.¶
This document describes how to implement key exchange based on
a hybrid between Streamlined NTRU Prime sntrup761 and X25519
with SHA-512 [RFC6234] in SSH.¶
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.¶
The key-agreement is done by the X25519 Diffie-Hellman
protocol as described in section 3 (Key Exchange Methods) of [RFC8731], and the key encapsulation method described
in [NTRUPrimePQCS].¶
The key exchange procedure re-use the Elliptic Curve
Diffie-Hellman (ECDH) key exchange defined in section 4 (ECDH Key Exchange) and section
7.1 (ECDH Message Numbers) of [RFC5656]. The protocol flow and the
SSH_MSG_KEX_ECDH_INIT and SSH_MSG_KEX_ECDH_REPLY messages are
identical, except that we use different ephemeral public
values Q_C and Q_S and shared secret K as described below.¶
The SSH_MSG_KEX_ECDH_INIT's value Q_C that holds the client's
ephemeral public key MUST be constructed by concatenating the
1158 byte public key output from the key generator of
sntrup761 with the 32 byte K_A = X25519(a, 9) as described in
[NTRUPrimePQCS] and [RFC8731].
The Q_C value is thus 1190 bytes.¶
The SSH_MSG_KEX_ECDH_REPLY's value Q_S that holds the server's
ephemeral public key MUST be constructed by concatenating the
1039 byte ciphertext output from the key encapsulation
mechanism of sntrup761 with the 32 byte K_B = X25519(b, 9) as
described in [NTRUPrimePQCS] and [RFC8731]. The Q_S value is thus 1071 bytes.¶
Clients and servers MUST abort if the length of
the received public keys Q_C or Q_S are not the expected
lengths. An abort for these purposes is defined as a
disconnect (SSH_MSG_DISCONNECT) of the session and
SHOULD use the
SSH_DISCONNECT_KEY_EXCHANGE_FAILED reason for the message, see
section 11.1 (Disconnection Message) of [RFC4253]. No further validation is required
beyond what is described in [RFC7748], [RFC8731] and [NTRUPrimePQCS].¶
The SSH_MSG_KEX_ECDH_REPLY's signature value is computed as
described in [RFC5656] with the following
changes. Instead of encoding the shared secret K as 'mpint',
it MUST be encoded as 'string'. The shared secret K value
MUST be the 64-byte output octet string of the SHA-512 hash
computed with the input as the 32-byte octet string key output
from the key encapsulation mechanism of sntrup761 concatenated
with the 32-byte octet string of X25519(a, X25519(b, 9)) =
X25519(b, X25519(a, 9)).¶
Jan Mojzis added "sntrup4591761x25519-sha512@tinyssh.org" to
TinySSH [TinySSH] in 2018 and Markus
Friedl implemented it for OpenSSH [OpenSSH] during 2019. During 2020
Damien Miller replaced sntrup4591761 with sntrup761 in
OpenSSH, to create "sntrup761x25519-sha512@openssh.com".
TinySSH added support for it during 2021. It became the
default key exchange algorithm in OpenSSH during 2022. That
is identical to the "sntrup761x25519-sha512" mechanism
described in this document.¶
We wish to thank the following people who contributed to this
document: Roman Danyliw, Loganaden Velvindron, Panos
Kampanakis, Mark Baushke, and Theo de Raadt.¶
Streamlined NTRU Prime sntrup761 is aiming for the standard
goal of IND-CCA2 security, is widely implemented with good
performance on a wide range of architectures, and has been
studied by researchers for several years. However new
cryptographic primitives should be introduced and trusted
conservatively, and new research findings may be published at
any time that may warrant implementation reconsiderations.
The method described here to combine Curve25519 with sntrup761
(i.e., SHA-512 hashing the concatenated outputs) is also
available for the same kind of cryptographic scrutiny.¶
The increase in communication size and computational
requirements may be a concern for restricted computational
devices, which would then not be able to take advantage of the
improved security properties offered by this work.¶
Since sntrup761x25519-sha512 is expected to offer no reduction
of security compared to curve25519-sha256, it is RECOMMENDED
that it is used and preferred whenever curve25519-sha256 is
used today, when the extra communication size and
computational requirements are acceptable.¶
As discussed in the security considerations of
Curve25519-sha256 [RFC8731], the X25519 shared
secret K is used bignum-encoded in that document, and this
raise a potential for a hash-processing time side-channel that
could leak one bit of the secret due to different length of
the bignum sign pad. This document resolve that problem by
using string-encoding instead of bignum-encoding.¶
IANA is requested to add a new "Method Name" of
"sntrup761x25519-sha512" to the "Key Exchange Method Names"
registry for Secure Shell (SSH) Protocol Parameters [IANA-KEX] with a "reference" field to this
RFC and the "OK to implement" field of "MUST".¶
Bernstein, D.J., Brumley, B. B., Chen,, M., Chuengsatiansup, C., Lange, T., Marotzke, A., Peng, B., Tuveri, N., Vredendaal, C. V., and B. Yang, "NTRU Prime: round 3", WWW https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf, .
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/info/rfc2119>.
[RFC4251]
Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH) Protocol Architecture", RFC 4251, DOI 10.17487/RFC4251, , <https://www.rfc-editor.org/info/rfc4251>.
[RFC4253]
Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH) Transport Layer Protocol", RFC 4253, DOI 10.17487/RFC4253, , <https://www.rfc-editor.org/info/rfc4253>.
[RFC5656]
Stebila, D. and J. Green, "Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer", RFC 5656, DOI 10.17487/RFC5656, , <https://www.rfc-editor.org/info/rfc5656>.
[RFC6234]
Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487/RFC6234, , <https://www.rfc-editor.org/info/rfc6234>.
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/info/rfc8174>.
[RFC8731]
Adamantiadis, A., Josefsson, S., and M. Baushke, "Secure Shell (SSH) Key Exchange Method Using Curve25519 and Curve448", RFC 8731, DOI 10.17487/RFC8731, , <https://www.rfc-editor.org/info/rfc8731>.