1819409 - Integrate liboqs into NSS.

Status: ASSIGNED

(NSS :: Libraries, enhancement, P3)

Description

[Robert Relyea]

In preparation for post-quantum, we need to have a source of post-quantum algorithms. Implementing these algorithms are even more tricky than our traditional algorithms and we have limitted resources to through at this.

Red Hat has the same issues with all their libraries, so we decided to encourage all our libraries to converge on using liboqs internally. This allows everyone to participate in getting properly reviewed, evaluated, constant time and still optimized versions.

The algorithms in liboqs can be picked up either peicemeal, or as the whole library. Red Hat would prefer to pick up liboqs as one library, so it can be evaluated once (for FIPS) and then used by everyone. Other options include picking up liboqs implementations without the liboqs plumbing.

Comment 1

[John Schanck [:jschanck]]

I don't think we should do this. Linking against liboqs means using their implementations of AES, SHA2, SHA3, and random number generation (see: https://github.com/open-quantum-safe/liboqs/tree/main/src/common).

The parts of liboqs that we would want come from PQClean. We can cherry-pick from there if need be.

That said, there are other sources of high quality public domain implementations, including formally verified implementations, and we have the expertise on staff to evaluate those. Given the limited amount of PQ experimentation we have on our roadmap, I think it's fine for us to choose the best available implementation of each system.

Comment 2

[Robert Relyea]

Attachment: WIP: Bug 1819409 Integrate liboqs into NSS.

This is the initial patch which pulls a version of liboqs into the NSS build
environement. At this point I expect pretty rapid changes to liboqs as
NIST finalizes their design, so I opted for the easiest way to pull new
versions of this patch.

everything under lib/liboqs/src and lib/liboqs/include is generated from
liboqs.
config.mk, manifest.mn and liboqs.gyp are also generated.

fetch_liboqs is the script that facilitates pulling new versions of liboqs.
It checks out a new version of liboqs, then uses cmake to configure it. It
then copies the relevant sources from liboqs and populates the src and include
directories. It uses the cmake build environment and the various .template
files.

To get a new version of liboqs, run

./fetch_liboqs checkout

To get a the latest upstream liboqs, then

./fetch_liboqs config

To generate all the files. hg diff will then give you the difference between
the new and old versions.

Test the build with gmake nss_build_all in the nss root, and ./build.sh -c in
the nss root (be sure to test both builds). If the two builds succeed you can
check in the new version. If you have issues, you can use:

./fetch_liboqs configkeep

to see the intermediate cmake files. You can modify fetch_liboqs and/or the *.template files to fix an build issues and rerun ./fetch_liboqs configkeep before retrying your builds. Once everything is fixed and builds complete, run ./fetch_liboqs hgprep to clean up all the files you don't want to check in to hg.

./fetch_liboqs all combines the checkout, config, and hgprep command in one
shot.

