Module signing and post-quantum crypto public key algorithms

Module signing and post-quantum crypto public key algorithms

[David Howells]

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.

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.

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/

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.

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


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.

David

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

[Ignat Korchagin]

Hi David,

On Fri, Jun 13, 2025 at 3:54 PM David Howells <dhowells@redhat.com> 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.

Is it that impending? At least for now it seems people are more
concerned about quantum-safe TLS, so their communications cannot be
decrypted later. But breaking signatures of open source modules
probably only makes sense when there is an actual capability to break
RSA (or ECDSA)

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

Does it matter from a kernel perspective? As far as I remember we just
attach the "plain" signature to binary. Or is it about provisioning
the key through the keystore?

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

Can indeed work for modules, but with our limited deployment of IMA in
production with many services even with the current approach we get
some complains:
  * verification takes too long for some binaries (which were not
stripped for example)
  * just hashing the binaries over and over burns some CPU and
actually burns only 1 CPU at a time (stalling it)

We need to consider cases, for example, when a python script calls
some binaries via system(3) or similar in a tight loop. Yes, with IMA
we would verify only once, but still there are cases, when software
updates happen frequently or config management "templates" the
binaries, so they change all the time.

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

Agreed - we should have an in-kernel option

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

Yep, mentioned above.

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

This makes it somewhat similar to UEFI secure boot trusted signature
DB, where one can have either a trusted public key to verify the
signature or a direct allowlist of hashes

> David
>

Ignat

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

[David Howells]

Ignat Korchagin <ignat@cloudflare.com> wrote:

> > The not so good news, as I understand it, though, is that the X.509 bits are
> > not yet standardised.
> 
> Does it matter from a kernel perspective? As far as I remember we just
> attach the "plain" signature to binary. Or is it about provisioning
> the key through the keystore?

PKCS#7 is used for the signatures and X.509 is used to provide the public
keys.

David

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

[Simo Sorce]

Premise: this problem can't be ignored, even if you think Quantum
Computers are BS, various government regulations are pushing all
commercial entities to require PQ signatures, so we have to deal with
this problem.

On Fri, 2025-06-13 at 16:21 +0100, Ignat Korchagin wrote:
> Hi David,
> 
> On Fri, Jun 13, 2025 at 3:54 PM David Howells <dhowells@redhat.com> 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.
> 
> Is it that impending? At least for now it seems people are more
> concerned about quantum-safe TLS, so their communications cannot be
> decrypted later. But breaking signatures of open source modules
> probably only makes sense when there is an actual capability to break
> RSA (or ECDSA)

We do not know when Q-day (or Y2Q if you prefer) will strike, "never"
is still a possibility.

But, as a data point, IBM just announced a roadmap for a contraption
with 200 error corrected logic qubits.
That is substantial progress, so we cannot assume it will never happen,
the risk is too high (it is not me saying this, it is the cryptography
community consensus).

In terms of impending, what is pressing businesses at this time is the
CNSA 2.0 requirements, which wants software and firmware signatures to
transition to PQ algorithm in 2025 (yes this year) with complete phase
off of classic signatures by 2030 (it is an aggressive timeline, yes).

This is because a lot of the keys are embedded in HW (think Secure
Boot), so you can't wait until *after* you have a machine that can
generate forged signatures to protect your software update process.

A Quantum computer capable of breaking RSA == you can load any code in
a kernel that uses RSA/ECC signed modules.



> We need to consider cases, for example, when a python script calls
> some binaries via system(3) or similar in a tight loop. Yes, with IMA
> we would verify only once, but still there are cases, when software
> updates happen frequently or config management "templates" the
> binaries, so they change all the time.

In general, if you care about performance what you want to do is to
limit the amount of signatures you have to check to the bare minimum,
that is why I proposed to David the use of hashes, where you can have a
whole bundle of them and a single signature covering them all. This is
paramount for something like IMA if you want to make it usable wrt
performance.

> > 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.
> 
> Agreed - we should have an in-kernel option
> 
> > 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).
> 
> Yep, mentioned above.

Note that PQ algorithms are not all slow, but mostly signatures are
large, much larger than hashes, which is another reason to move to
storing hashes in the kernel, rather than signatures.

