Classify algorithm status

[baentsch]

A concrete NIST announcement date, hurray: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/7yLIZcFOMF0/m/vn43l1tQAQAJ

Bets still accepted.... :-) Eliminating McEliece and SPHINCS+ would be a boon for our CI runtime (and the world's power-consumption-induced CO2 emissions).

[baentsch]

Well, (combatting) global warming seems to have been no major decision criterion :-(

On the bright side it seems we now can claim/document to have all selected and all round 4 algorithms. Suggestion thus to prune (post 0.7.2)

• Frodo
• NTRU
• NTRU prime
• Rainbow
• Picnic

[jschanck]

I suggest keeping NTRU for now. There's a footnote on page 18 of the round 3 status report which says that NTRU is the backup if the patent agreements for Kyber are not finalized by end-of-year.

[dstebila]

I suggest keeping NTRU for now. There's a footnote on page 18 of the round 3 status report which says that NTRU is the backup if the patent agreements for Kyber are not finalized by end-of-year.

Yes, I had in mind that we'd probably keep NTRU around for the time being due to that footnote. In today's status meeting we didn't make any firm decisions about what to prune, instead wanting to think more over the next couple of weeks and see whether there will be a future for any of the algorithms outside of NIST, e.g. resubmission to Round 4 or interest by other governments. We might provide some configure-time options to help people select certain bundles of algorithms.

[baentsch]

Agree. So the goal for the resolution of this issue is to define and create a mechanism to build liboqs such as to differentiate at configure time (at least) between "standardized", "round4" and "research" algorithms, leading to different levels of (CI) testing and default inclusion in library builds. A final class comprises algorithms to be completely pruned.

So here's a first proposal:

"standard": kyber, dilithium, falcon, sphincs
"round4": bike, classic_mceliece, hqc, sike
"research": frodo, ntru, picnic
prune: rainbow, saber, ntruprime

Comments welcome. Regarding picnic, particularly by @christianpaquin; ntru as per the above (thanks, @jschanck) and frodo (thanks, @dstebila). Who could argue for the/a different classification of the "prune" candidates? Regarding ntruprime, what about touching base with the openssh community (whether they want to retain it regardless)?

[christianpaquin]

I think that makes sense. It will take time for the various teams to decide how to proceed with their schemes (and therefore for us to keep them as research algs), but meanwhile we can start building the framework, and leniently mark the unknowns as "research". Teams have until Oct 1st to submit round4 tweaks, so I suppose we'll have an updated release by the end of the year.

[tmcqueen-materials]

Just to chime in here: I fully appreciate the desire to separate out algorithms, especially those that will not be proceeding to standardization, but in my view part of the value of liboqs is it allows experimentation and interoperability with a variety of components. I would thus be in favor of keeping ntruprime (or at least sntrup761), at least until such time as it is removed from OpenSSH.

[baentsch]

would thus be in favor of keeping ntruprime (or at least sntrup761), at least until such time as it is removed from OpenSSH.

Thanks for the proposal. To help us collect some more background to this suggestion: Did you (or are you aware of anyone that did) test interoperation between the OpenSSH-sntrup761 with https://github.com/open-quantum-safe/openssh ? Does OpenSSH use liboqs?

[dstebila]

would thus be in favor of keeping ntruprime (or at least sntrup761), at least until such time as it is removed from OpenSSH.

Thanks for the proposal. To help us collect some more background to this suggestion: Did you (or are you aware of anyone that did) test interoperation between the OpenSSH-sntrup761 with https://github.com/open-quantum-safe/openssh ? Does OpenSSH use liboqs?

Interop between OpenSSH and OQS-OpenSSH on sntrup761 doesn't really make sense, because OQS-OpenSSH would include OpenSSH's sntrup761 suite without alteration. As far as I know, OpenSSH natively includes an sntrup761 implementation, rather than using liboqs'.

[baentsch]

Interop between OpenSSH and OQS-OpenSSH on sntrup761 doesn't really make sense, because OQS-OpenSSH would include OpenSSH's sntrup761 suite without alteration. As far as I know, OpenSSH natively includes an sntrup761 implementation, rather than using liboqs'.

In that case I wonder why liboqs should be

keeping ntruprime (or at least sntrup761)

[tmcqueen-materials]

So to clarify: my point was not about incorporation in OpenSSH itself because, as noted, recent versions of OpenSSH include the reference sntrup761 implementation and does not rely on liboqs to provide it.

My point is rather about the ecosystem of software that speaks SSH but does not leverage the OpenSSH codebase, particularly custom clients and servers -- in some of those cases, liboqs is the rational plug-in provider of pqcrypto implementations. Since various long-term stable linux distributions incorporate OpenSSH 8.9 (e.g. Ubuntu 22), even if OpenSSH moves to one of the NIST "to be standardized" algorithms, sntrup761 will remain in many cases as the only available pqcrypto choices for some time.

Worst case software that relies on OpenSSH pqcrypto interop currently using liboqs can either just stick with an old version of liboqs or modified to directly use the reference implementation, but it seems wrong for a wonderful "reference toolkit" of options (i.e. liboqs) to not support it, at least until it is (mostly) phased out [I guess another way to "depreciate" that actually would mesh well with the timescales of LTSs would be to move the "prune" algorithms to "included but not built by default" in v0.8.x, and then removed in v.0.9.x]

[dstebila]

Ah, I see what you're getting at: other SSH implementations that want to interop with OpenSSH will need an implementation of strnup761, and liboqs would be a convenient source for that, speaking to keeping strnup761 in liboqs. Duly noted, let's take that under consideration. Do you know if there any other algorithms from the NTRU Prime family that are relevant? If we can even prune it down to just strnup761 and remove code for the rest of them, that would be helpful.

[xvzcf]

I've prepared the following summary of the status of our implementations. I thought it was best placed here, but I can break it out into another issue if need be.

KEMS

Algorithm name	Update?	Will update break interop?	Comments
BIKE	Yes, tracked in #1318	Yes, features a new vector sampling technique that results in new KATs.	Implementaton corresponds to BIKE_Spec.2020.05.03.1.pdf spec, whereas the latest specification is BIKE_Spec.2022.10.10.1.pdf.
Classic McEliece	Yes, tracked in #1314	Yes, removes plaintext-confirmation, which means ciphertexts are 32 bytes smaller.	Already noted here.
FrodoKEM	No	-	-
HQC	Yes, tracked in #1319	Yes, switches to KECCAK for domain separation and randomness.	Implementation taken from PQClean, whose is based on the 2020-10-01 specification. Latest version is 2021/06/06.
Kyber	Done via #1316	No	Implementation based on commit 8e00ec73035147d18b27d06048dff322f8de1f29, there is one commit (and merge commit) after, that fixes a comment typo.
Kyber (ARM)	Yes, tracked in #1320	No	Taken from PQClean, which is based on neon-ntt commit c6ffbcd1e5590e4dddbc604fc80d2ad756485b4d; a more recent commit 328d80a81ea9ff1f0bb72123460fd941795f6157 seems to have relevant changes (to feat.s).
NTRU	No	-	Taken from PQClean, where its been removed. The latest update to NTRU was on 2020-10-16. Last update to PQClean was on November 15, 2021.
NTRU-Prime	No. Remove. Tracked in #1317	-	No longer in the NIST PQC competition.
Saber	No. Remove. Tracked in #1317	-	No longer in the NIST PQC competition.

Signatures

Algorithm Name	Update?	Will update break interop?	Comments
CRYSTALS-Dilithium	Done via #1316	No.	Implementation based on commit 61b51a71701b8ae9f546a1e5d220e1950ed20d06. There is one commit after which adds an additonal license.
CRYSTALS-Dilithium (ARM)	Yes, tracked in #1320	No.	Same situation as Kyber (ARM).
Falcon	Yes, tracked in #1315	Yes, features updated paramters and enforces a unique encoding of signatures.	Already noted here.
Picnic	No. Remove. Tracked in #1317	-	No longer in the NIST PQC competition.
Rainbow	No. Remove. Tracked in #1317	-	No longer in the NIST PQC competition.
SPHINCS+	Yes, tracked in #1249	Yes, see here	See here.

[dstebila]

Thanks @xvzcf that's really helpful! Were you able to tell which updates were implementation updates and which were algorithm updates breaking interoperability?

[xvzcf]

Thanks @xvzcf that's really helpful! Were you able to tell which updates were implementation updates and which were algorithm updates breaking interoperability?

I did not pay particular attention to that, but I can add another column to the table indicating whether that is the case.

[xvzcf]

I did not pay particular attention to that, but I can add another column to the table indicating whether that is the case.

Done.

[dstebila]

Thanks very much, Goutam! Let's discuss prioritizing these in tomorrow's meeting.

[bhess]

Thanks @xvzcf for the list! I opened a PR with the Dilithium/Kyber update: #1316.

[christianpaquin]

Just to confirm that Picnic is not part of Round 4; it can be removed as well.

[xvzcf]

In light of https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/WX3u_lU_AQAJ, shall we remove NTRU as well?

[dstebila]

In light of https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/WX3u_lU_AQAJ, shall we remove NTRU as well?

@jschanck Any comments before we take a decision? Are there any plans for NTRU to be considered for standardization elsewhere?

[jschanck]

Not that I'm aware of. I think it's safe to remove it.

[baentsch]

In light of https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/WX3u_lU_AQAJ, shall we remove NTRU as well?

In light of the same statement, shall we consider removing SPHINCS+ robust' variant, too? It would save substantial amounts of (also CI) computing/time.

[dstebila]

In light of https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/WX3u_lU_AQAJ, shall we remove NTRU as well?

In light of the same statement, shall we consider removing SPHINCS+ robust' variant, too? It would save substantial amounts of (also CI) computing/time.

That makes sense too. Although I can't find in that email chain where NIST mentioned the specific SPHINCS+ variants they are keeping, perhaps I missed it.

[baentsch]

At the very first mail in the chain, "Moody, Dustin (Fed)" writes

We plan to include the simple (and NOT the robust) version. 

[dstebila]

At the very first mail in the chain, "Moody, Dustin (Fed)" writes

We plan to include the simple (and NOT the robust) version.

Ah, I see that now, thanks! Yes, let's go with that.

[baentsch]

There's more algorithms as "not really favoured" on that list (e.g., Kyber/Dilithium AES variants)... We once discussed about creating a mechanism to build a library with only the "base set" (true "standard" algs) and an "extended research" set? We have something similar in the downstreams with the "enabled" flag (unset for various algorithms). What about the same in liboqs? This would facilitate a smaller (and faster) build for the "select few" and a larger (and slower) build for "all experimental algs". Worth its own issue? But then again, this could be as simple as a cmake variable setting a specific set of OQS_ENABLE_XYZ defines.

[dstebila]

Hmmm... I had thought that the extended research set would comprise things in Round 4 and the new signature call for proposals, with the base set being things selected for standardization. I guess we could consider keeping the variants in the extended set, but are they really still of interest?

[christianpaquin]

I guess we could consider keeping the variants in the extended set, but are they really still of interest?

Ah, right, I guess we can consider removing them altogether (vs. relegating them to the extended set). Maybe wait until we know for sure that NIST won't keep them before fully removing them.

[loganaden]

It appears that the industry still trusts NTRU prime despite its status within the NIST standard process. I've opened an issue here #1329. Removing NTRU prime breaks interop between asyncssh and OpenSSH. This is an issue in my humble opinion. There is also a PR here: #1328

[baentsch]

Removing NTRU prime breaks interop between asyncssh and OpenSSH.

Thanks for the feedback -- very much in line with @dstebila 's comment

Ah, I see what you're getting at: other SSH implementations that want to interop with OpenSSH will need an implementation of strnup761, and liboqs would be a convenient source for that, speaking to keeping strnup761 in liboqs. Duly noted, let's take that under consideration. Do you know if there any other algorithms from the NTRU Prime family that are relevant? If we can even prune it down to just strnup761 and remove code for the rest of them, that would be helpful.

#1329 adds all NTRUPrime algs back, though -- would it be possible/sensible/sufficient to modify the PR such that it only brings back the algorithm(s) needed for OpenSSH?

[loganaden]

@baentsch sure. we will work on updating the PR.

[xvzcf]

Shall I convert this into a discussion? Seems like this is turning into one anyway ...

[loganaden]

@xvzcf although we are focused mostly on integrating pq into different internet protocols, we would be happy to maintain NTRU Prime and improve it. However, we would need some initial help :-)

[baentsch]

All algorithms to-be-removed are gone and all required updates are separately tracked. Thus closing this issue.