ssh: mlkem768x25519-sha256 KEX intermittently fails with "incorrect signature" (~1/512 handshakes)

[cole-christensen]

Describe the bug

mlkem768x25519-sha256 key exchange intermittently fails — about 1 in 512
handshakes (~0.2%), independent of load. Against an OpenSSH 10.x peer the
symptom is, client-side:

ssh_dispatch_run_fatal: Connection to <host> port <port>: incorrect signature   # OTP is the server
Key exchange failed                                                              # OTP is the client

curve25519-sha256 on the same daemon never fails. The cause is a fixed-width
vs. mpint octet-string mistake in ssh_transport:hybrid_common/4: the classical
X25519 shared secret is hashed via a representation that drops a genuine leading
0x00 byte ~1/512 of the time, so the two peers derive a different hybrid shared
secret → different exchange hash H → the host-key signature over H fails
verification and the handshake aborts.

Affected versions

• Present on maint and master at time of writing.
• Introduced by 95d0848c60 ("ssh: MLKEM kex ssh").
• First released in OTP-28.4; present in 28.4.x, 28.5.x, 29.0.x.

Root cause

lib/ssh/src/ssh_transport.erl:

hybrid_common(K_pq_secret, Curve, PeerPublic, MyPrivate) ->
    K_cl_secret = compute_key(ecdh, PeerPublic, MyPrivate, Curve),   %% an integer
    K_cl_secret_mpint = <<?Empint(K_cl_secret)>>,                    %% = ssh_bits:mpint/1
    K_cl_secret_mpint_trim =
        binary:part(K_cl_secret_mpint, byte_size(K_cl_secret_mpint), -?X25519_PUBLICKEY_SIZE),
    crypto:hash(sha(Curve), <<K_pq_secret/binary, K_cl_secret_mpint_trim/binary>>).

?Empint (ssh_bits:mpint/1) is a minimal-length big-endian encoding
(<<Len:32, MinimalBigEndianBytes/binary>>, with 0x00 prepended only when the
top payload bit is set). The code wants a fixed 32-byte X25519 secret; taking
the last 32 bytes of the mpint usually yields that, but not always. With S =
the 32-byte big-endian ECDH secret:

Case	S[0]	S[1]	mpint payload	total mpint	binary:part(_, size, -32)
A	01..7f	any	32	36	S ✓
B	80..ff	any	33 (00-padded)	37	S ✓
C	00	< 0x80	31	35	<<0x1f, S[1..31]>> ✗
C'	00	>= 0x80	32 (00-padded)	36	S ✓

In case C the payload is only 31 bytes, so "last 32 bytes" of the 35-byte
binary starts one byte inside the length prefix and returns 0x1f (=31) where
the real secret has 0x00.

P(case C) = P(S[0]==0x00) × P(S[1] < 0x80) = 1/256 × 128/256 = 1/512.

As more leading bytes are zero the corruption grows (by ~4 leading zeros the
whole length prefix bleeds in); at ≥5 leading zero bytes the mpint is shorter
than 32 bytes and binary:part/3 raises badarg instead of corrupting. That
path is ~2⁻⁴⁰ by chance and not reachable via a low-order point (OpenSSL rejects
those in EVP_PKEY_derive before the encoding runs), but the fix removes it too.

Reproduce (deterministic, no network)

Secret  = <<0, 1, 0:240>>,                                %% case C: MSB 0x00, next 0x01
N       = binary:decode_unsigned(Secret, big),
Mpint   = ssh_bits:mpint(N),
Buggy   = binary:part(Mpint, byte_size(Mpint), -32),      %% current hybrid_common
Correct = <<N:256>>,
io:format("buggy   = ~s~ncorrect = ~s~n",
          [binary:encode_hex(Buggy), binary:encode_hex(Correct)]),
Buggy =:= Correct.
%% buggy   = 1F01000000...00
%% correct = 0001000000...00
%% => false

A 300k-trial Monte-Carlo gives a 0.194% mismatch rate, and every mismatch
satisfies exactly S[0]==0x00 ∧ S[1] < 0x80.

Reproduce (end-to-end, vs OpenSSH 10.3p1)

A minimal :ssh.daemon/client pinned to mlkem768x25519-sha256, driven in a
loop, with the hybrid code instrumented to count how many handshakes hit case-C:

Direction	Build	case-C handshakes	failures
OTP daemon ← OpenSSH client	stock	20	20 (1:1)
OTP daemon ← OpenSSH client	fixed	45	0
OTP client → OpenSSH sshd	stock	21	21 (1:1)
OTP client → OpenSSH sshd	fixed	31	0

On stock, failures equal the case-C count and are the only failures; with the
fix, 76 case-C handshakes across both roles all succeed.

Security impact

• Not a confidentiality or integrity break. The shared secret is part of the
  signed exchange hash H; a mismatch fails host-key signature verification and
  the handshake aborts before any session keys are installed — it fails safe, no
  session forms on mismatched keys, nothing leaks.
• It is an availability / PQ-reliability defect. ~0.2% of mlkem768x25519
  handshakes fail. A KEX that intermittently fails undermines the
  harvest-now-decrypt-later protection it exists to provide: clients/tools
  configured to fall back to a classical KEX on failure would silently complete
  classical-only for those connections, and operators tend to disable the PQ KEX
  altogether to stop the failures.
• Not attacker-weaponizable. The triggering byte pattern is a property of the
  ephemeral ECDH secret, which depends on the peer's fresh random key; an
  attacker cannot bias a targeted handshake (verified over 2M handshakes: a fixed
  attacker pubkey yields the natural leading-zero distribution, no control), and
  all canonical low-order points are rejected by crypto:compute_key. Triggering
  it gains an attacker nothing beyond a failed handshake.

Fix

Encode the ECDH shared secret fixed-width instead of trimming an mpint:

K_cl_secret_fixed = <<K_cl_secret:(?X25519_PUBLICKEY_SIZE*8)/big-unsigned-integer>>,
crypto:hash(sha(Curve), <<K_pq_secret/binary, K_cl_secret_fixed/binary>>).

draft-ietf-sshm-mlkem-hybrid-kex
§2.4 specifies this encoding: the component secrets are "encoded as
fixed-length byte arrays, not as integers," by "re-encoding [the mpint] as a
fixed-size (32 bytes for Curve25519 …) byte array always big-endian" — which
the line above implements. OpenSSH's kexmlkem768x25519.c matches it (X25519
secret as a fixed-length raw octet string, ML-KEM secret first).

A canonical mpint of the same secret is 31 bytes in case C (the leading zero is
stripped) and would mismatch the peer's 32-byte field. The field is a
fixed-width 32-byte octet string.

The new encoding is byte-for-byte
identical to the old code in cases A/B/C′ — over 500k trials it changes the
result only in case C. A regression test
(ssh_algorithms_SUITE:mlkem768x25519_hybrid_secret_encoding) constructs a
case-C X25519 secret and asserts the fixed-width encoding; it fails on the old
code and passes with the fix. Full ssh_algorithms_SUITE is green (930 ok, 0
failed) with the change.

Branch/PR with the fix + regression test to follow.

Environment

• OTP 29.0.1 (ssh 6.0), built from source.
• Client/peer: OpenSSH_10.3p1, OpenSSL 3.6.2 (and OpenSSH_10.2 system sshd).

[u3s]

PR merged