Where the smaller classic signatures (ECC) are 32 bytes, the smallest
produced by ML-DSA are 2420 bytes (with a public key of 1312).
For SLH-DSA the smaller signature is 7856 bytes (but hey! 32 bytes
pubic key).

The proposed FN-DSA standard has smaller signature sizes (the smallest
in the drafts is ~666B with a 897B public key, numbers are still
subject to change), yet it requires a IEEE-754 FPU to implement and is
a bit crazy, and it is generally not recommended for software
signatures.

Some algorithm is also slow (eg SLH-DSA with strong parameters), but
ML-DSA is comparable to ECC in performance.


In any case reducing the number of verification operations is a net
positive for kernel boot/operations performance so moving to hash-based
checks instead of full signature verification wherever possible just
makes general engineering sense, even if it can make loading of hash
lists slightly more complicated.

HTH,
Simo.

-- 
Simo Sorce
Distinguished Engineer
RHEL Crypto Team
Red Hat, Inc

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

[James Bottomley]

On Fri, 2025-06-13 at 13:33 -0400, Simo Sorce wrote:
> Premise: this problem can't be ignored, even if you think Quantum
> Computers are BS, various government regulations are pushing all
> commercial entities to require PQ signatures, so we have to deal with
> this problem.

I agree it's coming, but there's currently no date for post quantum
requirement in FIPS, which is the main driver for this.

> On Fri, 2025-06-13 at 16:21 +0100, Ignat Korchagin wrote:
> > Hi David,
> > 
> > On Fri, Jun 13, 2025 at 3:54 PM David Howells <dhowells@redhat.com>
> > 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.
> > 
> > Is it that impending? At least for now it seems people are more
> > concerned about quantum-safe TLS, so their communications cannot be
> > decrypted later. But breaking signatures of open source modules
> > probably only makes sense when there is an actual capability to
> > break RSA (or ECDSA)
> 
> We do not know when Q-day (or Y2Q if you prefer) will strike, "never"
> is still a possibility.
> 
> But, as a data point, IBM just announced a roadmap for a contraption
> with 200 error corrected logic qubits. That is substantial progress,
> so we cannot assume it will never happen, the risk is too high (it is
> not me saying this, it is the cryptography community consensus).

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.  Grover's only requires just over 2,000 (which
is why NIST is worried about that first).

Regards,

James

[1] you can change this by a couple of orders of magnitude depending on
how long you're willing to wait

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

[Stephan Mueller]

Am Freitag, 13. Juni 2025, 19:50:22 Mitteleuropäische Sommerzeit schrieb James 
Bottomley:

Hi James,

> On Fri, 2025-06-13 at 13:33 -0400, Simo Sorce wrote:
> > Premise: this problem can't be ignored, even if you think Quantum
> > Computers are BS, various government regulations are pushing all
> > commercial entities to require PQ signatures, so we have to deal with
> > this problem.
> 
> I agree it's coming, but there's currently no date for post quantum
> requirement in FIPS, which is the main driver for this.

Perhaps [1] should be considered if you refer to FIPS?

Further, [2] also gives a timeline.

[1] https://csrc.nist.gov/pubs/ir/8547/ipd

[2] https://www.nsa.gov/Press-Room/News-Highlights/Article/Article/3148990/
nsa-releases-future-quantum-resistant-qr-algorithm-requirements-for-national-
se/

Ciao
Stephan

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

[Simo Sorce]

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. That said ML-KEM and ML-DSA can already be validated, so FIPS is
also covered.

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

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

> 
> Regards,
> 
> James
> 
> [1] you can change this by a couple of orders of magnitude depending on
> how long you're willing to wait

-- 
Simo Sorce
Distinguished Engineer
RHEL Crypto Team
Red Hat, Inc

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

[James Bottomley]

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

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

[Simo Sorce]

On Mon, 2025-06-16 at 11:14 -0400, James Bottomley wrote:
> 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.

The only case where you can use LMS/XMSS in software is if you perform
exclusively verification, or if you perform a small number of
signatures and then immediately destroy the private key.

LMS/and XMSS absolutely cannot be used as software algorithms to
generate signatures while keeping a key around because ensuring the
status is never reused is fundamentally impossible in software. And a
single reuse in LMS/XMSS means complete breakdown of the crypto-system.

