Post-quantum KexAlgorithms (Key Exchange) are still missing and it's increasingly preventing connections to servers

[kwinz]

Summary of the new feature / enhancement

In the latest release OpenSSH_for_Windows_9.8p2 Win32-OpenSSH-GitHub, LibreSSL 4.0.0 neither

mlkem768x25519-sha256, nor
sntrup761x25519-sha512, nor
sntrup761x25519-sha512@openssh.com (already reported as missing in #1927 3 years ago)
work!

While in this build they are not available at all, in other sane builds of OpenSSH those are even the default that the client will select first. I can't connect to more and more servers that increasingly only allow post quantum KEX.

Proposed technical implementation details (optional)

Please make sure that those KexAlgorithms are included in new builds.

[tgauth]

Thanks for opening this issue - mlkem768x25519-sha256 was added upstream in version 9.9 and we are investigating incorporating it into an upcoming release.

[mgkuhn]

The LibreSSL 4.1.0 release notes (2025-04-30) mention

Imported ML-KEM 768 and 1024 from BoringSSL (not yet public API)

so there appears to be some recent activity towards support of at least part of the first in upstream.

Or is it time to review the entire LibreSSL vs OpenSSL choice?

(Good news: the supply of cryptographically-relevant quantum computers remains very limited ...)

[djmdjm]

Hi, upstream OpenSSH developer here - OpenSSH 10.1 (due in around a month) will display warnings to users when the connection does not select a post-quantum key agreement scheme. There is more information about this change at https://openssh.com/pq.html

This means connections to Windows machines will display this warning until this project adopts a PQ KEX algorithm, which IMO is a little embarassing.

AFAIK the sntrup761x25519 KEX as a result of #2140 because MSVC doesn't support variable-length arrays needed to compile sntrup761.c. There are only a handful of VLA declarations in this file and a moderately competent developer could convert all of them to temporary heap allocations in an afternoon.

I strongly recommend investing this effort and reenabling this key agreement scheme as soon as possible.

[djmdjm]

IMO it's also very desirable to support mlkem768x25519-sha256 as this is based on the NIST standard PQ ML-KEM.

The best way to get this is to update to a more recent upstream OpenSSH, but backporting the implementation from upstream should be very easy too. The ML-KEM implementation we use (from https://github.com/cryspen/libcrux) does not require VLAs.

[djmdjm]

To make it easier, please try this patch that removes the VLAs from sntrup761.c: https://www.mindrot.org/misc/sntrup761-no-vla.diff