PQ/T Hybrid Key Exchange in SSH

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 25 February 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. 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

2. PQ/T Hybrid Key Exchange

       byte     SSH_MSG_KEX_HYBRID_INIT
       string   C_INIT

       byte     SSH_MSG_KEX_HYBRID_REPLY
       string   K_S, server's public host key
       string   S_REPLY
       string   the signature on the exchange hash

      #define SSH_MSG_KEX_HYBRID_INIT               30
      #define SSH_MSG_KEX_HYBRID_REPLY              31

      mlkem768nistp256-sha256
      mlkem1024nistp384-sha384
      mlkem768x25519-sha256

        K = HASH(K_PQ || K_CL)

      string V_C, client identification string (CR and LF excluded)
      string V_S, server identification string (CR and LF excluded)
      string I_C, payload of the client's SSH_MSG_KEXINIT
      string I_S, payload of the server's SSH_MSG_KEXINIT
      string K_S, server's public host key
      string C_INIT, client message octet string
      string S_REPLY, server message octet string
      string K, SSH shared secret

4. Acknowledgements

The authors want to thank Gerado Ravago from AWS for implementing the draft and finding issues. We also want to thank Damien Miller and Markus Friedl for their feedback and for bringing some of the SSH key exchange methods in this document in OpenSSH.¶

5. IANA Considerations

This memo includes requests of IANA to register new method names "mlkem768nistp256-sha256", "mlkem1024nistp384-sha384", and "mlkem768x25519-sha256" to be registered by IANA in the "Key Exchange Method Names" registry for SSH [IANA-SSH].¶

6. Security Considerations

The security considerations given in [RFC5656] and [RFC8731] also apply to the ECDH part of the P/T Hybrid key exchange schemes defined in this document.¶

The way a derived binary secret string is encoded (i.e., adding or removing zero bytes for encoding) before it is hashed may lead to a variable-length secret which raises the potential for a side-channel attack. In broad terms, when the secret is longer, the hash function may need to process more blocks internally which could determine the length of what is hashed. This could leak the most significant bit of the derived secret and/or allow detection of when the most significant bytes are zero. In some unfortunate circumstances, this has led to timing attacks, e.g. the Lucky Thirteen [LUCKY13] and Raccoon [RACCOON] attacks. In [RFC8731] and [RFC5656], the ECDH shared secrets were mpint and fixed-length integer encoded respectively which raised a potential for such side-channel attacks. This problem is addressed in this document by encoding K_PQ and K_CL as fixed-length byte arrays and K as a string. Implementations MUST use these encodings for K_PQ, K_CL, and K.¶

[NIST-SP-800-56C] and [NIST-SP-800-135] gives NIST recommendations for key derivation methods in key exchange protocols. Some PQ/T Hybrid combinations may combine the shared secret from a NIST-approved algorithm (e.g., ECDH using the nistp256/secp256r1 curve or ML-KEM) with a shared secret from a non-approved algorithm (e.g., X25519). [NIST-SP-800-56C] lists simple concatenation as an approved method for generation of a PQ/T Hybrid shared secret in which one of the constituent shared secret is from an approved method. Thus, the combination of the two shared secrets in this document is FIPS-approved assuming the ECDH curve and ML-KEM negotiated parameters are FIPS approved. [NIST-SP-800-135] also approves the key derivation used in SSH. This method is the same used in this document to derive keys from the quantum-resistant shared secret for use in SSH. Thus, the keys derived from the PQ/T Hybrid key exchange in this document are FIPS approved.¶

[PQ-PROOF] [PQ-PROOF2] contain proofs of security for PQ/T Hybrid key exchange schemes. [PQ-PROOF2] discusses how the key combination to derive K and the derivation of SSH symmetric keys in this document can be proven IND-CPA and IND-CCA2 secure with some assumptions. IND-CPA is achieved if we assume the HASH calls perform as a KDF which is a reasonable assumption. IND-CCA2 security is achieved by assuming the HASH is a random oracle which is a stronger assumption especially for hash functions like SHA-2 which permit length extension concerns. To leverage a HASH which is more suitable as a random oracle, we could use SHAKE256 or introduce HMAC-SHA-256 as proposed in options (2b) and (2c) in Appendix A. This document uses SHA2 which is ubiquitous although it makes an IND-CCA2 proof need stronger assumptions because even SSH's traditional key derivation has not been proven to be IND-CCA2. As with (EC)DH keys today, generating an ephemeral key exchange keypair for ECDH and ML-KEM is still REQUIRED per connection by this specification (IND-CPA security). Implementations also MUST NOT reuse randomness in the generation of KEM ciphertexts.¶

Appendix A. Other Combiners

Other combiners to derive K and the SSH keys were considered while working on this document. These include¶

(1)

K = K_PQ || K_CL. All SSH keys are derived from K as defined in Section 7.2 in [RFC4253].¶

(2)

All SSH keys are derived from K as defined in Section 7.2 in [RFC4253].¶

(a)

K = HASH(K_PQ, K_CL). This is the option adopted in this specification.¶

(b)

K = HMAC-HASH(K_PQ, K_CL)¶

(c)

K = HMAC-HASH(0, K_PQ || K_CL)¶

(3)

K = HKDF-HASH_Extract(0, K_PQ || K_CL). SSH keys are now derived from K using HKDF-HASH(K, H || session_id, 6*sizeof(HASH)).¶

Option (3) follows the Extract-and-Expand logic described in [NIST-SP-800-56C]. It deviates from existing SSH key derivation significantly and might be viewed as too far from the current SSH design. It probably would be a good approach for SSH to move from basic hashing everywhere to use proper KDFs with extract/expand, but that should be a separate effort.¶

We also considered combiners like the ones proposed in [I-D.josefsson-chempat] and [I-D.connolly-cfrg-xwing-kem]. [I-D.connolly-cfrg-xwing-kem] has a separate IND-CCA2 security proof. Although such combiners may be proven IND-CCA2 secure, to be IND-CCA2, the SSH key derivation would still require the assumptions laid out in [PQ-PROOF2] and discussed in Section 6.¶

Authors' Addresses