Due to the above in general implementing LMS/XMSS signature generation
in software is a *very bad idea*(TM) because people do not understand
how it can be used safely, and I would seriously discourage it.

The next option in this line of thought is SLH-DSA (which I would favor
if not for the following).

The problems with SLH-DSA are that it has rather large signatures and
is the slowest of all the algorithms and that CNSA 2.0 does not list
SLH-DSA as approved :-(

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

To be honest it does not really matter, either we'll have a workable
quantum computer or not, if we do we do, and the scaling will be rapid
enough that the difference in required bits won't really matter. I find
it very unlikely that we'll find ourselves in a situation where we'll
have a QC that can efficiently performer the Grover's algorithm with
enough bits, and yet implementing Shor's one is too hard and will take
a decade or more to reach.

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

What I believe is that we should not worry about Grover, because if we
get a workable Grover implementation that works we'll get Shor's too
which breaks clsssic algorithms entirely. Therefore we better move to
PQ algorithms and not spend time on a "small transition".

Of course we can decide to hedge *all bets* and move to a composed
signature (both a classic and a PQ one), in which case I would suggest
looking into signatures that use ML-DSA-87 + Ed448 or ML-DSA-87 + P-521
,ideally disjoint, with a kernel policy that can decide which (or both)
needs to be valid/checked so that the policy can be changed quickly via
configuration if any of the signature is broken.

This will allow for fears of Lattice not being vetted enough to be
managed as well as increasing the strength of the classic option, while
maintaining key and signature sizes manageable.

-- 
Simo Sorce
Distinguished Engineer
RHEL Crypto Team
Red Hat, Inc

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

[Stefan Berger]

On 6/16/25 1:27 PM, Simo Sorce wrote:
> 
> Of course we can decide to hedge *all bets* and move to a composed
> signature (both a classic and a PQ one), in which case I would suggest
> looking into signatures that use ML-DSA-87 + Ed448 or ML-DSA-87 + P-521
> ,ideally disjoint, with a kernel policy that can decide which (or both)
> needs to be valid/checked so that the policy can be changed quickly via
> configuration if any of the signature is broken.
> 

FYI: based on this implementation of ML-DSA-44/65/87

https://github.com/IBM/mlca/tree/main/qsc/crystals

(entry point is mlca_verify)

I created a prototype of a kernel driver for mldsa-44/65/87 that can 
verify self-signed mldsa certs created with this openssl command:

openssl \
	req \
	-x509 \
	-newkey mldsa44 \
	-keyout localhost-mldsa44.key \
	-subj /CN=localhost \
	-addext subjectAltName=DNS:localhost \
	-days 30 \
	-nodes \
	-out localhost-mldsa44.crt

(it seems to use the shake256 hash by default)

https://github.com/stefanberger/linux-ima-namespaces/commits/mldsa.06092025/

There's lots of cleanup needed, but with a test suite in user space, 
this should not be too difficult.

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

[David Howells]

Stefan Berger <stefanb@linux.ibm.com> wrote:

> On 6/16/25 1:27 PM, Simo Sorce wrote:
> > Of course we can decide to hedge *all bets* and move to a composed
> > signature (both a classic and a PQ one), in which case I would suggest
> > looking into signatures that use ML-DSA-87 + Ed448 or ML-DSA-87 + P-521
> > ,ideally disjoint, with a kernel policy that can decide which (or both)
> > needs to be valid/checked so that the policy can be changed quickly via
> > configuration if any of the signature is broken.
> 
> FYI: based on this implementation of ML-DSA-44/65/87
> 
> https://github.com/IBM/mlca/tree/main/qsc/crystals

The problem with that is that the Apache-2 licence is incompatible with GPLv2.
Now, it might be possible to persuade IBM to dual-license their code.

David

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

[Stephan Mueller]

Am Freitag, 7. November 2025, 11:03:49 Mitteleuropäische Normalzeit schrieb 
David Howells:

Hi David,

> Stefan Berger <stefanb@linux.ibm.com> wrote:
> > On 6/16/25 1:27 PM, Simo Sorce wrote:
> > > Of course we can decide to hedge *all bets* and move to a composed
> > > signature (both a classic and a PQ one), in which case I would suggest
> > > looking into signatures that use ML-DSA-87 + Ed448 or ML-DSA-87 + P-521
> > > ,ideally disjoint, with a kernel policy that can decide which (or both)
> > > needs to be valid/checked so that the policy can be changed quickly via
> > > configuration if any of the signature is broken.
> > 
> > FYI: based on this implementation of ML-DSA-44/65/87
> > 
> > https://github.com/IBM/mlca/tree/main/qsc/crystals
> 
> The problem with that is that the Apache-2 licence is incompatible with
> GPLv2. Now, it might be possible to persuade IBM to dual-license their
> code.

The code used as a basis for the current approach (leancrypto.org) offers 
hybrids with ED25519 and ED448) including the X.509/PKCS7 support.

