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

Roberto Sassu
2025-06-13T16:49:09Z

On Fri, 2025-06-13 at 12:13 -0400, James Bottomley wrote:
> On Fri, 2025-06-13 at 15:54 +0100, David Howells wrote:
> > Hi,
> >
> > So we need to do something about the impending quantum-related
> > obsolescence of the RSA signatures that we use for module signing,
> > kexec, BPF signing, IMA and a bunch of other things.
>
> Wait, that's not necessarily the whole threat. There are two possible
> ways quantum could compromise us. One is a computer that has enough
> qbits to run the shor algorithm and break non-quantum crypto. The
> other is that a computer comes along with enough qbits to speed up the
> brute force attacks using the grover algorithm. NIST still believes
> the latter will happen way before the former, so our first step should
> be doubling the number of security bits in existing algorithms, which
> means ECC of at least 512 bits (so curve25519 needs replacing with at
> least curve448) and for all practical purposes deprecating RSA (unless
> someone wants to play with huge keys).
>
> > From my point of view, the simplest way would be to implement key
> > verification in the kernel for one (or more) of the available post-
> > quantum algorithms (of which there are at least three), driving this
> > with appropriate changes to the X.509 certificate to indicate that's
> > what we want to use.
>
> Can you at least enumerate them? There's still a dispute going on
> about whether we should use pure post-quantum or hybrid. I tend to
> think myself that hybrid is best for durable things like digital
> signatures but given the NIST advice, we should be using > 512 bit
> curves for that.
>
> > The good news is that Stephan Mueller has an implemementation that
> > includes
> > kernel bits that we can use, or, at least, adapt:
> >
> > https://github.com/smuellerDD/leancrypto/
>
> So the only hybrid scheme in there is dilithium+25519 which doesn't
> quite fit the bill (although I'm assuming dilithium+448 could easily be
> implemented)
>
> >
> > Note that we only need the signature verification bits.  One
> > question, though: he's done it as a standalone "leancrypto" module,
> > not integrated into crypto/, but should it be integrated into crypto/
> > or is the standalone fine?
> >
> > The not so good news, as I understand it, though, is that the X.509
> > bits are not yet standardised.
> >
> >
> > However!  Not everyone agrees with this.  An alternative proposal
> > would rather get the signature verification code out of the kernel
> > entirely.  Simo Sorce's proposal, for example, AIUI, is to compile
> > all the hashes we need into the kernel at build time, possibly with a
> > hashed hash list to be loaded later to reduce the amount of
> > uncompressible code in the kernel.  If signatures are needed at all,
> > then this should be offloaded to a userspace program (which would
> > also have to be hashed and marked unptraceable and I think
> > unswappable) to do the checking.
> >
> > I don't think we can dispense with signature checking entirely,
> > though: we need it for third party module loading, quick single-
> > module driver updates and all the non-module checking stuff.  If it
> > were to be done in userspace, this might entail an upcall for each
> > signature we want to check - either that, or the kernel has to run a
> > server process that it can delegate checking to.
>
> I agree we can't predict everything at build time, so we need a runtime
> scheme (like signatures) as well. However, I'm not convinced it should
> be run outside the kernel. The expansion of the TCB plus the amount of
> checking the kernel has to do to make sure the upcall is secure adds to
> the vulnerability over in-kernel where everything just works.
>
> > It's also been suggested that PQ algorithms are really slow.  For
> > kernel modules that might not matter too much as we may well not load
> > more than 200 or so during boot - but there are other users that may
> > get used more frequently (IMA, for example).
>
> If we go with a hybrid signature scheme, we can start off with only
> verifying the pre-quantum signature and have a switch to verify both.
>
> > Now, there's also a possible hybrid approach, if I understand Roberto
> > Sassu's proposal correctly, whereby it caches bundles of hashes
> > obtained from, say, the hashes included in an RPM.  These bundles of
> > hashes can be checked by signature generated by the package signing
> > process.  This would reduce the PQ overhead to checking a bundle and
> > would also make IMA's measuring easier as the hashes can be added in
> > the right order, rather than being dependent on the order that the
> > binaries are used.
>
> I think you're referring to the IMA digest list extension proposal:
>
> https://github.com/initlove/linux/wiki/IMA-Digest-Lists-Extension
>
> I'm not sure it's been progressed much.

The latest iteration can be found here:

https://lore.kernel.org/linux-integrity/20241119104922.2772571-1-roberto.sassu@huaweicloud.com/

It is more or less ready for upstreaming (from my point of view), with
the exception of a few comments that I still need to address.

The main problem was parsing the RPM headers in the kernel, that Linus
didn't like, but I believe I solved it now with Mimi's suggestion of
making the digest list parsers pluggable (so the RPM parser has been
removed from this submission, and moved to a kernel module that is
expected to be signed by distros).

I explored the alternative of moving the parser to user space, but as
you mentioned, it is a more risky approach.

Other than that, yes, it makes IMA much faster in my benchmarks (~34
seconds to lookup 12312 digests and verify 303 ECDSA signatures, as
opposed to ~98 seconds to verify 12312 ECDSA signatures).

Roberto