The Inability to Count Correctly?

The Inability to Count Correctly?

Over the past few weeks, I’ve presented four quantum computing talks to over 400 people — including two with employees of NatWest and Lloyds Bank, and I have another major one coming up at #Risk in London [here]. The focus of these is on the risks of PQC (Post Quantum Cryptography) — and it is a topic that is moving to the top of the cybersecurity agenda:

In the talks, I outline how we need to move away from ECDH (Elliptic Curve Diffie Hellman) towards Kyber for key exchange and that the move needs to happen sooner rather than later. But not everyone thinks that Kyber is the method we could be focusing on, and one of those who are sounding alarm bells is the mighty Daniel Bernstein:

And, so, NIST moves towards standardizing three new digital signature methods (Dilithium, FALCON and SPHINCS+) and a key exchange method (Kyber). But not everyone is happy about the selection of Kyber. But, Daniel Bernstein thinks there is a problem and that the security of Kyber-512 (the 128-bit security level) has been miscalculated.

His starting point is that 2⁴⁰ + 2⁴⁰ is 2⁴¹ and not 2⁸⁰.

Daniel believes that the security levels of the Kyber-512 method are flawed, as it has multiplied two cost values that should have been added. And, so, in March 2022, a FOIA (Freedom of Information Act Request) was submitted by the mighty Dan Bernstein [here]:

For this, he believes that there has been NSA involvement in the NIST standards, including meetings where there were more NSA people within the [email protected] team members than for NIST people, and that there are documents that refer to NIST’s .“next meeting with the NSA PQC folks”, along meetings with the NSA.

Daniel has since created a new lawsuit based on new evidence.

From his current blog posting, Daniel outlines that NIST miscalculated the security level of Kyber and thus showed that it has a better security performance than NTRU.

Daniel outlines that Bob and Alice agree on new encryption methods and that have a cost of computation of 2²⁵ operations and 2³⁵ bit operations, and where NIST’s calculation defines this as 2⁶⁰ operations, but where it should be just over 2³⁵ bit operations as we should add them together. For example, if we have 2⁸ (256) and add it to 2²⁰ (1,048,576), we get a value that is just over 2²⁰ (1,048,832) and not 2²⁸ (268,435,456).

And, so, Daniel thinks that the security levels of Kyber have been compromised. Also, he questions the scalability of Kyber, and where we jump from Kyber-512 to Kyber-768, and then to Kyber-1024 for even higher security, but that going beyond this could leave it open to occasional “decryption failures”. But, he argues that NTRU ((Nth degree TRUncated polynomial ring)) gives much better options for higher security levels:

https://asecuritysite.com/lattice/ntru_key

Overall, Kyber 768 has a security level of around 128 bits of security. Daniel’s viewpoint is that Kyber 768 has 1,184-byte public keys and 1,088-byte ciphertexts and that an application which is limited to 1KB of memory will not be able to process the encryption (and will thus be limited to Kyber 512 with its 800-byte keys and 768-byte ciphertexts). NTRU though could use sntrup653 and which has 994-byte keys and 897-byte ciphertext, and where the security level is 2¹²⁹, and for NTRU-677 this moves to 2¹⁴⁵ (and with 931-byte keys and 931-byte ciphertexts). The scalability of NTRU is thus much better than Kyber.

For the reason for picking Kyber over NTRU, NIST defined that

Kyber, as “marginally more convincing” than the problem inside NTRU.

But Daniel rebuts this with a range of arguments.

There’s much more that could and should have been said about the security comparison between Kyber and NTRU, including that the security proofs for NTRU are stronger than Kyber, for levels of security above Kyber-512. NTRU also has a smaller footprint for levels above Kyber-512.

When I ran tests for the PQC contenders, it can be seen that Kyber generally ran faster than NTRU [here]:

And that Kyber beat NTRU on key and cipher sizes for the equivalent key sizes [here]:

But, Daniel thinks that this is not the full story, and NTRU is much more flexible than Kyber, and where NTRU can be selected with the right parameters to beat Kyber in both performance and key/ciphertext sizes.

Conclusions

And, there you go. The move towards PQC will be one of the greatest changes in the security of the Internet ever, but it needs to be done correctly. This should involve scaling our security over the years. Daniel thinks that the selection of Kyber was (perhaps) flawed and that NTRU provides us with a better foundation for key exchange methods. The Kyber method does seem quite inflexible in its selection of parameters, whereas NTRU allows for security levels and performance to be more finely tuned.

The suspected intentional backdoor in the Dual EC random number generator showed that NIST could be open to weakening security levels:

https://asecuritysite.com/random/dualec

Daniel’s blog post is here.