Add Post-Quantum Crypto Schemes

[hrantzsch]

As indicated a while ago to @randombit in a private email the German Federal Ministry of Education and Research is funding a project to implement post-quantum crypto schemes in Botan (project homepage -- in German).

We are creating this issue to provide an overview of what we intend to do within the scope of this project and to provide a place to coordinate work.

The main goal of the project is to add post-quantum crypto schemes to Botan.
While the decision which schemes will be implemented is not yet final, the most likely candidates at the moment are Crystals-Kyber as a key exchange scheme and Crystals-Dilithium as a signature scheme.

Besides the implementation of the crypto schemes, the project also involves

• investigating possible improvements to key management in Botan (with a possible focus on post-quantum and trusted computing)
• a focus on measures to be taken against side-channel attacks
• implementing hybrid schemes with the added PQ schemes
• analyzing/extending crypto agility
• analyzing usability of the relevant interfaces
• implementing demo applications

Please feel free to comment here if you have thoughts or hints on those topics and specifically our preliminary selection of PQ algorithms.

Note that the project duration is scheduled until late 2022, so PRs adding the schemes are not to be expected within the next few months, yet.

[randombit]

I haven't checked the latest revisions of the Crystals algorithm specifications, I think things have changed a bit as the NIST competition as proceeded, but I would be in favor of adding both Kyber and Dilithium

[guidovranken]

Hi @hrantzsch, I maintain Cryptofuzz which uses differential fuzzing to find memory and correctness bugs in cryptographic libraries. This has proven to be a very effective approach, you can see the list of bugs here. If this interests you with regards to your project, feel free to contact me at [email protected].

[mouse07410]

I would also like to see inclusion of NTRU HPS4096821 and Falcon-1024.

[Ellie-42]

The BLISS algorithm would be pretty optimal too, lattice based cryptography is powerful

[randombit]

Is there any reason to prefer BLISS over Dilithium?

[mouse07410]

Is there any reason to prefer BLISS over Dilithium?

My concern with BLISS is that it wasn't submitted to the NIST PQC competition. So, it did not undergo a comparable scrutiny.

Its key and signature sizes are attractive, but not at the cost of being (potentially?) less-secure. Also, precursory search did not show what kind of licensing BLISS requires.

[Ellie-42]

Is there any reason to prefer BLISS over Dilithium?

My concern with BLISS is that it wasn't submitted to the NIST PQC competition. So, it did not undergo a comparable scrutiny.

Its key and signature sizes are attractive, but not at the cost of being (potentially?) less-secure. Also, precursory search did not show what kind of licensing BLISS requires.

The license is CeCILL. Its preference from Dilithium may be that there are implementations easily accessible out there for Dilithium, BLISS has about three easily found implementations. With the StrongSwan plugins set, directly form the original developers, and as a FPGA design.
As for it's security, there was one type of study repeatedly done involving finding the private key on a compromised host.
From what can see, it is also comparably fast in terms of speed against elliptical curve algorithms.

On the website they do explicitly state NOT to use the academic code for secure implementations, but a proper version is available form them.
https://bliss.di.ens.fr/

The StrongSwan implementation may also have protected against the above mentioned attacks given those attacks are well known.

Some attacks rely on the original BLISS scheme, not BLISS-B,
https://eprint.iacr.org/2017/490.pdf

But it still is vulnerable because of its spherical Gaussian sampling.
https://eprint.iacr.org/2019/898.pdf

It does have impeccable security, though is vulnerable to side-channel attacks, unfortunately.
Though, perhaps the developers have a secured version?

Though in every paper I find, the consensus remains the same, the Gaussian sampling method is prone to a FLUSH+RELOAD cache attack.

Perhaps it could also be prevented by utilizing secure measures in the system itself to prevent leakage?

In short, the biggest appeal is its speed and key size, but a major pitfall is it's susceptibility to side channel attacks.

[randombit]

Ominously, Strongswan's BLISS implementation is still vulnerable to the bug identified in 2019/898. I'm generally very wary of Gaussian sampling in lattices as it seems both side channel prone and also just plain hard to sample correctly - IIRC there was a bug in an early version of the Falcon code that sampled incorrectly and was insecure. Dilithium's use of uniform sampling seems much safer.