However, please note that the X.509 specification for storing hybrid public 
keys is not yet completed and there is still some work on the draft IETF 
standard [1].

Side note: the leancrypto code base uses the Linux kernel X.509/PKCS7 parser 
code where the relevant handler functions (see [2]) could be relatively 
quickly transplanted into the kernel if needed.

[1] https://lamps-wg.github.io/draft-composite-sigs/draft-ietf-lamps-pq-composite-sigs.html

[2] https://github.com/smuellerDD/leancrypto/blob/master/asn1/src/
x509_cert_parser.c

Ciao
Stephan

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

[Stefan Berger]

On 11/7/25 5:03 AM, David Howells wrote:
> Stefan Berger <stefanb@linux.ibm.com> wrote:
> 
>> On 6/16/25 1:27 PM, Simo Sorce wrote:
>>> Of course we can decide to hedge *all bets* and move to a composed
>>> signature (both a classic and a PQ one), in which case I would suggest
>>> looking into signatures that use ML-DSA-87 + Ed448 or ML-DSA-87 + P-521
>>> ,ideally disjoint, with a kernel policy that can decide which (or both)
>>> needs to be valid/checked so that the policy can be changed quickly via
>>> configuration if any of the signature is broken.
>>
>> FYI: based on this implementation of ML-DSA-44/65/87
>>
>> https://github.com/IBM/mlca/tree/main/qsc/crystals
> 
> The problem with that is that the Apache-2 licence is incompatible with GPLv2.
> Now, it might be possible to persuade IBM to dual-license their code.

Correct. It was supposed to become GPLv2 + Apache 2.

> 
> David
> 
> 

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

[Elliott, Robert (Servers)]

> -----Original Message-----
> From: Simo Sorce <simo@redhat.com>
> Sent: Monday, June 16, 2025 12:27 PM
> Subject: Re: Module signing and post-quantum crypto public key
> algorithms
> 
...
> Of course we can decide to hedge *all bets* and move to a composed
> signature (both a classic and a PQ one), in which case I would suggest
> looking into signatures that use ML-DSA-87 + Ed448 or ML-DSA-87 + P-521
> ,ideally disjoint, with a kernel policy that can decide which (or both)
> needs to be valid/checked so that the policy can be changed quickly via
> configuration if any of the signature is broken.
> 
> This will allow for fears of Lattice not being vetted enough to be
> managed as well as increasing the strength of the classic option, while
> maintaining key and signature sizes manageable.

I like the ML-DSA-87 + Ed448 combination.

Consider signing with two signatures: traditional and composite.

The traditional signature would use whatever algorithm is used today.
Legacy verifiers would only check that.

The composite signature would use:
    ML-DSA-87 + Ed448 (+ SHAKE256 if using the CMS composite construction)

New verifiers would only check the composite signature (which requires
checking both of its parts).

That composite would be
* FIPS compliant (all the algorithms are)
* CNSA compliant (ML-DSA-87 makes it so; the rest is just noise)
* compliant with any European requirements or preferences for using hybrids
* compliant with any requirements or preferences for high security strengths
* even with two algorithms, faster than the traditional choices for signing,
  and faster than ECDSA but slower than RSASSA for verification. By bringing
  in Ed448, it might be viewed as an improvement even by PQC skeptics.

