liboqs
liboqs copied to clipboard
open-quantum-safe
Add Stateful Signature (XMSS and LMS)
Adds implementations of stateful signatures to liboqs for XMSS and LMS. The feature include new OQS APIs to generate key-pairs, signature generation, verification, and secret key state-management. Actual secret key storage is left up to the application.
This PR also includes an enhancement to OQS SHA2 API to allow handling updates with arbitrary length buffers.
- [ No ] Does this PR change the input/output behaviour of a cryptographic algorithm (i.e., does it change known answer test values)? (If so, a version bump will be required from x.y.z to x.(y+1).0.)
- [ Yes ] Does this PR change the list of algorithms available -- either adding, removing, or renaming? Does this PR otherwise change an API? (If so, PRs in fully supported downstream projects dependent on these, i.e., oqs-provider and OQS-OpenSSH will also need to be ready for review and merge by the time this is merged.) OQS provider support is a separate and forthcoming feature. This is separated because of the need to manage the stateful of secret keys.
TODO: Address @baentsch comments here: https://github.com/open-quantum-safe/liboqs/issues/1098#issuecomment-1836288094
Thanks very much for this gargantuan effort @ashman-p @ducnguyen-sb!
Since this is such a big PR, I'm going to review a few files at a time and occasionally leave a batch of comments. It will probably take me at least a couple of days to get through everything thoroughly. More to come next week...
This code is extremely dangerous as is.
The verification part is fine, but I urge you to make it extremely difficult to compile and have working signature generation code in liboqs.
Handling state for XMSS and LMS is integral to the security of the scheme and that is why all standards organizations recommend these schemes be implemented in Hardware only.
Only a purpose built hardware token can guarantee (hopefully!) that state is correctly managed without errors. A software implementation simply can't. Simple operation like system backup and restore will completely destroy the cryptosystem. As well as a hardware fault that causes a crash after a signature is generated but before the state can be written back to disk.
Putting XMSS/LMS signature generation out there in a software library is borderline irresponsible to be honest.
This code is extremely dangerous as is.
The verification part is fine, but I urge you to make it extremely difficult to compile and have working signature generation code in liboqs.
Handling state for XMSS and LMS is integral to the security of the scheme and that is why all standards organizations recommend these schemes be implemented in Hardware only.
Only a purpose built hardware token can guarantee (hopefully!) that state is correctly managed without errors. A software implementation simply can't. Simple operation like system backup and restore will completely destroy the cryptosystem. As well as a hardware fault that causes a crash after a signature is generated but before the state can be written back to disk.
Putting XMSS/LMS signature generation out there in a software library is borderline irresponsible to be honest.
How are developers supposed to do testing on XMSS/LMS without a software implementation of signing?
There is certainly an argument to be made for having it not compiled in by default, or not being accessible by default.
How are developers supposed to do testing on XMSS/LMS without a software implementation of signing?
There is certainly an argument to be made for having it not compiled in by default, or not being accessible by default.
To add to that, if you have suggestions on what an appropriate guard around the signing code would be, happy to hear it.
How are developers supposed to do testing on XMSS/LMS without a software implementation of signing?
Using test vectors.
There is certainly an argument to be made for having it not compiled in by default, or not being accessible by default.
Yes, and it should be hard to enable, not just an innocent configure switch, unless that switch is something like --enable-crypto-system-destroying-signature-generation-code-use-only-for-testing
Something that makes extremely clear this code should never be enabled in any production code.
This code is extremely dangerous as is.
The verification part is fine, but I urge you to make it extremely difficult to compile and have working signature generation code in liboqs.
Handling state for XMSS and LMS is integral to the security of the scheme and that is why all standards organizations recommend these schemes be implemented in Hardware only.
Only a purpose built hardware token can guarantee (hopefully!) that state is correctly managed without errors. A software implementation simply can't. Simple operation like system backup and restore will completely destroy the cryptosystem. As well as a hardware fault that causes a crash after a signature is generated but before the state can be written back to disk.
Putting XMSS/LMS signature generation out there in a software library is borderline irresponsible to be honest.
@simo5, Thanks for the comments, we agree with you that key management is paramount to security of stateful schemes. These points were discussed at the onset. The decision to move forward was based on providing space for experimentation and research. Keep in mind also that the library provides no key management features/capabilities at all. And so there is no risk as was mentioned in the above comment. Any application writer has to provide means to store and manage key states, as that is outside the boundary of the library. (There have been other comments about this feature not being usable off-the-shelf because of this reason). Your thoughts?
There is certainly an argument to be made for having it not compiled in by default, or not being accessible by default.
Yes, and it should be hard to enable, not just an innocent configure switch, unless that switch is something like
--enable-crypto-system-destroying-signature-generation-code-use-only-for-testingSomething that makes extremely clear this code should never be enabled in any production code.
Well, right now it's as simple as setting "OQS_ENABLE_SIG_STFL_XMSS" cmake define. And that is set by default. Personally I'd also prefer having this OFF by default.
Beyond your argumentation as to the secure use of this, I'm less than certain that this functionality can be used at all (at least without major headaches, e.g., callbacks to be properly implemented, status files to be juggled, mutexes set, etc.). But "security by complexity" isn't a good argument :-/
So what about the suggestion to move this to a separate OQS subproject? It anyway has a (IMO significantly different) API from liboqs (sig API), so why not split it out completely? @dstebila @ducnguyen-sb @ashman-p ? Give it a different lifecycle, maintainership, etc and see how it evolves (ease-of-use, security, uptake, etc)?
@simo5, Thanks for the comments, we agree with you that key management is paramount to security of stateful schemes. These points were discussed at the onset. The decision to move forward was based on providing space for experimentation and research. Keep in mind also that the library provides no key management features/capabilities at all. And so there is no risk as was mentioned in the above comment. Any application writer has to provide means to store and manage key states, as that is outside the boundary of the library. (There have been other comments about this feature not being usable off-the-shelf because of this reason). Your thoughts?
The fact Security Critical state is not managed at all by the implementation makes the situation worse if it is even possible.
Leaving to non-cryptographer the task of figuring out how to "hold it right" does not really change the fact this is extremely dangerous code to have available, even people that should know better have been found to ask CMVP to allow them to backup XMSS/LMS keys from FIPS certified HMSs ... which is bonkers if you think of it. Assuming the general public can use these APIs sanely is a lost bet IMHO.
Most software developers have no idea how to safely use even relatively safe APIs. This is basically a foot gun where the manufacturer declares that the safety latch is on the gun owner to implement ...
I agree with @baentsch that it is unclear whether XMSS/LMS can really be used safely.
Personally I even think these primitives should be deprecated and not be considered going forward now that we have Quantum resistant algorithms like Dilithium or SPHINCS+. The operational management challenges are just a nightmare ... the risk is not worth it.
So what about the suggestion to move this to a separate OQS subproject? It anyway has a (IMO significantly different) API from liboqs (sig API), so why not split it out completely? @dstebila @ducnguyen-sb @ashman-p ? Give it a different lifecycle, maintainership, etc and see how it evolves (ease-of-use, security, uptake, etc)?
big +1 to that
there will be very few sources of stateful signatures because to actually deploy production environments of those you have to invest a lot into dedicated hardware (making an XMSS signature system that you can depend on for the next 20 years is very non-trivial), so the usefulness of even code to do verification of stateful hashes is questionable...
Most software developers have no idea how to safely use even relatively safe APIs. This is basically a foot gun where the manufacturer declares that the safety latch is on the gun owner to implement ...
And for the latest example of that, see https://people.redhat.com/~hkario/marvin/ where basically no high level language provides a side-channel free API to do PKCS#1 v1.5 decryption. A thing that every cryptographer knew was necessary for the last 25 years.
I would hesitate to exclude signing from XMSS/LMS, let alone exclude them from liboqs entirely. The current state of liboqs is a research/prototyping library and it is recommended that it shouldn't be used in production. Being able to evaluate XMSS and LMS as quantum resistant algorithms vs the NIST candidates is going to be quite useful.
Should liboqs switch from being a research library to a production library, I would propose starting an experimental branch. This branch could include signing for both XMSS/LMS as well as NIST candidates (aka, the ones that are still under consideration rather than selected for standardization).
But until the focus changes from a research/experimental library to a production focused one, I'm ok with these algorithms living in main.
(As I understand it) the purpose of liboqs is not to provide an API to software developers or the general public, but to provide (relatively) clean and efficient implementations of purportedly quantum-safe algorithms to researchers and others who are interested in experimenting with them. In particular, the library README stipulates that liboqs in general should not be used in any production code.
That said, I have no objection to disabling the non-verify operations by default and including a special disclaimer in the documentation for the switch to enable them in CONFIGURE.md. Would this help resolve some of your concerns @simo5 @tomato42?
Having it not configured by default is definitely a decent first step.
On the research only purpose it would be nice to have clarity. This seems to be the only game in town when it comes to Open Source implementations and there is even an oqs-provider for OpenSSL, if none of this is ever meant to be used in production there should be a very large disclaimer in the readme, but there I see:
liboqs is part of the Open Quantum Safe (OQS) project led by Douglas Stebila and Michele Mosca, which aims to develop and integrate into applications quantum-safe cryptography to facilitate deployment and testing in real world contexts. In particular, OQS provides prototype integrations of liboqs into TLS and SSH, through OpenSSL and OpenSSH.
This is pretty much the definition of production applications ...
Just to be clear, I know that there is a later disclaimer in bold there, but I always read that as a "temporary" disclaimer due to the fact the library is under heavy development and algorithms are not final, not as a long term intention.
@dstebila, @baentsch, et. al., Just wanted to add a clarification from the status meeting today... The question was asked about a key difference between stateful APIs and the current stateless ones. I think my response might have left the impression that this stateful feature did nothing to manage updating the secret key state. If so, i gave the wrong impression. This implementation does update key states when needed. However, it does not provide secret key storage. And in this regard is no different than the current APIs. The current APIs do not provide secure key storage. It does not manage keys. Key management is outside the scope of this library. The new thing required by the stateful API is that a callback must be supplied, which is called when the key needs to be saved (on key/signature generation). In most cases it is always up to the application to provide a suitable means to secure secret keys. This is now a requirement for stateful APIs.
Also, the answer to how OpenSSL would support stateful schemes... it could not without modifications because there currently isn't a means for OpenSSL to supply the needed callback.
Let me know if this makes the design any clearer. Thanks.
Just to be clear, I know that there is a later disclaimer in bold there, but I always read that as a "temporary" disclaimer due to the fact the library is under heavy development and algorithms are not final, not as a long term intention.
Yes, it is our intention to move towards a production-oriented implementation as the algorithms finalize and as we can improve the quality of the code. And we are aware that people are starting to rely on it more in some cases even now. While I see @Martyrshot's perspective about us advertising it as experimental, given the direction that we're going, I think we should be thinking now about what it will look like when we get closer to removing the experimental qualifiers.
This is similar to another issue that will come up: when we have a version that we are aiming to be production-oriented, we do also still anticipate providing a space for continuing experiments with new, non-standardized algorithms. How should we organize that? Do we put all that code in the same repository and branch but just with different build configurations? Do we put the experimental code on a separate branch or a separate repository? (Those get harder to maintain.) To some extent stateful hash-based signature key generation and signing would fall into the same category.
If we were to put stateful hash-based signature key generation and signing in the same repository and branch, what would need to do in order to be reasonably safe here?
- Not compiled in by default
- Strongly worded and clear documentation
- Function names including warning words like
_hazardousor_unsafe - Build configuration variable including warning words like
_hazardousor_unsafe - Is there an option to have CMake pause and make the user agree to a "clickthrough warranty" agreeing that they understand enabling a certain configuration is risky?
- No command-line program that does these operations?
- Not make key generation and signing available in oqs-provider (@baentsch, what do you think of this?)
@ashman-p is going to take a look at what it would take in our codebase to sequester the key generation and signing operations under a separate build configuration variable.
Just to be clear, I know that there is a later disclaimer in bold there, but I always read that as a "temporary" disclaimer due to the fact the library is under heavy development and algorithms are not final, not as a long term intention.
This also is my understanding. FWIW, my personal motivation to do oqsprovider was to pave the way for OQS (or PQC in general) to be used/useful "for real" (sooner than later).
Not make key generation and signing available in oqs-provider (@baentsch, what do you think of this?)
I assume you mean "not make keygen and signing available for SHS algorithms", right, @dstebila ? Removing them completely/for all other PQC would not meet with my unlimited enthusiasm (pardon the Germanic person trying English humour).
Assuming that understanding, such approach would be possible but entail somewhat pointless work:
- Integrate the new OQS "stfl_sig" API into
oqsprovider, adding all kinds of "bookkeeping shenanigans" to enable this new data structure - Disabling calls to keygen/sign for such algorithms -- and thus, the only two calls that require step 1 -- and that I then call pointless.
What about the alternative proposal to build liboqs by default to enable SHS (stateful hashbased signatures -- XMSS/LMS) support behind the current OQS_SIG API (as discussed about a year ago)? keygen and sign of course then couldn't work (without the ability to update state/private key after sign) but data structure setup via OQS_SIG_new and OQS_SIG_verify would work, thus making oqsprovider work as suggested (not supporting SHS sign/keygen) -- pretty much automatically.
Open question of course: How to generate the (SHS) data to be verified without using keygen/sign (as is presently done for OQS SIG algs)? Are there acceptable/hardware-based tools that could provide such data?
If not, what about the idea to create a completely new (separate from oqsprovider), say insecure-shs-provider?
Such thing maybe somewhat "generated" from the oqsprovider code base by completely eliminating KEM support and replacing OQS_SIG support with OQS_STFL_SIG support. That appears to be pretty straightforward given "OQS_STFL_SIG" has been created following the "OQS_SIG" API. This provider could then be used to generate test data for the verification-only oqsprovider. And of course, we would not make binaries available for that thing.
But this proposal comes full circle and triggers a question to the statement that started the discussion:
Putting XMSS/LMS signature generation out there in a software library is borderline irresponsible to be honest.
@simo5: Do you challenge the notion of making SHS sig gen available via any software library or liboqs specifically? The former feels like a task of putting a genie back in a bottle while the latter is surely more easily achievable (admittedly I never had a genie and a bottle at hand to try the former :-).
- Not make key generation and signing available in oqs-provider (@baentsch, what do you think of this?)
I think that signature verification would be a reasonable (the only) thing for oqsprovider.
@simo5: Do you challenge the notion of making SHS sig gen available via any software library or
liboqsspecifically? The former feels like a task of putting a genie back in a bottle while the latter is surely more easily achievable (admittedly I never had a genie and a bottle at hand to try the former :-).
I can't stop random people from doing bad things of course, but good projects should take responsibility for providing safe interfaces and make it very obvious when there are dangerous things by either not implementing them, or by hiding them under compile flags that make it very clear that they are not safe to use and only for research, and are definitely not built by default.
My intent is to make very clear to anyone casually trying to use XMSS/LMS that they really shouldn't try to generate keys and signatures and manage them in software for anything but research/experimentation.
If they really want to use the code in production anyway nothing will stop them, but they should do so very consciously, and take full responsibility for putting their organization at risk.
Personally I think oqs-provider should not try to expose SHS siggen/keygen at all.
Thanks for your take @simo5 . Completely agree. So the question remaining then is how complicated we'll make it for people to activate & use SHS sign/keygen (and not activate it by default in liboqs :)
Thanks to @ashman-p for agreeing that it shall not be in oqsprovider: This makes me bring up my pretty old suggestion to first do a provider-integration using the "stateful-sig" branch before merging that branch to liboqs main: That way we could exercise the SHS liboqs APIs (in any "activation" configuration) before "committing" to them for "external"/3rd party downstream use. Personally I'd think a separate ("derived" as per the discussion above) shs-only-provider (separate branch in oqsprovider or altogether separate project?) would be the fastest way forward for that.
@ashman-p I found this work item but no way to comment on it, so allow me to do it here: It's listed as "In progress", so I wonder whether there's anything you can share? Looking at such code (e.g., the amount of changes needed) could help alleviate my usability concerns stated above. Or should this rather better be tackled as & when you have a proposal to "de-support" SHS sig&keygen? Please let me know if there'd be something you'd like me to look into.
This was to address a question ( I recall you had) about down stream users of the stateful API when we first started talking about merging to main. Incorporating the stateful API in OpenSSL via oqsprovider was a natural choice. As you know, the stateful API makes use of callbacks to refresh secret keys (after one from the pool is used). The work item in question was to have oqsprovider set that callback.
That said, while OpenSSL and oqsprovider are general purpose libraries, I don't know that stateful key and signature generation have general purpose-uses (and especially in light of standards and recommendations). However, signature verification very well could. And so that is why i support having signature verification be included oqsprovider. I would not add key and sig gen to the provider.
As far disabling key/signature generation... that is mostly done now except for handling the test code files written to test them. I will also reach out to Duc who can help me with some of the XMSS test code.
Thanks for disabling keygen/verify by default. But as XMSS/LMS are also disabled by default, it seems there's not a single CI run for these configs now... Please correct me if I'm wrong. If I'm not mistaken, please add new CI targets with activated OQS_ENABLE_SIG_STFL_XMSS, OQS_ENABLE_SIG_STFL_LMS and OQS_ENABLE_SIG_STFL_KEY_SIG_GEN both active and inactive. A local test with
OQS_ENABLE_SIG_STFL_XMSS=ONreturned 28pytestfailures.
@ashman-p I can take care of the CI config and make a PR targeting the stateful-sigs branch, if that works for you. I've been tinkering with the config a lot lately, so it should be pretty quick.
Thanks for disabling keygen/verify by default. But as XMSS/LMS are also disabled by default, it seems there's not a single CI run for these configs now... Please correct me if I'm wrong. If I'm not mistaken, please add new CI targets with activated OQS_ENABLE_SIG_STFL_XMSS, OQS_ENABLE_SIG_STFL_LMS and OQS_ENABLE_SIG_STFL_KEY_SIG_GEN both active and inactive. A local test with
OQS_ENABLE_SIG_STFL_XMSS=ONreturned 28pytestfailures.@ashman-p I can take care of the CI config and make a PR targeting the stateful-sigs branch, if that works for you. I've been tinkering with the config a lot lately, so it should be pretty quick.
@SWilson4, that would be so great. I started reading up on the CI interface and getting things installed. But I appreciate you offering and yes, I will take that help. If you set up the tests, I will work with you to flush out any errors. I will begin with the errors Micheal mentioned. I suspect that they are not actual failures but more of a presentation. For example the stateful tests were first written with the expectation that both XMSS and LMS were present. But if say LMS was disabled calls to create LMS variants would fail (and should fail) in fact all 28 variants :).
I can take care of the CI config and make a PR targeting the stateful-sigs branch
Thanks, @SWilson4 also from me (you'll use github CI, right?) and apologies @ashman-p thinking that that'd be not too much effort for you -- CI has it's quirks, indeed... Edit/add: Adding these additional tests also would be quick for me, now that I think about it: Please let me know when you'd have time, @SWilson4 : If there's other things on your plate, I'll handle by Monday or so....
I'll rebase on main to sort out the merge conflicts; looks like they're related to my recent work.
@SWilson4 , do you mind if I go ahead and rebase this branch on top of main? I'll do it sometime next week.
