RFC 10042: Overview of Communication Sequences and Message Structure for Post-Quantum/Traditional Hybrid Key Exchange with the Module-Lattice-Based Key-Encapsulation Mechanism for Use in SSH

This article is a technical explanation and implementation example created using AI. Although the code and procedures presented are based on primary sources, the author has not verified them on actual hardware. Behavior may vary depending on the environment and version.

The Secure Shell (SSH) protocol has long utilized traditional key exchange methods such as Elliptic-Curve Diffie-Hellman (ECDH). However, if quantum computers with sufficient capability are realized in the future, the security of these conventional methods could be compromised. To address such concerns, there is an urgent need for countermeasures against “Harvest now, decrypt later” attacks, where adversaries store encrypted communications and attempt to decrypt them later using a quantum computer.

To tackle these challenges, RFC 10042 defines specifications for introducing a “Post-Quantum/Traditional (PQ/T) Hybrid key exchange” mechanism into the SSH transport layer protocol, which combines the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), a post-quantum cryptography, with traditional Elliptic-Curve Diffie-Hellman (ECDH) key exchange. Based on primary sources, this article organizes the abstract structure, message exchange, specific variant options, and shared secret generation method of this hybrid key exchange.

1. Background and Basic Concepts of Hybrid Key Exchange

Traditional SSH key exchanges have used ECDH methods (such as RFC 5656 and RFC 8731) based on the hardness of the discrete logarithm problem. In contrast, primary sources define a PQ/T hybrid key exchange that combines ML-KEM, standardized by NIST, with classical algorithms.

The security of individual key exchange schemes within the hybrid method is mutually independent. In other words, the PQ/T hybrid key exchange scheme is structured to ensure security that is at least as secure as the strongest constituent key exchange scheme.

Under the NIST framework, a KEM (Key-Encapsulation Mechanism) primarily consists of the following three algorithms:

• KeyGen() -> (pk, sk): A probabilistic algorithm that outputs a public key pk and a private key sk.

• Encaps(pk) -> (ct, ss): A probabilistic algorithm that takes a public key pk as input and outputs a ciphertext ct and a shared secret ss.

• Decaps(sk, ct) -> ss: An algorithm that takes a private key sk and a ciphertext ct as input and outputs a shared secret ss (or an error value).

The primary security requirements for KEM include indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) and indistinguishability under chosen-plaintext attack (IND-CPA). ML-KEM adopted in RFC 10042 was standardized in 2024 as FIPS 203, with three variants existing as parameters: ML-KEM-512, ML-KEM-768, and ML-KEM-1024.

2. Specifications of Communication Sequence and Message Structure

In the PQ/T hybrid key exchange, new messages are defined instead of the traditional SSH_MSG_KEXDH_INIT or SSH_MSG_KEX_ECDH_INIT.

The following is an overview of the message flow for the PQ/T hybrid key exchange performed between the client and the server.

sequenceDiagram
    participant Client as SSH Client
    participant Server as SSH Server
    Client->>Server: SSH_MSG_KEX_HYBRID_INIT (C_INIT = C_PK2 || C_PK1)
    Server->>Client: SSH_MSG_KEX_HYBRID_REPLY (K_S, S_REPLY = S_CT2 || S_PK1, Signature)

Message Sent from Client: SSH_MSG_KEX_HYBRID_INIT

Using SSH_MSG_KEX_HYBRID_INIT assigned with message number 30, the client sends the following string data.

• byte: SSH_MSG_KEX_HYBRID_INIT (30)

• string: C_INIT

Here, C_INIT is the concatenation of two ephemeral public keys, constructed as C_INIT = C_PK2 || C_PK1 (where || denotes concatenation).

• C_PK1: The ephemeral public key of the traditional classical key exchange (such as ECDH).

• C_PK2: The public key pk output from the KeyGen of the corresponding post-quantum KEM.