It'd be nice if signed kernel modules and packages used the same 
algorithms. Both of these define ML-DSA-87 + Ed448 composites:
* draft-ietf-lamps-pq-composite-sigs
  * id-MLDSA87-Ed448-SHAKE256 with OID: 1.3.6.1.5.5.7.6.51
* draft-ietf-openpgp-pqc
  * ML-DSA-87+Ed448 as public key algorithm ID 31

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

[David Howells]

Elliott, Robert (Servers) <elliott@hpe.com> wrote:

> The traditional signature would use whatever algorithm is used today.
> Legacy verifiers would only check that.

Would there be any legacy verifiers?  Kernel modules are generally tied to the
kernel version for which they were compiled.  Granted there are things like
the wifi regulatory stuff that are also signed.

But note also, PKCS#7 supports multiple independent signatures in a single
object.  The kernel will handle this already.  At least one signature must be
verifiable and none must be blacklisted.

I assume that the main aim of using a composite algorithm is to share the
result of the content hash - but in this case only the authenticatedAttributes
are going to be hashed for the signature, and that's relatively small.

David

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

[Elliott, Robert (Servers)]

> -----Original Message-----
> From: David Howells <dhowells@redhat.com>
> Sent: Saturday, November 8, 2025 1:47 AM
> To: Elliott, Robert (Servers) <elliott@hpe.com>
> Cc: dhowells@redhat.com; Simo Sorce <simo@redhat.com>; James Bottomley
> <James.Bottomley@HansenPartnership.com>; Ignat Korchagin
> <ignat@cloudflare.com>; Herbert Xu <herbert@gondor.apana.org.au>;
> Stephan Mueller <smueller@chronox.de>; torvalds@linux-foundation.org;
> Paul Moore <paul@paul-moore.com>; Lukas Wunner <lukas@wunner.de>;
> Clemens Lang <cllang@redhat.com>; David Bohannon <dbohanno@redhat.com>;
> Roberto Sassu <roberto.sassu@huawei.com>; keyrings@vger.kernel.org;
> linux-crypto@vger.kernel.org; linux-security-module@vger.kernel.org;
> linux-kernel@vger.kernel.org
> Subject: Re: Module signing and post-quantum crypto public key
> algorithms
> 
> Elliott, Robert (Servers) <elliott@hpe.com> wrote:
> 
> > The traditional signature would use whatever algorithm is used today.
> > Legacy verifiers would only check that.
> 
> Would there be any legacy verifiers?  Kernel modules are generally tied
> to the kernel version for which they were compiled.  Granted there are
> things like the wifi regulatory stuff that are also signed.

If the system building and signing a module doesn't have OpenSSL 3.5 yet,
it can only provide a legacy signature. If the kernel is only looking
for a composite by default, a kernel command line allowing a legacy
signature to be accepted would help the transition.

Userspace tools can check signatures, but I don't know if that is done
in any non-developer situations. I did it manually while testing x86
optimized crypto module changes a few years ago.

If and when a distro is confident there are no userspace tools, it could
stop signing with legacy signatures.

> But note also, PKCS#7 supports multiple independent signatures in a
> single object.  The kernel will handle this already.  At least one
> signature must be verifiable and none must be blacklisted.

Yes, I think that makes multiple signatures viable.

> I assume that the main aim of using a composite algorithm is to share
> the result of the content hash - but in this case only the
> authenticatedAttributes are going to be hashed for the signature, and
> that's relatively small.

The composite motivation is to provide some protection if someone
discovers a basic flaw in the PQC algorithm. If quantum computers
haven't arrived yet to break the traditional algorithm, the
composite still proves validity.

The CMS and OpenPGP constructions ensure that the signatures are
non-separable; an attacker cannot strip off the strong one and leave
the broken one. The verifier always runs both algorithms (unlike
the current OR policy with multiple signatures).

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

[Simo Sorce]

On Sun, 2025-11-09 at 19:30 +0000, Elliott, Robert (Servers) wrote:
> The composite motivation is to provide some protection if someone
> discovers a basic flaw in the PQC algorithm. If quantum computers
> haven't arrived yet to break the traditional algorithm, the
> composite still proves validity.

Given you quoted me wrt composite signatures, I'd like to make clear I
do *not* necessarily favor it.

