Internet-Draft PQ SSH November 2022
Kampanakis, et al. Expires 24 May 2023 [Page]
Intended Status:
P. Kampanakis
D. Stebila
University of Waterloo
T. Hansen

Post-quantum Hybrid Key Exchange in SSH


This document defines post-quantum hybrid key exchange methods based on classical ECDH key exchange and post-quantum key encapsulation schemes. These methods are defined for use in the SSH Transport Layer Protocol.

[EDNOTE: Discussion of this work is encouraged to happen on the IETF WG Mailing List or in the GitHub repository which contains the 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

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 24 May 2023.

Table of Contents

1. Introduction

Change Log [EDNOTE: Remove before publicaton. ]
* draft-kampanakis-curdle-ssh-pq-ke-00
  Initial draft replacing draft-kampanakis-curdle-pq-ssh-00

Secure Shell (SSH) RFC4251 [RFC4251] performs key establishment using key exchange methods based on (Elliptic Curve) Diffie-Hellman style schemes. SSH [RFC4252] [RFC8332] [RFC5656] [RFC8709] also defines public key authentication methods based on RSA, ECDSA, or EdDSA signature schemes. The cryptographic security of these key exchange and signature schemes relies on certain instances of the discrete logarithm and integer factorization problems being computationally infeasible to solve for adversaries.

However, if sufficiently large quantum computers become available these instances would no longer be computationally infeasible rendering the current key exchange and authentication methods in SSH insecure [I-D.hoffman-c2pq]. While large quantum computers are not available today an adversary could record the encrypted communication sent between the client and server in an SSH session and later decrypt it when sufficiently large quantum computers become available. This kind of attack is known as a "record-and-harvest" attack.

This document addresses the problem by extending the SSH Transport Layer Protocol RFC4253 [RFC4253] key exchange with post-quantum (PQ) hybrid (PQ-hybrid) key exchange methods. The security provided by each individual key exchange scheme in a PQ-hybrid key exchange method is independent. This means that the PQ-hybrid key exchange method will always be at least as secure as the most secure key exchange scheme executed as part of the exchange. [PQ-PROOF] contains proofs of security for such PQ-hybrid key exchange schemes.

In the context of the NIST Post-Quantum Cryptography Standardization Project [NIST_PQ], key exchange algorithms are formulated as key encapsulation mechanisms (KEMs), which consist of three algorithms:

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.

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

2. PQ-hybrid Key Exchange

2.1. PQ-hybrid Key Exchange Method Abstraction

This section defines the abstract structure of a PQ-hybrid key exchange method. This structure must be instantiated with two key exchange schemes. The byte, string and mpint types are to be interpreted in this document as described in RFC4251 [RFC4251].

In a PQ-hybrid key exchange, instead of SSH_MSG_KEXDH_INIT [RFC4253] or SSH_MSG_KEX_ECDH_INIT [RFC5656], the client sends

       byte SSH_MSG_HBR_INIT
       string C_INIT

where C_INIT is the concatenation of C_PK1 and C_PK2. C_PK1 and C_PK2 represent the ephemeral client public keys used for each key exchange of the PQ-hybrid mechanism. Typically, C_PK1 represents a classical (i.e., ECDH) key exchange public key. C_PK2 represents the 'pk' output of the corresponding post-quantum KEM's 'KeyGen' at the client.

Instead of SSH_MSG_KEXDH_REPLY [RFC4253] or SSH_MSG_KEX_ECDH_REPLY [RFC5656], the server sends

       byte SSH_MSG_HBR_REPLY
       string S_REPLY

where S_REPLY is the concatenation of S_PK1 and S_CT2. Typically, S_PK1 represents the ephemeral (EC)DH server public key. S_CT2 represents the ciphertext 'ct' output of the corresponding KEM's 'Encaps' algorithm generated by the server which encapsulates a secret to the client public key C_PK2.

[EDNOTE: Initially we were encoding the server and client client and server classical and post-quantum public key/ciphertext as its own string. We since switched to an encoding method which concatenates them together as a single string in the C_INIT, S_REPLY message. This method concatenates the raw values rather than the length of each value plus the value. The total length of the concatenation is still known, but the relative lengths of the individual values that were concatenated is no longer part of the representation. This assumes that the lengths of individual values are fixed once the algorithm is selected, which is the case for classical key exchange methods currently supported by SSH and all post-quantum KEMs in Round 3 of the NIST post-quantum standardization project. If that is the WG consensus we need to put a note of this in the Appendix for historical reference and expand on the concatenated string here in this section.]

C_PK1, S_PK1, C_PK2, C_CT2 are used to establish two shared secrets, K_CL and K_PQ. K_CL is the output from the classical ECDH exchange using C_PK1 and S_PK1. K_PQ is the output of the post-quantum KEM exchange using C_PK2 and C_CT2. K_CL and K_PQ are used together to generate the shared secret K according to Section 2.4.

2.2. PQ-hybrid Key Exchange Message Numbers

The message numbers 30-49 are key-exchange-specific and in a private namespace defined in [RFC4250] that may be redefined by any key exchange method [RFC4253] without requiring an IANA registration process.

The following message numbers have been defined in this document:

      #define SSH_MSG_HBR_INIT               30
      #define SSH_MSG_HBR_REPLY              31

2.3. PQ-hybrid Key Exchange Method Names

The PQ-hybrid key exchange method names defined in this document (to be used in SSH_MSG_KEXINIT [RFC4253]) are

These instantiate abstract PQ-hybrid key exchanges defined in Section 2.1.

2.3.1. defines that the classical client and server public keys C_PK1, S_PK1 belong to the Curve25519 curve [RFC7748]. Private and public keys are generated as described therein. The public keys are defined as strings of 32 bytes. The K_CL shared secret is generated from the exchanged C_PK1 and S_PK1 public keys as defined in [RFC8731] (key agreement method curve25519-sha512) with SHA-512 [nist-sha2] [RFC4634] .

The post-quantum C_PK2 or S_CT2 string from the client and server are from Kyber512. The K_PQ shared secret is decapsulated from the ciphertext S_CT2 using the client post-quantum KEM private key.

[EDNOTE: Placeholder. is experimentally following OpehSSH's experimental implementation of the method name, but this draft uses Kyber which was NIST's Round PQ KEM pick. We will update later if necessary.]

2.3.2. ecdh-nistp256-kyber-512-sha256

ecdh-nistp256-kyber-512-sha256 defines that the classical client and server public keys C_PK1, S_PK1 belong to the NIST P-256 curve [nist-sp800-186]. The private and public keys are generated as described therein. The public keys are defined as strings of 64 bytes [EDNOTE: Confirm representation ] for NIST P-256. The K_CL shared secret is generated from the exchanged C_PK1 and S_PK1 public keys as defined in [RFC5656] (key agreement method ecdh-sha2-nistp256) with SHA-256 [nist-sha2] [RFC4634] as the hash.

The post-quantum C_PK2 or S_CT2 string from the client and server are Kyber512. The K_PQ shared secret is decapsulated from the ciphertext S_CT2 using the client private key.

[EDNOTE: Placeholder. ecdh-nistp256-kyber-512-sha256 currently follows OQS OpehSSH's method names. We will update if necessary.]

2.4. Shared Secret K

The shared secret, K, is defined in [RFC4253] and [RFC5656] as an integer encoded as a multiple precision integer (mpint). The PQ-hybrid key exchange establishes two a binary strings K_CL and K_PQ by using scalar multiplication and post-quantum KEM decapsulation ('Decaps') respectively. K is the concatenation of the two shared secrets K_CL and K_PQ as

        K = K_CL || K_PQ

This is the same logic as in [I-D.ietf-tls-hybrid-design] where the classical and post-quantum exchanged secrets are concatenated and used in the key schedule.

[EDNOTE: The keys are derived following the same SSH logic (as explained in the Key Derivation Section) with some small performance overhead

        Initial IV c2s: HASH(K || H || "A" || session_id)
        Initial IV s2c: HASH(K || H || "B" || session_id)
        Encryption key c2s: HASH(K || H || "C" || session_id)
        Encryption key s2c: HASH(K || H || "D" || session_id)
        Integrity key c2s: HASH(K || H || "E" || session_id)
        Integrity key s2c: HASH(K || H || "F" || session_id)

That is option 1 key derivation which is the same as the one implemented in OpenSSH experimentally when the method is used.

Other key derivation options include (Option 2) the following SSH logic

        (2a) K = HASH(K_CL || K_PQ) or
            (2b) K = HMAC-HASH(K_PQ, K_CL) or
            (2c) K = HMAC-HASH(0, K_CL || K_PQ)
        Initial IV c2s: HASH(K || H || "A" || session_id)
        Initial IV s2c: HASH(K || H || "B" || session_id)
        Encryption key c2s: HASH(K || H || "C" || session_id)
        Encryption key s2c: HASH(K || H || "D" || session_id)
        Integrity key c2s: HASH(K || H || "E" || session_id)
        Integrity key s2c: HASH(K || H || "F" || session_id)

Option (2a) resembles (1), but is slightly faster because SSH hashes the shared key K 6 times, so the larger the K, the more compression function invocations we will need.

Or (Option 3) using the dualPRF and the Extract-and-Expand logic of TLS, NIST etc

        K = HKDF-HASH(0, K_CL || K_PQ) // Extract
        Initial IV c2s || Initial IV s2c || Encryption key c2s ||
        Encryption key s2c || Integrity key c2s ||
        Integrity key s2c =
              HKDF-HASH(K, H || session_id, 6(size(HASH) ) // Expand

Note that (2b), (2c) and (3) deviate from SSH 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 might be a separate step from this PQ-hybrid draft.

We need to decide how the keys should be derived from the hPQ-ybrid shared secret K. The options that end up not being chosen should be added in an Appendix as reference. Currently we picked option 1 to follow the logic in OpenSSH with method, but that could change later.]

The concatenated bytes are converted into K by interpreting the octets as an unsigned fixed-length integer encoded in network byte order. The mpint K is then encoded using the process described in Section 5 of [RFC4251], and the resulting bytes are fed to the key exchange method's hash function to generate encryption keys as described in [RFC4253].

2.5. Key Derivation

The derivation of encryption keys MUST be done from shared secret K according to Section 7.2 in [RFC4253] with a modification on the exchange hash H.

The PQ-hybrid key exchange hash H is the result of computing the HASH, where HASH is the hash algorithm specified in the named PQ-hybrid key exchange method name, over the concatenation of the following

      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 C_INIT, client message octet string
      string S_REPLY, server message octet string
      string K, SSH shared secret

The HASH functions used for the definitions in this specification are SHA-512 [nist-sha2] [RFC4634][EDNOTE: Keeping SHA-512 for now as OpenSSH does. Update later if necessary].

3. Message Size

An implementation adhering to [RFC4253] must be able to support packets with an uncompressed payload length of 32768 bytes or less and a total packet size of 35000 bytes or less (including 'packet_length', 'padding_length', 'payload', 'random padding', and 'mac'). These numbers represent what must be 'minimally supported' by implementations. This can present a problem when using post-quantum key exchange schemes because some post-quantum schemes can produce much larger messages than what is normally produced by existing key exchange methods defined for SSH. This document does not define any method names (Section 2.3) that cause any PQ-hybrid key exchange method related packets to exceed the minimally supported packet length. This document does not define behaviour in cases where a PQ-hybrid key exchange message cause a packet to exceed the minimally supported packet length.

4. Acknowledgements

5. IANA Considerations

This memo includes requests of IANA to register new method names "ecdh-nistp256-kyber-512-sha256", "" to be registered by IANA in the "Key Exchange Method Names" registry for SSH [IANA-SSH].

6. Security Considerations

[PQ-PROOF] contains proofs of security for such PQ-hybrid key exchange schemes.

[NIST-SP-800-56C] or [NIST-SP-800-135] give NIST recommendations for key derivation methods in key exchange protocols. Some PQ-hybrid combinations may combine the shared secret from a NIST-approved algorithm (e.g., ECDH using the nistp256/secp256r1 curve) with a shared secret from a non-approved algorithm (e.g., post-quantum). [NIST-SP-800-56C] lists simple concatenation as an approved method for generation of a PQ-hybrid shared secret in which one of the constituent shared secret is from an approved method. [EDNOTE: Thus, the key exchange defined here is FIPS approved assuming the ECDH exchanged parameters are FIPS approved. ]

The way the derived mpint 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.

[EDNOTE: We need to decide if we want to allow variable-length secret K. RFC8731 decided not to address this potential problem due to backwards compatibility. In this spec we could do the same or say that this specification MUST only be used with algorithms which have fixed-length shared secrets (after the variant has been fixed by the algorithm identifier in the Method Names negotiation in Section 2.3. Or we could mandate variable length keys be rejected. ]

[EDNOTE: The security considerations given in [RFC5656] therefore also applies to the ECDH key exchange scheme defined in this document. Similarly for the X25519 document. PQ Algorithms are newer and standardized by NIST. We should include text about the combination method for the KEM shared secrets. ]

[EDNOTE: Discussion on whether an IND-CCA KEM is required or whether IND-CPA suffices.] Any KEM used in the manner described in this document MUST explicitly be designed to be secure in the event that the public key is re-used, such as achieving IND-CCA2 security or having a transform like the Fujisaki-Okamoto transform [FO][HHK] applied. While it is recommended that implementations avoid reuse of KEM public keys, implementations that do reuse KEM public keys MUST ensure that the number of reuses of a KEM public key abides by any bounds in the specification of the KEM or subsequent security analyses. Implementations MUST NOT reuse randomness in the generation of KEM ciphertexts.

Public keys, ciphertexts, and secrets should be constant length. This document assumes that the length of each public key, ciphertext, and shared secret is fixed once the algorithm is fixed. This is the case for all NIST Round 3 finalists and alternate candidates.

7. References

7.1. Normative References

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <>.
Ylonen, T., Lonvick, C., Ed., and RFC Publisher, "The Secure Shell (SSH) Protocol Architecture", RFC 4251, DOI 10.17487/RFC4251, , <>.
Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH) Authentication Protocol", RFC 4252, DOI 10.17487/RFC4252, , <>.
Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH) Transport Layer Protocol", RFC 4253, DOI 10.17487/RFC4253, , <>.

7.2. Informative References

Fujisaki, E. and T. Okamoto, "Secure Integration of Asymmetric and Symmetric Encryption Schemes", DOI 10.1007/s00145-011-9114-1, Journal of Cryptology Vol. 26, pp. 80-101, , <>.
Hofheinz, D., Hövelmanns, K., and E. Kiltz, "A Modular Analysis of the Fujisaki-Okamoto Transformation", DOI 10.1007/978-3-319-70500-2_12, Theory of Cryptography pp. 341-371, , <>.
Hoffman, P., "The Transition from Classical to Post-Quantum Cryptography", Work in Progress, Internet-Draft, draft-hoffman-c2pq-07, , <>.
Stebila, D., Fluhrer, S., and S. Gueron, "Hybrid key exchange in TLS 1.3", Work in Progress, Internet-Draft, draft-ietf-tls-hybrid-design-05, , <>.
IANA, "Secure Shell (SSH) Protocol Parameters", , <>.
Al Fardan, N.J. and K.G. Paterson, "Lucky Thirteen: Breaking the TLS and DTLS record protocols", , <>.
NIST, "FIPS PUB 180-4", , <>.
National Institute of Standards and Technology (NIST), "Recommendation for Existing Application-Specific Key Derivation Functions", , <>.
National Institute of Standards and Technology (NIST), "Recommendation for Key-Derivation Methods in Key-Establishment Schemes", , <>.
NIST, "SP 800-186", , <>.
NIST, "Post-Quantum Cryptography", , <>.
Campagna, M. and A. Petcher, "Security of Hybrid Key Encapsulation", , <>.
Merget, R., Brinkmann, M., Aviram, N., Somorovsky, J., Mittmann, J., and J. Schwenk, "Raccoon Attack: Finding and Exploiting Most-Significant-Bit-Oracles in TLS-DH(E)", , <>.
Lehtinen, S. and C. Lonvick, Ed., "The Secure Shell (SSH) Protocol Assigned Numbers", RFC 4250, DOI 10.17487/RFC4250, , <>.
Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms (SHA and HMAC-SHA)", RFC 4634, DOI 10.17487/RFC4634, , <>.
Stebila, D. and J. Green, "Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer", RFC 5656, DOI 10.17487/RFC5656, , <>.
Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, , <>.
Bider, D., "Use of RSA Keys with SHA-256 and SHA-512 in the Secure Shell (SSH) Protocol", RFC 8332, DOI 10.17487/RFC8332, , <>.
Harris, B. and L. Velvindron, "Ed25519 and Ed448 Public Key Algorithms for the Secure Shell (SSH) Protocol", RFC 8709, DOI 10.17487/RFC8709, , <>.
Adamantiadis, A., Josefsson, S., and M. Baushke, "Secure Shell (SSH) Key Exchange Method Using Curve25519 and Curve448", RFC 8731, DOI 10.17487/RFC8731, , <>.

Authors' Addresses

Panos Kampanakis
Douglas Stebila
University of Waterloo
Torben Hansen