Understanding SSH Key Exchange Through Diffie-Hellman and Elliptic Curve Cryptography: Verifying curve25519-sha256 and Session Key Derivation in Python

Why Study SSH’s Key Exchange

This blog has already built up the math and protocol implementation of key exchange through Diffie-Hellman key exchange, elliptic curve cryptography (ECC) and ECDH, and the TLS 1.3 handshake. But there’s a protocol many engineers use even more often than TLS, and use it every single day: SSH.

Every time you type ssh user@host, a DH or ECDH key exchange runs behind the scenes and a session key gets derived. The SSH algorithm names tell the story directly: curve25519-sha256 is X25519 (ECDH), and diffie-hellman-group-exchange-sha256 is classical Safe-Prime-based DH. This post dissects SSH’s connection-setup phase in Python to verify exactly how the math we’ve already covered gets used in a real, everyday protocol.

Overview of the SSH Transport Layer and Key Exchange Phase

The SSH protocol (RFC 4253, “The Secure Shell (SSH) Transport Layer Protocol”) proceeds in this order immediately after the TCP connection is established:

Version string exchange: client and server each send an identification string of the form SSH-2.0-... (\(V_C\) , \(V_S\) ).
SSH_MSG_KEXINIT exchange: both sides send prioritized lists of the key exchange, host key, encryption, MAC, and compression algorithms they support (\(I_C\) , \(I_S\) ).
Algorithm negotiation: from those two lists, one algorithm is chosen for each category.
Key exchange (KEX): using the chosen key exchange algorithm, both sides generate an ephemeral key pair, exchange public keys, and compute the shared secret \(K\) and exchange hash \(H\) .
Session key derivation: encryption keys, IVs, and MAC keys are derived from \(K\) and \(H\) .
SSH_MSG_NEWKEYS: both sides switch to encrypted communication using the derived keys.

This post focuses on steps 2 through 5.

Algorithm Negotiation (RFC 4253 §7.1)

SSH_MSG_KEXINIT carries several name-lists (comma-separated, priority-ordered algorithm names), such as kex_algorithms, server_host_key_algorithms, and encryption_algorithms_client_to_server. RFC 4253 Section 7.1 defines the negotiation rule as follows:

The chosen encryption algorithm to each direction MUST be the first algorithm on the client’s name-list that is also on the server’s name-list.

In other words, the client’s priority order wins: the rule is “scan the client’s list from the top, and pick the first algorithm the server also supports.” The same rule applies to the key exchange algorithm itself (kex_algorithms).

RFC 4253 also defines an optimization called the “guessed” key exchange packet:

Each side MAY guess which algorithm the other side is using, and MAY send an initial key exchange packet according to the algorithm, if appropriate.

Both sides may guess that the other side is also using its own first choice, and send a key-exchange packet for that guessed algorithm right after KEXINIT — saving a round trip. If the guess turns out wrong (either the key exchange algorithm or the host key algorithm doesn’t match), the optimistically sent packet is discarded and key exchange restarts using the properly negotiated algorithm.

OpenSSH’s typical kex_algorithms priority order looks like this (it varies by version):

curve25519-sha256,curve25519-sha256@libssh.org,
ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,
diffie-hellman-group-exchange-sha256,
diffie-hellman-group16-sha512,diffie-hellman-group18-sha512

ECDH-based methods (curve25519-sha256, ecdh-sha2-*) are listed first, and classical DH (diffie-hellman-group-*) comes later — this is the modern standard configuration. As the benchmark below shows, this ordering exists precisely because curve25519 is faster than classical DH.

Mapping SSH’s Key Exchange Algorithms Onto Prior Posts

SSH’s major key exchange algorithms are, in fact, exactly the math this blog has already covered.

SSH algorithm name	Defining RFC	Mathematical foundation
`diffie-hellman-group14-sha256`, etc.	RFC 8268	DH over a finite field (Safe Prime, fixed parameters)
`diffie-hellman-group-exchange-sha256`	RFC 4419	DH over a finite field (server negotiates p, g)
`ecdh-sha2-nistp256` / `nistp384` / `nistp521`	RFC 5656	Elliptic curve ECDH (Weierstrass curves like P-256)
`curve25519-sha256`	RFC 8731	X25519 (ECDH over Curve25519)