Unlike regular software or firmware, kernel modules are generally tied
to a specific version of the kernel, therefore there is no real need
for long term resistance (unless you plan to never upgrade a kernel).

If a defect in a signing algorithm is found you can simply distribute a
new kernel with modules resigned with a different algorithm.

The problem of using composite algorithms are many:
- You need composite keys (or at least two keys, depending on the
implementation).
- You will pay a higher price in terms of CPU/time for verification for
each signature. 
- You will pay a higher price in terms of disk/ram space to store
multiple signatures.

It is generally not worth paying this price when the remediation is
easy.

-- 
Simo Sorce
Distinguished Engineer
RHEL Crypto Team
Red Hat, Inc

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

[David Howells]

Simo Sorce <simo@redhat.com> wrote:

> If a defect in a signing algorithm is found you can simply distribute a
> new kernel with modules resigned with a different algorithm.

Probably more "have to" than "can".  The cert providing the composite key for
both would have to be invalidated to stop it from being used - and invalidated
by having it added to the UEFI dbx table.

David

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

[Linus Torvalds]

On Fri, 13 Jun 2025 at 07:54, David Howells <dhowells@redhat.com> wrote:
>
> So we need to do something about the impending quantum-related obsolescence [..]

I'd suggest you worry more about the rumors that Kazakhstan is growing
a veritable army of gerbils, and giving them all ABACUSES!

What's your plan for that imminent attack vector? Because they could
be here any day.

Yes, yes, please stop using RSA and relying over-much on big prime
numbers. But let's not throw the "Post Quantum" word around as if it
was reality.

The reality of kernel security remains actual bugs - both in hardware
and in software - not some buzzword.

             Linus

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

[James Bottomley]

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.

Regards,

James

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

[Roberto Sassu]

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

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

[Stephan Mueller]

Am Freitag, 13. Juni 2025, 18:13:43 Mitteleuropäische Sommerzeit schrieb James 
Bottomley:

Hi James,

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

Dilithium-ED448 just landed. One bug to squash though.

Ciao
Stephan

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

[Eric Biggers]

On Fri, Jun 13, 2025 at 03:54:30PM +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.
> 
> 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.
> 
> 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/
> 
> 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 proper place for crypto algorithm implementations, both new and existing, is
lib/crypto/.  crypto/ should contain only the compatibility code to integrate
the algorithm implementations into the generic APIs like crypto_akcipher, *if*
it's needed.

ML-DSA a.k.a. Dilithium support is fairly low on my priority list at the moment,
so if someone really wants it soon they would need to drive that effort.

- Eric

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

[Lukas Wunner]

On Fri, Jun 13, 2025 at 03:54:30PM +0100, David Howells wrote:
> 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/

I assume Herbert will insist that any new algorithm is hardened
against side channel attacks.  Thankfully, Stephan seems to have
put some effort into that:

   "side-channel-resistant: A valgrind-based dynamic side channel
    analysis is applied to find time-variant code paths based on
    secret data."

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

Module signing isn't the only motivation to add PQC algorithms to
the kernel.  Another is SPDM, a protocol for device authentication,
measurement and secure channel setup.

The DMTF has finally published SPDM 1.4.0 on May 25th and this
revision adds support for PQC algorithms (see list on page 216):

https://www.dmtf.org/sites/default/files/standards/documents/DSP0274_1.4.0.pdf

An in-kernel implementation is being worked on by Jonathan (+cc) and me:

https://github.com/l1k/linux/commits/doe

We haven't added SPDM 1.4 support yet, but will have to eventually.
So far we only support RSA and ECDSA, because that's the baseline
mandated by the PCIe Base Specification for PCI device authentication.
I expect there'll be an ECN sooner rather than later to extend the
baseline to PQC algorithms.

Thanks,

Lukas

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

[Herbert Xu]

On Thu, Jun 19, 2025 at 02:31:40PM +0200, Lukas Wunner wrote:
>
> I assume Herbert will insist that any new algorithm is hardened
> against side channel attacks.  Thankfully, Stephan seems to have
> put some effort into that:

No I think we should instead only support public keys.  There is
no valid use-case for private keys in the kernel.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt