Post-Quantum Cryptography

 

TL;DR "We recommend using the Kyber-768 parameter set, which—according to a very conservative analysis—achieves more than 128 bits of security against all known classical and quantum attacks."  

~ Kyber Team            

In a soon-approaching world of quantum computers that can easily break the current cryptography we rely on for secure banking and e-commerce, mathematicians are hard at work finding the next generation of cryptography standards that can withstand even quantum computing attacks. The U.S. National Institute of Standards and Technology (NIST) has been evaluating candidates since 2017 and published Round 3 candidates on July 22, 2020, whittling the public key encryption finalists down to four:

• Classic McEliece
• CRYSTALS-KYBER
• NTRU
• SABER

These are the candidates that NIST feels are the most mature, peer-reviewed, and production-ready to be considered for a final decision.

They also acknowledged some newer candidates that offer potential but need more time to mature:

• BIKE
• FrodoKEM
• HQC
• NTRU Prime
• SIKE

NIST provides security levels (1-5) that are roughly equivalent to familiar AES / SHA counterparts.

Some notes for reference:

Kyber has great Level 3 clean performance:

Another source (note the significant performance improvement of Kyber on ARMv8 NEON boards):

... the Apple M1 chip is even more dramatic:

Quentin M. Kniep's thesis with security level definitions and relevant benchmarks (SABER, NewHope, and NTRU NIST-Level-I were slower than Kyber so not included). Of especial note: "Kyber-768 seems almost perfect for the L1 handshake, as it is almost as fast as WG, and also fits into one datagram per message."

Another source (lower is better):

Referenced paper's conclusion: "If execution time or power consumption are of greatest concern, the Kyber, New Hope, Ntru, and Saber implementations are good candidates for KEM algorithms. However, if memory usage is of greatest concern, the Kyber and Three Bears algorithms are best suited."

NIST concurs: "[KYBER] has excellent all-around performance for most applications. ... NIST views CRYSTALS-KYBER as one of the most promising KEM schemes to be considered for standardization at the end of the third round."

NIST also indicated "SABER has excellent performance and would be immediately suitable for general-purpose applications. ... SABER is one of the most promising KEM schemes to be considered for standardization at the end of the third round."

There are risks, however. For example, Kyber, SABER, and NTRU Prime have known patent threats. NIST explains: "NTRU has less risk of unexpected intellectual property claims. NIST expects that, at most, only one of these candidates—KYBER, SABER, or NTRU—will be standardized at the end of the third round. In the event that new cryptanalytic or intellectual property issues threaten the future of KYBER and SABER, NTRU would be seen as a more appealing finalist."

       source

Here's an additional risk matrix published by NTRU Prime:

As noted in the matrix above, Kyber and SABER allow extremely rare, but non-zero, decryption failures. 

It was recently demonstrated FrodoKEM is susceptible to side-channel attacks and power trace attacks. NIST also noted "FrodoKEM would have a noticeable performance impact on high traffic TLS servers"

NTRU Prime is susceptible to side-channel attacks.

Solutions based on isogenies, like SIKE, are susceptible to fault attacks.

Another fault attack targeted NewHope, Kyber, FrodoKEM, and Dilithium. This one was particularly interesting. NewHope, Kyber, FrodoKEM, and Dilithium are all LWE based. Kyber adds some compression to the private key so the attack was able to break LWE and recover the keys for NewHope, FrodoKEM, and Dilithium directly but the Kyber result was inconclusive. "[T]he authors do not consider this as an added layer of security but simply as a technique to reduce the output size". SABER is LWR based (a variant of LWE), which was not in scope for their test: "Our attack removes the hardness guarantees of the generated hard instance from the Module-LWE problem, while the Module-LWR problem remains to be solved." Accordingly, NIST recommends SABER perform "additional research regarding side-channel ... [and] concrete differences between the security of MLWE and MLWR".

Because Classic McEliece has large public keys (over a megabyte!), NIST indicated "Classic McEliece is not a good fit for general use in internet protocols". Efforts are underway to address this with McTiny (mctiny6960119) which breaks the key up into chunks.

NTRU causes unusual, rapid power fluctuation:

The latest October 2020 BIKE 4.1 spec isn't generally available but the open source community is working on it. Also, performance is worse than most of the competitors. In addition, "BIKE" is practically impossible to Google search due to the generic name -- "bikesuite" and "bike-kem" seem your best SEO options at the moment.

HQC released a NIST submission update a couple weeks ago. The detailed paper highlights attack vectors that affect both HQC and Classic McEliece: Information Set Decoding and structural attacks like DOOM. They propose defenses using strong parameters but this increases key size and reduces performance. In addition, HQC doesn't scale well after 256 bits.

Bottom line: Kyber and SABER both show the strongest promise if the patent concern can be resolved. Between them, Kyber is faster, not vulnerable to amplification attack, is ARM optimized, uses less RAM and slightly less energy so it's my top pick at the moment, although the potential fault attack needs to be researched further.

P.S. strongSwan users should avoid using BLISS. NIST also dropped NewHope in favor of Kyber for performance reasons. NTRU is supported. Check out alpine-strongswan-vpn (uses NewHope) or qske (any algorithm supported by the nistpqc library) or pq-strongswan (any algorithm supported by the liboqs library, via the undocumented oqs plugin).

P.P.S. WireGuard has provided guidance on the best method to post-quantum protect itself. The following projects implement that approach: pq-wireguard, which uses a combination of Classic McEliece and a SABER variant, is "less than 60% slower than a WireGuard handshake, is more than 5 times faster than an IPsec handshake using Curve25519, and more than 1000 times faster than an OpenVPN  handshake" (source). Based on Quentin M. Kniep's thesis project, pqwg-rust (forked from Cloudflare's boringtun project) replaces Wireguard's handshake with Kyber since "SABER and NewHope ... both have slower computation and are no better in message sizes than Kyber"; however the tool can be configured to use SABER, NewHope, NTRU, or SIDH. Vula is another option, using a less-secure isogeny-based CSIDH algorithm. Note: although not truly post-quantum cryptography, you can mix in a preshared key to protect against post-quantum attacks -- this is what Windscribe uses for their "quantum resistant" VPN and Mullvad uses for their "post-quantum strategy" and Microsoft in their OpenSSL fork. However, Kniep notes "This solution will never be able to provide [perfect forward secrecy] PFS this way because the [pre-shared key] PSK is static. ... In other words, all traffic sent over such a tunnel, is only secure against a quantum adversary for as long as the static-PSK stays safe." This is Level 0 (Kniep-L0) as defined above.

source

P.P.P.S. Go lang fans should check out crystals-go (code).

P.P.P.P.S. OpenSSLNTRU: Faster post-quantum TLS key exchange demonstrates that NTRU is still a potential option, despite its larger keys and relatively moderate performance:

Excited? Dive in!