For reviewing this patch, look at lib/liboqs/fetch_liboqs, lib/liboqs/Makefile lib/libosq/*.template and all the files outside of lib/liboqs.

Liboqs proper:
MIT License
Kyber:
Public Domain (https://creativecommons.org/share-your-work/public-domain/cc0/);
or Apache 2.0 License (https://www.apache.org/licenses/LICENSE-2.0.html).
Dilithium:
Public Domain (https://creativecommons.org/share-your-work/public-domain/cc0/);
or Apache 2.0 License (https://www.apache.org/licenses/LICENSE-2.0.html).
Falcon:
MIT License
SPHINCS:
CC0 (nominally public Domain).

Comment 3

[Robert Relyea]

There is a question: is CC0 and OK license to include. Everything else is pretty well known licenses (MIT, Apache 2.0). CC0 is usually used to prose content (like documentation), and usually not included in code. If we can't swallow CC0, we could drop SPHINCS from the builds. SPHINCS is envisioned to be used for code signing. It's concidered solid from a security attack point of view, but the signatures are quite large, which makes them less useful in the context of something like SSL (though possibly useful for S/MIME).

bob

Comment 4

[Robert Relyea]

Sigh, here is the issue with cherrypicking:

1. It means that we have more than one place where we can make mistakes in picking up crypto. We already have the problem of trying to pick up new evaluated versions of the algorithms we have (not how long it's taken to pickup evaluated RSA). The code I'm proposing pulls in liboqs in a semi-automated way (a script pulls it in and integrates it).
   What I'm afraid of is everyone will run out and grab some implementation, and then build off that implemenation on their own. Cherrypicking is the worst solution because it's both error prone (early implementations will almost certainly have flaws), and high maintenance (it's hard to share updates once the code is pulled in), and is multiplied by all the users (openssl, nss, gnutls, etc.). It would be better to all get our feedback to the same source. The liboqs developers are happy to get updates, and if there are new hardened implementations out there, they are almost certainly willing to pick those up.
2. From the Red Hat perspective, this issue is muliplied by N where N is at least 3. We hope that the various upstreams would agree on a single oqs library. So here's the Red Hat preference:
   2a) liboqs is just used in the library (with an option to use a system version of the library).
   2b) there is an option to use liboqs rather than any internally build provider. Ideally this could also be an option where liboqs can be built and supplied by nss (like sqlite), but it's not a full requirement.
3. I don't intend on compiling liboqs in. The goal is that liboqs will be an external library (a.la. sqlite). It could even be dlopened.
4. aes won't be exported. NSS will continue to use it's own aes. I'd actually like to push a patch upstream where the caller provides basic crypto primitives (like aes, SHA-2, sha-3, and shake) and not use the liboqs alternatives. They already do this for openssl. For now the calls would be internal to liboqs code. NSS wouldn't export a liboqs interface to the application (anymore than it exports the freebl interface). It would just be the internal implementation of the quantuam safe algorithms.

Comment 5

[Robert Relyea]

That said, there are other sources of high quality public domain implementations, including formally verified implementations, and we have
the expertise on staff to evaluate those. Given the limited amount of PQ experimentation we have on our roadmap, I think it's fine for us to
choose the best available implementation of each system.

I submit that we should use that expertise to push the best available implentation to liboqs. I spent some time evaluating the available options.
I'll attach my evaluation I did in March of last year.

Comment 6

[Robert Relyea]

Attachment: opensourcepq.pdf

Comment 7

[John Schanck [:jschanck]]

(In reply to Robert Relyea from comment #4)

1. It means that we have more than one place where we can make mistakes in picking up crypto.

For SPHINCS and Falcon, PQClean is upstream of liboqs, so cherry-picking from PQClean gives you the exact same code. The benefit is that you get to write the shims for AES, SHA2, SHA3, etc yourself, so you can avoid the headache of modifying liboqs to take externally provided implementations of those.

For CRYSTALS-Kyber and Dilithium, liboqs is pulling directly from the submission teams, but PQClean provides identical implementations as well. I'm on the CRYSTALS team, so I'm not concerned about our ability to choose implementations of those primitives.

FWIW I don't see a pressing need for the signature schemes. We don't expect to experiment with them in Firefox this year. So I don't think we should take SPHINCS, Falcon, and Dilithium yet regardless of the source.

Comment 8

[Robert Relyea]

For SPHINCS and Falcon, PQClean is upstream of liboqs, so cherry-picking from PQClean gives you the exact same code. The benefit is that you get > to write the shims for AES, SHA2, SHA3, etc yourself, so you can avoid the headache of modifying liboqs to take externally provided
implementations of those.

Unless you are automating the picking up the algorthims. There's a maintenance cost to keep up-to-date. We don't have a good track record of 'keeping up to date' with code pulled from other sources in freebl. For the PQ algorithms that will be more important because the implementations are not yet stable, and the pitfalls in PQ side channel links are even more devistating than ECC or RSA. I expect the implementations of these algorithms to get quite a few updates in the next 24 months at least. That is my main worry.

If that doesn't convince you, then I can fall back to a patch where we just include system liboqs support. My preference would be that all the upstreams participate in liboqs/pqclean developement, but I do recognize that the siren call of 'pull and fork' is pretty strong (I know we are fighting an up hill battle in all of our upstreams). From a Red Hat perspective, we're putting our eggs in the liboqs basket hoping for critical mass. For that we don't need to actually build liboqs in NSS (it's actually easier to use their own build as their own package), we just need configurable hooks in softoken. The downside of that is those hooks won't be tested if we don't have a compiled version of liboqs.

As for signatures, Red Hat needs signature schemes in the next year (and we'll need stateful signature verification in even faster). Kyber is the priority, of course, and I'm looking forward to the kyber patches coming down the pike. But signatures are also something that will need some higher level changes (actually there are some higher level changes needed to move to integrated hash and sign mechanism in PKCS #11. The PQ are all integrated hash and sign).
bob

Comment 9

[John Schanck [:jschanck]]

Unless you are automating the picking up the algorthims. There's a maintenance cost to keep up-to-date.

Couldn't agree more. I wrote several of the scripts that keep liboqs up-to-date with PQClean, and I wrote several of the scripts that keep PQClean up-to-date with the submission packages. I would do the same for NSS (or accept a patch) as soon as we have a need for these algorithms.

If that doesn't convince you, then I can fall back to a patch where we just include system liboqs support.

Imagine if someone came to us saying "NSS doesn't support NTRU, but BoringSSL does. Here's a patch on FreeBL that calls the NTRU implementation in BoringSSL. It relies on BoringSSL to get random bytes from the OS, and it uses BoringSSL's implementation of SHA256." We wouldn't take that patch.

signatures are also something that will need some higher level changes

Yes, I agree there's a lot of groundwork that needs to be done before we can integrate any of new signature schemes into a PKCS#11 module.

Comment 10

[Robert Relyea]

OK, so if we are going to pull PQClean from upstream with scripts, I'm OK with that. The scripts should be checked into NSS. This means that changes mozilla makes will go back to PQClean and changes other libraries make will come back to mozilla, so our goal of a single source for PQ that can be hardened together will be met.

We (RedHat) still needs to include an option to build with nss with liboqs. There is a difference to our BoringSSL case here, it's a request from a group who has made a long term commitment to NSS developement and maintenance (which I've been working on for 30 year;). We'll be asking the same for openssl and gnutls.