Also the licensing of both Strongswan's version and the reference code are quite incompatible with BSD-2. So we'd have to do a from scratch impl. Whereas Dilithium for example has a public domain reference implementation that we can adapt directly if we want. Not insurmountable but does add to the work.

Ultimately though, everyone is better off if major libraries converge on just a handful of PQ schemes that can interop. Otherwise we end up with a lot of problems for users, it will hurt adoption since it won't be consistently available, and we won't be able to use nice things like cryptofuzz effectively. Since BLISS is not in the running with NIST it is unlikely to fill the niche of lattice based signatures, vs Dilithium or Falcon.

Perhaps it could also be prevented by utilizing secure measures in the system itself to prevent leakage?

Always a reasonable option for the system designer, but somewhat out of scope for us as a library.

[Ellie-42]

Ominously, Strongswan's BLISS implementation is still vulnerable to the bug identified in 2019/898.

As a follow up, I did contact the researchers (separate of this, for my own research) and BLISS has been discontinued for development and Leo Ducas recommended using Dilithium for a lattice based signature scheme.

Thought that might be of use in this discussion 😄

[randombit]

@hrantzsch Do you know if this relates in a direct way to
https://thunderbird.topicbox.com/groups/planning/T5abbf135db2f3c1c/the-german-bsi-intends-to-sponsor-pqc-improvements-for-openpgp-in-thunderbird or is just a coincidence that Thunderbird uses RNP which uses Botan, and BSI wants PQ in Thunderbird?

Also, any updates on this project you can share? Timelines etc. Thanks!

[hrantzsch]

Hi Jack, I am aware of the project, although I wasn't aware that Thunderbird's PGP is based on Botan!
The project isn't related to us in a direct way and I currently the tendering procedure is still ongoing.

The implementation of Kyber and Dilithium is ongoing and making good progress. I'm personally not involved in the implementation but I asked our project partner for an update of the timeline.

[mouse07410]

@hrantzsch why not just use Kyber and Dilithium implementations provided by their inventors?

[Ellie-42]

@hrantzsch why not just use Kyber and Dilithium implementations provided by their inventors?

Because the Botan library tries to be dependent upon itself, and not have redundant algorithms. There's no need to use the source code that implements their own SHA256 or SHA3 while have a cryptographically secure version in the Botan library (Not to say the source is not secure but its easier to ensure it is) This also makes it easy to perform updates on modules rather than redundant updates through various source code. But I'm sure big parts of it are being used, just being modified to accompany existing code.

[taudor]

@hrantzsch Do you know if this relates in a direct way to
https://thunderbird.topicbox.com/groups/planning/T5abbf135db2f3c1c/the-german-bsi-intends-to-sponsor-pqc-improvements-for-openpgp-in-thunderbird or is just a coincidence that Thunderbird uses RNP which uses Botan, and BSI wants PQ in Thunderbird?

Hi Jack, I'm also part of the KBLS team. It's not a coincidence that RNP/Botan is used in the linked project. The work from KBLS is also mentioned explicitly there.

Also, any updates on this project you can share? Timelines etc. Thanks!

A PR for Kyber should be ready in August, and for Dilithium later this year.

[reneme]

Implementations of ML-KEM, ML-DSA and SLH-DSA were merged into the master branch today and are slated for release with Botan 3.6.0 next week.

A huge amount of work, sweat and effort went into this and wouldn't have been possible without the contribution of a lot of people as well as the financial support via the KBLS project as well as BSI's Project 481!

🎉

Many thanks to all the contributors that made this possible! ❤️

@atreiber94
@FAlbertDev
@lieser
@securitykernel
@boricm
@omarama
@hrantzsch
@lz101010
@falko-strenzke
@aewag
@falsecurity
@taudor
@sehlen-bsi
@fluppe2
@weitkaemper-bsi
@heihagemei

And, of course, a special and heartfelt THANK YOU to @randombit for all the time and effort spent in many code reviews, consultations and discussions!

You guys rock!