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

[Aaron Rainbolt]

On Sat, 12 Jul 2025 08:06:36 +1000 (AEST)
Damien Miller <djm at mindrot.org> wrote:

> 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.

I don't want to start a controversy over who's algorithm is better, but
I do think I should point out the second article I referenced is
actually a direct reply from DJB to the article you referenced. I just
wanted to explain why I personally would prefer SLH-DSA and am uneasy
when looking at the ML-* family of algorithms.

> 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).

Well... I've already summed up my feelings about NIST's ability to
categorize things :P but that is good to know.

> > 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.

Fair enough. Then again, SSH signatures may not last that long, but
quantum-vulnerable SSH-using distros are likely to last that long.
Debian Trixie and RHEL 10 will probably still be in (limited) use once
cryptographically relevant quantum computers exist, and without a PQ
signature scheme, it will probably be practical to MITM connections to,
or gain unauthorized access to, those machines.

Then again, being in a rush when dealing with cryptography is usually a
bad idea, and it sounds like people are already working on PQ
signature schemes, so I'm probably worrying needlessly. I am still
interested in trying to help out if I can, though being a
non-cryptographer I don't really know how I can other than maybe
testing things.

--
Aaron
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20250711/2dbfdff9/attachment.asc>