Re: Module signing and post-quantum crypto public key algorithms

[James Bottomley <James.Bottomley@HansenPartnership.com>]

On Mon, 2025-06-16 at 10:02 -0400, Simo Sorce wrote:
> On Fri, 2025-06-13 at 13:50 -0400, James Bottomley wrote:
> > I agree it's coming, but there's currently no date for post quantum
> > requirement in FIPS, which is the main driver for this.
> 
> The driver is the CNSA 2.0 document which has precise deadlines, not
> FIPS.

The NSA "hopes" that the CNSA algorithms will be in FIPS by about 2030,
yes.  However, even if you have CNSA 2.0 requirement, it still includes
several classical algorithms (it even includes RSA3072 which is, to say
the least, a bit controversial).

>  That said ML-KEM and ML-DSA can already be validated, so FIPS is
> also covered.

The main worry everyone has is that while it is believed that there's
not a quantum short cut over classical for lattice algorithms, they
haven't been studied long enough to believe there's no classical short
cut to breaking the encryption.  The only real algorithms we're sure
about are the hash based ones, so perhaps we should start with XMSS/LMS
before leaping to ML-.  Particularly for kernel uses like modules, the
finite signatures problem shouldn't be that limiting.

> > Current estimates say Shor's algorithm in "reasonable[1]" time
> > requires around a million qubits to break RSA2048, so we're still
> > several orders of magnitude off that.
> 
> Note that you are citing sources that identify needed physical qbits
> for error correction, but what IBM publishes is a roadmap for *error
> corrected* logical qbits. If they can pull that off that computer
> will already be way too uncomfortably close (you need 2n+3 error
> corrected logical qbits to break RSA).

The roadmap is based on a linear presumption of physical to logical
qbit scaling.  Since quantum error effects are usually exponential in
nature that seems optimistic ... but, hey, we should know in a couple
of years.

> > Grover's only requires just over 2,000 (which
> > is why NIST is worried about that first).
> 
> Grover can at most half the search space,

I assume you're thinking in terms of 2^n spaces, because for a search
space of size s, classical brute force takes O(s) and quantum takes
O(sqrt(s)).  So if s=2^n then quantum takes O(2^(n/2)).  Which is why
the recommendation is to double the bits of security.

>  so it is not really a concern, even with the smallest key sizes the
> search space is still 2^64 ... so it makes little sense to spend a
> lot of engineering time to find all places where doubling key size
> break things and then do a micro-migration to that. It is better to
> focus the scarce resources on the long term.

Well the CNSA 2.0 doc you cite above hedges and does a 1.5x security
bit increase, so even following it we can't do P-256, 25519 or RSA2048
we have to move to at least P-384 and X448 (even though it allows
RSA3072, I don't think we should be supporting that).  So if we're
going to have to increase key size anyway, we may as well up it to 256
bits of security.

So even if you believe quantum is slightly more imminent than the
Kazakh Gerbil invasion, we should still begin with the key size
increase.

Regards,

James