Message Reply from Server: SSH_MSG_KEX_HYBRID_REPLY

Using SSH_MSG_KEX_HYBRID_REPLY assigned with message number 31, the server returns the following data.

• byte: SSH_MSG_KEX_HYBRID_REPLY (31)

• string: K_S (server public host key)

• string: S_REPLY

• string: signature on exchange hash

Here, S_REPLY is constructed as S_REPLY = S_CT2 || S_PK1.

• S_PK1: The traditional ephemeral ECDH server public key.

• S_CT2: The KEM ciphertext ct generated by the server-side Encaps algorithm (encapsulating the secret against the client’s public key C_PK2).

3. Verification Processing and Security Assurance

During message transmission and reception, rigorous checks are mandatory to prevent length-targeted attacks (such as length extension attacks).

• Server-side checks: Before generating S_CT2, the server MUST confirm that the length of the received C_INIT matches the sum of the expected lengths of each public key (C_PK1 and C_PK2) under the negotiated scheme. It must also execute the encapsulation key checks defined in FIPS 203. If it fails, the connection is aborted using SSH_MSG_DISCONNECT (reason: SSH_DISCONNECT_KEY_EXCHANGE_FAILED).

• Client-side checks: Before performing decryption (decapsulation), the client must confirm that the length of S_REPLY matches the sum of the expected lengths of the traditional public key S_PK1 and the ML-KEM ciphertext S_CT2. If a length mismatch or decryption error occurs, the connection is similarly aborted with a disconnect message.

4. Specific Hybrid Schemes Defined

In RFC 10042, the following three schemes are registered with IANA as specific combinations. These are used in SSH_MSG_KEXINIT.

1. mlkem768nistp256-sha256

   • Traditional key exchange: NIST P-256 curve (ecdh-sha2-nistp256)

   • Post-quantum KEM: ML-KEM-768

   • Hash function: SHA-256

2. mlkem1024nistp384-sha384

   • Traditional key exchange: NIST P-384 curve (ecdh-sha2-nistp384)

   • Post-quantum KEM: ML-KEM-1024

   • Hash function: SHA-384

3. mlkem768x25519-sha256

   • Traditional key exchange: Curve25519 (curve25519-sha256)

   • Post-quantum KEM: ML-KEM-768

   • Hash function: SHA-256

5. Method for Deriving the Shared Secret (Shared Secret K)

In hybrid key exchange, two shared secrets are established: K_CL obtained from classical ECDH and K_PQ obtained from the post-quantum ML-KEM.

The final shared secret K is calculated as the hash value of the concatenation of these two shared secrets.

$$K = text{HASH}(K_{text{PQ}} parallel K_{text{CL}})$$

While TLS 1.3 (RFC 9954) inputs the concatenated secrets directly into the key schedule, this specification adopts an approach where they are passed through a hash function after concatenation, in accordance with SSH’s key derivation method.

Additionally, while the shared secret in traditional methods was encoded as an integer (mpint), in this specification it is treated as a fixed-length big-endian byte array (32 bytes for Curve25519 and secp256r1, 48 bytes for secp384r1).

6. Input Elements for Key Derivation and Hash Calculation (H)

The hash function $H$ of the key exchange method is obtained by calculating the hash over data concatenating the following elements:

• Client identification string V_C

• Server identification string V_S

• Client SSH_MSG_KEXINIT payload I_C

• Server SSH_MSG_KEXINIT payload I_S

• Server public host key K_S

• Client message string C_INIT

• Server message string S_REPLY

• SSH shared secret K

Based on this hash result H and the shared secret K, encryption keys are derived. Note that regarding message size, it is premised on operating within the range of the minimum supported payload length (32768 bytes or less) stipulated by the traditional SSH specification (RFC 4253).

Reference Information

• RFC 10042: Post-Quantum/Traditional Hybrid Key Exchange with the Module-Lattice-Based Key-Encapsulation Mechanism for Use in SSH