Post Quantum Signatures support

[simo5]

The problem
With the standardization of the new Quantum Safe algorithms from NIST and the pressure from US and international agencies to adopt Quantum Safe asymmetric cryptography it is time to consider how this will be done in RPMs.

Context
In the past, new algorithms would take years, even decades before being adopted by standard bodies, however the timelines today are compressed because there is a somewhat reasonable threat that Quantum Computers capable of breaking classic cryptography will actually be available "soon".

This means there is no time to wait for all existing OSs to grow support for QR algorithms and then have a flag day and change signature algorithms.

Moreover some of the new algorithms are pretty young and there are still some doubts on their ability to withstand cryptanalysis, therefore either double-signature or hybrid encryption schemes are being considered as the logical next step.

For RPM this means we should have the ability to produce RPMs that carry both a classic signature with the current format for backwards compatibility, and a new signature using Quantum Safe algorithms.

The Openpgp standard is evolving in IETF to make available PQ algorithms for both encryption (KEMs) and Signatures, however they are bundling these changes in a new packet level format that will require new implementations of the libraries to be able to use it. This means that even if they come up with a hybrid scheme RPM will not be able to use it and provide backwards compatibility to older Operating Systems.

Describe the solution you'd like
The RPM format should evolve to be able to carry additional signatures (more than one) so that we can approach a transition to PQ signature schemes without disrupting the ability to install or even just verify RPMs on current OSs using the current classic signature.

Describe alternatives you've considered
The alternative is to update the signature scheme to a hybrid signature, this would meet the requirement of signing with a PQ scheme but would be extremely disruptive as legacy systems would not be able to check signatures at all.

Additional context
One of the reasons why the timelines are compressed and require (IMO) to support multiple disjoint signatures is the CNSA 2.0 document: https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF
See the timeline part for adoption of Software/firmware signatures.

Other nations agencies are developing similar plans.

Note on signatures timelines
For those wondering why CNSA 2.0 has such a timeline for software signing when IETF is focusing mostly on Online encryption (to prevent "harvest now decrypt later"), my hypothesis is that the NSA, in this case, is more grounded in reality than (software/standards) developers :)

Although harvesting is definitely a big threat the NSA knows that hardware gets actually deployed and will not be changed easily until its lifetime is spent, for some devices this lifetime is measured in decades, while most consumer stuff last 3-5 years.
If your device receives software updates that are signed with classic algorithms only, the downfall of classic algorithms means anyone would be able to attack the systems by providing updates with forged signatures. This is especially problematic for firmware and OS updates as they underpin any data being managed by this hardware.

[mlschroe]

See also #189 and #1050

[pmatilai]

The signature header is a generic container, it can carry arbitrary number of items. Adding new things is basically a matter of reserving a tag number for it, so that is a non-issue. I got the impression that there's work going on to standardize around PQ in the OpenPGP realm, so I'd expect that direction to be the path of least pain.

I wouldn't know a PQS if it walked up to me on the street. So lets start with a practical question: how do you generate such a signature?

[simo5]

Well it depends at what level you are asking.
I can give you openssl commands that use oqs-provider and will let you generate keys and apply raw signatures.
But I assume you want to see a PGP command line app that will generate a PQ signature instead?
In that case we should probably ask someone like @nwalfield if sequoia already has a way (I think I've seen Justus mentioned on IETF mailing lists they did make test with PQ algorithms already).

[teythoon]

The OpenPGP working group is working on draft-openpgp-pqc. Currently, the focus is on FIPS compliance, and harmonizing KEM combiners and algorithm selection across different protocols to amortize the implementation and validation efforts across different software components.

It is true that PQC in OpenPGP will depend on a new wire format, RFC 9580 aka "v6", but Sequoia is very robust in that regard. If you go with having two OpenPGP signatures, one classical and one PQ (ML-DSA as composite, or SLH-DSA), current versions of Sequoia can gracefully ignore the PQ signature. We'd be happy to assist you with creating plausible mockups of v6 PQ signatures for RPMs test suite.

Thinking about the timeline, our v6 implementation is almost complete, and we plan to merge it later this year. I don't expect the work on draft-openpgp-pqc to conclude before that.

Adding PQC support on top is relatively straight forward, as from an OpenPGP perspective it only adds algorithms. The challenge here will be to find suitable cryptographic libraries to supplement our current cryptographic backends with, as I expect that support in the mainstream cryptographic libraries will be a little behind.

[simo5]

Cryptographic support will not be an issue, we already have support in OpenSSL via liboqs+oqs-provider and OpenSSL will natively integrate ML-KEM / ML-DSA / SLH-DSA in due time.
Nettle has a ML-KEM implementation and is receiving a ML-DSA one.

We will need two distinct signature packets to make the packages usable on older systems that do not have support for the newest v6 formats, while allowing to add PQ signatures for those that can use them.
The classic signature will need to continue using the current v4 format to attain this goal. Binding the signatures is not a goal.

SLH-DSA is attractive because the math is solid and it is less "risky", but we'll need to be flexible, and may even need to add multiple PQ signatures for wider compatibility and risk management.

[pmatilai]

Well it depends at what level you are asking.
I can give you openssl commands that use oqs-provider and will let you generate keys and apply raw signatures.
But I assume you want to see a PGP command line app that will generate a PQ signature instead?

OpenPGP command line yes, but while waiting for that to materialize I play the cat that curiosity killed and poke at openssl created raw signatures instead. Not for applying in rpm, but just to make this whole PQ affair somehow more tangible. Seeing is believing etc.

As for the rpm part: the verification machinery in rpm does support multiple signatures per package as-is, I added it as a pre-requisite for #1050 back in 2018 or so, but the part that actually creates multiple signatures in rpm was never merged, so it's been unused and could've bitrotted. The foundation is there though.

The existing RSAHEADER/DSAHEADER signatures are treated as if only one can exist, but that's just convention rather than a technical limitation. So assuming Sequoia can do OpenPGP PQS, we can add a new tag for that and add it alongside an existing RSA/DSA signature instead of replacing it. And then on package read, stash it up for verification, and voi'la, the rest is up to rpm-sequoia. Rpm only knows "verify everything" policy currently, but what makes up "everything" can be configured with the various verification macros, so you could manually disable either the "classic" or the PQ signature. And with that, I think we have a rudimentary PCS support in rpm.

[simo5]

Is there any chance we can start testing something by applying both an RSA and an ECDSA based signature? And later we replace one of them with a PQ algorithm ?

[simo5]

Or even two RSA signatures with different keys ..

[pmatilai]

It could be demoed with RSA+ECDSA signatures, yes. Perhaps counter-intuitively, two RSA signatures would be more complicated 😅

[simo5]

It would be a nice feature though, it would allow to have backup keys or slowly rotate keys.
Of course it would need to allow verification to be marked ok with a single signature verifying providing the other has a missing verification key ... fun times.