Plans for post-quantum-secure signature algorithms for host and public key authentication?

[Damien Miller]

On Fri, 11 Jul 2025, Aaron Rainbolt wrote:

> On Sat, 12 Jul 2025 06:09:34 +1000 (AEST)
> Damien Miller <djm at mindrot.org> wrote:
> 
> > There are no concrete plans to add support for a PQ signature scheme
> > but I think that it's fairly likely we'll add support for hybrid
> > ML-DSA/ed25519 per
> > https://datatracker.ietf.org/doc/draft-sun-ssh-composite-sigs/01/
> 
> Nice. If some input is allowable, I would like to see SLH-DSA
> specifically though since as I understand it, ML-DSA is related to
> ML-KEM (Kyber), and there are concerns that Kyber's security properties
> may have been intentionally misrepresented by NIST. [1] [2]

AIUI those claims are 1) disputed (e.g. [1]), 2) are at the margins
even for ML-KEM512, 3) don't really apply to ML-KEM768, which is what
most people (inc. us) are using and 4) it's not clear the extent to
which they apply to ML-DSA.

If we adopt a ML-DSA variant then we'd pick one with a similar
security margin (i.e. probably ML-DSA-65).

> Currently
> in the documentation I'm working on, I've recommended the use of
> sntrup761x25519-sha512 over mlkem768x25519-sha256 after skimming
> through the mentioned articles.

FWIW ML-KEM is quite a bit faster and targets a higher security level
(NIST category 3) [2] to sntrup761's NIST category 2 [3].

Also, in OpenSSH at least, ML-KEM has a formally-verified
implementation (from libcrux).

> SLH-DSA I believe also has
> better-understood security properties, so it may be more reliable.

I haven't studied any of the PQ hash algorithms enough so in my
ignorance I'll generally defer to the cryptographers that will still
speak to me. Most of them are focusing their adoption efforts on
ML-DSA for general purpose protocols like SSH.

Anyway, we're not in a rush to adopt a PQ signature scheme -
there's no analogous store-now-decrypt-later situation like there is
for key agreement and the only places that SSH signatures could
plausibly last into the era of cryptographically-relevant quantum
computing are sshsig and CA signatures of certificates, and these
both have pretty tractable remediation paths.

-d

[1] https://keymaterial.net/2023/11/18/kyber512s-security-level/
[2] https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.203.pdf section 3.2
[3] https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf section 3.5