diffie-hellman-group-exchange-sha256 (RFC 4419) is a variant of DH described in the Diffie-Hellman post: instead of a fixed Safe Prime, the client proposes a desired key size (min/preferred/max bits), and the server picks and returns a matching \((p, g)\) pair each time. curve25519-sha256 (RFC 8731), on the other hand, is simply the ECDH covered in the ECC post’s X25519 section, carried over SSH’s own key-exchange message format.

The rest of this post focuses on curve25519-sha256 — the modern de facto choice — and builds a toy implementation in Python.

The curve25519-sha256 Protocol Flow (RFC 8731)

RFC 8731 states that the SSH_MSG_KEX_ECDH_INIT / SSH_MSG_KEX_ECDH_REPLY message formats and protocol flow are “identical to Section 4 of [RFC 5656].” The flow is:

The client generates an ephemeral X25519 key pair \((x, Q_C)\) and sends the 32-byte public key \(Q_C\) to the server via SSH_MSG_KEX_ECDH_INIT.
The server generates its own ephemeral key pair \((y, Q_S)\) and computes the shared secret \(K\) from \(Q_C\) .
The server returns its host key \(K_S\) , its public key \(Q_S\) , the exchange hash \(H\) computed using \(K\) , and a signature over \(H\) , via SSH_MSG_KEX_ECDH_REPLY.
The client verifies the host key’s signature and computes the same \(K\) from its own private key \(x\) and the server’s public key \(Q_S\) .

The exchange hash \(H\) is the hash of the concatenation of the following values (RFC 8731, referencing RFC 5656 §4):

\[ H = \mathrm{hash}(V_C \,\|\, V_S \,\|\, I_C \,\|\, I_S \,\|\, K_S \,\|\, Q_C \,\|\, Q_S \,\|\, K) \tag{1} \]

For curve25519-sha256, this \(\mathrm{hash}\) is SHA-256 (RFC 8731 §3: “The hash used is SHA-256 for ‘curve25519-sha256’”). Here \(Q_C, Q_S\) are encoded as the string type within equation (1), and \(K\) — per RFC 8731 §3.1 — is derived by taking X25519’s raw output bytes (normally treated as a little-endian \(x\) -coordinate), reinterpreting them as an unsigned big-endian integer, and encoding that integer as an RFC 4251 §5 mpint.

Python Implementation: A Toy curve25519-sha256 Key Exchange

We reuse cryptography.hazmat.primitives.asymmetric.x25519 from the elliptic curve cryptography post and encode it according to SSH’s message format.

import hashlib
import struct

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey


def mpint(n: int) -> bytes:
    """RFC 4251 Section 5 mpint encoding"""
    if n == 0:
        return struct.pack(">I", 0)
    b = n.to_bytes((n.bit_length() + 7) // 8, "big")
    if b[0] & 0x80:
        b = b"\x00" + b  # prepend 0x00 to avoid colliding with the sign bit
    return struct.pack(">I", len(b)) + b


def ssh_string(b: bytes) -> bytes:
    """RFC 4251 Section 5 string encoding (4-byte length + body)"""
    return struct.pack(">I", len(b)) + b


# --- Client/server ephemeral key pairs (SSH_MSG_KEX_ECDH_INIT/REPLY) ---
client_priv = X25519PrivateKey.generate()
server_priv = X25519PrivateKey.generate()

Q_C = client_priv.public_key().public_bytes_raw()  # 32 bytes
Q_S = server_priv.public_key().public_bytes_raw()  # 32 bytes

shared_client = client_priv.exchange(server_priv.public_key())
shared_server = server_priv.exchange(client_priv.public_key())
assert shared_client == shared_server

# RFC 8731 §3.1: reinterpret raw X as a big-endian unsigned integer K, then mpint-encode
K_mpint = mpint(int.from_bytes(shared_client, "big"))

Actual output from running this:

Q_C (client public key, 32 bytes): 58d54c455205c7c27c36b4ff018c0d00a6ec7bfefcce0389e9266e76e45b2f7b
Q_S (server public key, 32 bytes): a02fc32cf1764c1b8d37c529e9822b8ccbd138704221894cfbddd928b1317852
shared secret X (raw, 32 bytes)  : 664e4fb17ccbd06cb5c907b5b39cffcddf9d45d9403d83e908cddd766ffe1c08
client/server match: True
K (mpint, 36 bytes): 00000020664e4fb17ccbd06cb5c907b5b39cffcddf9d45d9403d83e908cddd766ffe1c08

Thanks to the commutativity of X25519 scalar multiplication (the same structure as equation (8) in the ECC post’s ECDH section), client and server independently arrive at the identical shared secret.

Exchange Hash H and Session Key Derivation (RFC 4253 §7.2)

Next, we compute the exchange hash \(H\) from equation (1). In the real protocol, \(V_C, V_S\) are the version strings, \(I_C, I_S\) are the entire KEXINIT payloads, and \(K_S\) is the server’s host key — but since this post doesn’t perform an actual network exchange, these are stand-ins with fixed mock values. The goal here is to verify the correctness of the hash formula itself.

V_C = b"SSH-2.0-ToyClient_1.0"
V_S = b"SSH-2.0-ToyServer_1.0"
I_C = b"\x14" + b"\x00" * 16 + b"mock-kexinit-client-payload"
I_S = b"\x14" + b"\x00" * 16 + b"mock-kexinit-server-payload"
K_S = ssh_string(b"ssh-ed25519") + ssh_string(b"\x00" * 32)  # mock host key

hash_input = (
    ssh_string(V_C) + ssh_string(V_S) + ssh_string(I_C) + ssh_string(I_S)
    + ssh_string(K_S) + ssh_string(Q_C) + ssh_string(Q_S) + K_mpint
)
H = hashlib.sha256(hash_input).digest()  # RFC 8731: curve25519-sha256 uses SHA-256
session_id = H  # RFC 4253 §7.2: on the first key exchange, H itself becomes the session_id

Actual output:

exchange hash H (SHA-256, 32 bytes): 81349c15fe800a34c8992ce7184fad4afc2c8241f009bdcbbc13b73fd2407fe6

RFC 4253 §7.2, “Output from Key Exchange,” defines a formula for deriving six pieces of key material from the shared secret \(K\) (as mpint), the exchange hash \(H\) , and session_id (which, on the first key exchange, is simply \(H\) itself):

\[ \begin{aligned} \mathrm{IV}_{C \to S} &= \mathrm{HASH}(K \,\|\, H \,\|\, \texttt{"A"} \,\|\, \mathrm{session\_id}) \\ \mathrm{IV}_{S \to C} &= \mathrm{HASH}(K \,\|\, H \,\|\, \texttt{"B"} \,\|\, \mathrm{session\_id}) \\ \mathrm{ENC}_{C \to S} &= \mathrm{HASH}(K \,\|\, H \,\|\, \texttt{"C"} \,\|\, \mathrm{session\_id}) \\ \mathrm{ENC}_{S \to C} &= \mathrm{HASH}(K \,\|\, H \,\|\, \texttt{"D"} \,\|\, \mathrm{session\_id}) \\ \mathrm{MAC}_{C \to S} &= \mathrm{HASH}(K \,\|\, H \,\|\, \texttt{"E"} \,\|\, \mathrm{session\_id}) \\ \mathrm{MAC}_{S \to C} &= \mathrm{HASH}(K \,\|\, H \,\|\, \texttt{"F"} \,\|\, \mathrm{session\_id}) \end{aligned} \tag{2} \]

If more key material is needed than a single hash output provides, RFC 4253 §7.2 also defines a key-stretching procedure:

\[ K_1 = \mathrm{HASH}(K\|H\|X\|\mathrm{session\_id}), \quad K_2 = \mathrm{HASH}(K\|H\|K_1), \quad K_3 = \mathrm{HASH}(K\|H\|K_1\|K_2), \ \ldots \tag{3} \]

\(K_1 \| K_2 \| K_3 \| \cdots\) are concatenated until enough bytes are produced, then truncated to the needed length. This is fundamentally the same idea as the iterated-hash structure of HKDF-Expand covered in the TLS 1.3 post — though SSH’s version is a plain concatenated HASH, not an HMAC-based HKDF.

We implement equation (2) in Python, with HASH = SHA-256 since we’re using curve25519-sha256.

def derive(letter: bytes) -> bytes:
    return hashlib.sha256(K_mpint + H + letter + session_id).digest()

iv_c2s = derive(b"A")
iv_s2c = derive(b"B")
enc_c2s = derive(b"C")
enc_s2c = derive(b"D")
mac_c2s = derive(b"E")
mac_s2c = derive(b"F")

Actual output:

Initial IV (client->server)           : fdd055ef7c5cfc89afd1a1ff08e436489136ae03d6c64a166c5c7d8f5b13d897
Initial IV (server->client)           : 1e10f9fa7428f316f8746c98febb0d0bca035bcfccb16dfc308527ad59745f3f
Encryption key (client->server)       : 17c292253737c9caa6f29000c397ea4a30156ab7706b8191ae719e13adf50ecb
Encryption key (server->client)       : 5b3f39417d643b8062594f2fdb8ec86f1d1451038f679c26d7a1a96ae1a72db9
Integrity key (client->server)        : c1d9231d590e790799c1d4e0762d14881135c8cf6f0666d879fa8b91a7e63c18
Integrity key (server->client)        : cea5a0c4b6d43937e5c1787aa36fb78338a7cd7a9afe1104cc9e250d504a6d8b

independent client/server derivation match: True

We confirmed that when the server independently runs the same procedure from shared_server, the resulting encryption key (ENC_{C→S}) matches exactly. Once the shared secret \(K\) and exchange hash \(H\) agree, both parties can derive all six keys with no further communication — this is exactly the practical payoff of DH/ECDH-based key agreement.

Benchmark: X25519 vs. DH Group Exchange (2048/3072 bit)

There’s a measurable performance reason why curve25519-sha256 outranks diffie-hellman-group-exchange-sha256 in SSH’s default algorithm priority list. Using cryptography.hazmat, we measured the actual time taken for key generation (generate_private_key) and key exchange (exchange) for both X25519 and FFDHE (equivalent to the RFC 7919 standard 2048/3072-bit parameters).

import time
from cryptography.hazmat.primitives.asymmetric import dh
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey

N = 200
t0 = time.perf_counter()
keys = [X25519PrivateKey.generate() for _ in range(N)]
t1 = time.perf_counter()
x25519_keygen_ms = (t1 - t0) / N * 1000
# ... key exchange timed the same way with time.perf_counter()

for bits in (2048, 3072):
    params = dh.generate_parameters(generator=2, key_size=bits)
    N_dh = 20
    t0 = time.perf_counter()
    dh_keys = [params.generate_private_key() for _ in range(N_dh)]
    t1 = time.perf_counter()
    dh_keygen_ms = (t1 - t0) / N_dh * 1000
    # ... key exchange timed the same way

Measured results (Python 3.x, cryptography 49.0.0; X25519 averaged over N=200 runs, DH over N=20 runs):

Algorithm	Key generation [ms/op]	Key exchange [ms/op]	Total [ms/op]
X25519	0.090	0.160	0.250
DH 2048 bit	2.630	2.639	5.268
DH 3072 bit	7.964	7.905	15.869

X25519 came out about 21.0x faster than DH 2048 bit and about 63.4x faster than DH 3072 bit.

SSH key exchange algorithm benchmark: X25519 vs FFDHE (2048/3072 bit)

DH group exchange requires computing \(g^a \bmod p\) — a modular exponentiation over a large modulus — and the computational cost grows as the key length increases (as discussed in the DH post, even with the binary exponentiation method, 2048-bit and 3072-bit integer arithmetic is inherently expensive). X25519, by contrast, completes with a fixed-length ~255-bit scalar multiplication. The ECC advantage discussed in the elliptic curve cryptography post — “equivalent security at a much shorter key length” — shows up directly as a speed advantage here. For ephemeral key exchange protocols like SSH and TLS, which generate a fresh key pair on every handshake, this speed difference translates directly into connection-setup time, which is exactly why curve25519 is prioritized.

Summary

SSH’s key exchange begins with algorithm negotiation via KEXINIT (RFC 4253 §7.1, client-priority first-match rule), then proceeds through key exchange to session key derivation.
curve25519-sha256 (RFC 8731) is X25519 (ECDH), and diffie-hellman-group-exchange-sha256 (RFC 4419) is a variant of classical Safe-Prime-based DH.
We implemented the exchange hash \(H = \mathrm{hash}(V_C \| V_S \| I_C \| I_S \| K_S \| Q_C \| Q_S \| K)\) and the session key formula \(\mathrm{HASH}(K \| H \| X \| \mathrm{session\_id})\) (RFC 4253 §7.2) in Python and confirmed that client and server independently arrive at identical keys.
The measured benchmark showed X25519 is roughly 21x faster than DH 2048 bit and roughly 63x faster than DH 3072 bit, giving a concrete, verified reason why SSH prioritizes curve25519 by default.

SSH isn’t “new cryptography” — it’s just one concrete implementation of the same DH/ECDH math we’ve already covered. Next, try reading this alongside the TLS 1.3 handshake post to see how the same ECDHE gets encoded into a different protocol format.

Diffie-Hellman Key Exchange: Theory and Python Implementation - The mathematical foundation of diffie-hellman-group-exchange-sha256 discussed in this post, including Safe Primes, MITM countermeasures, and the introduction of X25519.
Elliptic Curve Cryptography (ECC): Math and Python Implementation - The theoretical foundation of curve25519-sha256 discussed in this post, including the commutativity of ECDH and X25519’s clamping.
Dissecting the TLS 1.3 Handshake - A different protocol using the same X25519 ECDHE — compare its HKDF key schedule against SSH’s derivation.
Cryptography Roadmap: From DLP and Factoring to Elliptic Curves and PQC - A map of the whole cryptography learning area on this blog.

Hash Generator (DevToolBox) - For computing the SHA-256 used in session key derivation.
Base Converter (CalcBox) - For inspecting mpint-encoded byte strings in hex.

References

Ylonen, T., & Lonvick, C. (2006). “The Secure Shell (SSH) Transport Layer Protocol”. RFC 4253.
Friedl, M., Provos, N., & Simpson, W. (2006). “Diffie-Hellman Group Exchange for the Secure Shell (SSH) Transport Layer Protocol”. RFC 4419.
Stebila, D., & Green, J. (2009). “Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer”. RFC 5656.
Adamantiadis, A., Josefsson, S., & Baushke, M. (2020). “Secure Shell (SSH) Key Exchange Method Using Curve25519 and Curve448”. RFC 8731.
Baushke, M. (2017). “More Modular Exponentiation (MODP) Diffie-Hellman (DH) Key Exchange (KEX) Groups for Secure Shell (SSH)”. RFC 8268.

Why Study SSH’s Key Exchange

Overview of the SSH Transport Layer and Key Exchange Phase

Algorithm Negotiation (RFC 4253 §7.1)

Mapping SSH’s Key Exchange Algorithms Onto Prior Posts

The curve25519-sha256 Protocol Flow (RFC 8731)

Python Implementation: A Toy curve25519-sha256 Key Exchange

Exchange Hash H and Session Key Derivation (RFC 4253 §7.2)

Benchmark: X25519 vs. DH Group Exchange (2048/3072 bit)

Summary

Related Posts

Related Tools

References

この記事に関連する無料ツール

関連記事

Post-Quantum Cryptography in Python: Learning With Errors (LWE), Regev Encryption, and Why It Resists Quantum Computers

SHA-256 and HMAC in Python: The Merkle-Damgård Construction, Length-Extension Attacks, and RFC 4231 Verification

Dissecting the TLS 1.3 Handshake in Python: ECDHE, the HKDF Key Schedule, and AEAD