NIST Round 2 and Post-Quantum Cryptography – The New Asymmetric Algorithms (part 3)
In the first article of this series, I wrote about the NIST Post-Quantum Competition and which ciphers advanced to the second round, meaning that they passed through basic scrutiny and were advanced based on having strong fundamental design and good documentation.
Round 3 will see significant narrowing again, based on the relative strength of the algorithms against one another, as well as the performance of the algorithms on current devices.
Here we talk about each of the candidates for asymmetric algorithms, which are used in establishing a secure connection between a client and server. Even today, asymmetric handshakes are slow and asymmetric encryption is not used for doing anything but passing a secret value between a client and server. Once the shared secret value is passed, the connection switches to a much faster symmetric cipher like AES or ChaCha.
So without further ado, here are the candidates and the broadest strokes on what they are all about: (This is submissions L – Z, last week featured submissions A-L!)
LAKE, LOCKER and Ouroboros-R are now ROLLO
Rollo is a lattice based cryptosystem that relies on rank metric codes. This is similar to McEliece and others. It has had a few serious encryption problems in the sample implementations that generate non-random ciphertexts and the implementations are currently not constant-time.
LEDAkem and LEDApkc are now LEDAcrypt
LEDAcrypt is a merger of two separate projects, the LEDA Key Exchange Mechanism and LEDA Public Key Cryptography. The core function in LEDAcrypt is Quasi-Cyclic codes with noise which is a new iteration of the Neiderreiter and McEliece cryptosystems. The combination of quasi-cyclic codes and noise algorithms with error-correcting codes gives the system some interesting properties, such as resistance to power and timing analysis. Similar to BIKE, there is a nonzero chance of a decryption failure, which will cause a completely new handshake to be required at a stiff performance penalty. There’s also a number of theoretical problems you can have with implementing a cryptosystem where you can have failures without malicious tampering of data. Denial of service attacks and analysis attacks that intentionally insert errors into data come to mind.
Lepton
Lepton was eliminated in round 1.
LIMA
LIMA was eliminated in round 1.
Lizard
Lizard was eliminated in round 1.
LOTUS
LOTUS was eliminated in round 1.
McNie
McNie was eliminated in round 1.
Mersenne-756839
Mersenne-756839 was eliminated in round 1.
NewHope
NewHope’s core functions revolve around the Ring-Learning-With-Errors (Ring-LWE) problem. The big advantage to Ring-LWE over a regular LWE system is much smaller key sizes, with Ring-LWE key sizes being roughly the square root of a the size of a regular LWE key for the same cryptographic strength.
NewHope’s specification specifically mitigates the possibility of a cryptographic back-door by generating new polynomials every time the algorithm is called. Other implementations of lattice cryptography call for static polynomials which may insert weaknesses into the handshake on implementation. This not only creates resistance to malicious back-doors, but it also creates resistance to advances in cryptoanalytic attacks. If a well funded adversary were to find a weakness in a polynomial that allows decryption, a cryptosystem with static polynomials would have ALL communications using that polynomial broken, whereas one with a dynamic polynomial that changes every time the handshake is initiated means that only that single handshake is broken.
NewHope has relatively large keys due to the customization of the Ring-LWE problem, with handshakes in the 2-3MB range. But the algorithm is light on computation, which allows devices with weaker CPUs to not significantly stall during the key exchange.
Like most other algorithms that implement noise and error correction, there’s a nonzero chance that a handshake can fail. The NewHope designers have accounted for this by using a small noise distribution value, which significantly lowers the rate of possible decryption errors, but this change also weakens security guarantees.
NTRUEncrypt and NTRU-HRSS-KEM are now NTRU
NTRU (zip file warning) is lattice cryptosystem that is a largely unchanged version of the original NTRU design, which is now offered with broad open source licenses.
Recently, new attacks have surfaced for classical NTRU based systems that exploit the special structures of the rings in the reference design. The project does not appear to account for this.
pqNTRUSign
pqNTRUSign was eliminated in round 1.
NTRU Prime
NTRU Prime is a NTRU based lattice cryptosystem that attempts to improve on the original NTRU design by eliminating weaknesses in the structure of the rings used in older NTRU systems. This is a significant step-forward in closing likely attacks on other NTRU based systems.
NTS-KEM
NTS-KEM is a Neiderreiter based lattice cryptosystem that is very similar to Classical McElice. It features some hardware optimizations, but largely stays away from “fancy math” in order to preserve maximum security guarantees. While it does mention weaknesses in the system in the whitepaper, there appear to be no countermeasures written into the algorithm other than increasing the key sizes and primes to provide security guarantees against the speed-ups gained by new attacks.
Odd Manhattan
Odd Manhattan was eliminated in round 1.
Post-quantum RSA-Encryption and Post-quantum RSA-Signature
Also known as pqRSA, these were joke submissions to make the existing algorithm theoretically quantum resistant by making the keys and primes so large that quantum computers could not break them. This involved key sizes in the hundreds of gigabytes and they would take days or months to generate and process. It did not advance to round 2.
pqsigRM
pqsigRM was eliminated in round 1.
QC-MDPC KEM
QC-MDPC KEM was eliminated in round 1.
RaCoSS
RaCoSS was eliminated in round 1.
Ramstake
Ramstake was eliminated in round 1.
RankSign
RankSign was withdrawn from the competition by the team.
RLCE-KEM
RLCE-KEM was eliminated in round 1.
Round2 and HILA5 are now Round5.
Round5 is an algorithm that focuses on the General Learning with Rounding and Ring Learning with Rounding problems in its design. It is limited to NTT friendly prime numbers and subject to Ring-LWE attacks that don’t appear to be accounted for that are mentioned in the NTRU Prime submission. It is, however, significantly stronger than an implementation that uses a fixed polynomial A. Similar to almost all other submissions, there’s a nonzero chance that decryption can fail, leading to a large performance penalty and possible denial of service attacks and other problems when implemented into systems.
RQC
RQC (Rank Quasi-Cyclic) is a code-based crypto design that is similar in nature to BIKE and other cyclic cryptosystems. The interesting aspect of RQC is that it should never have decryption failures during normal operation.
RVB
RVB was withdrawn from the competition by the team.
SABER
SABER is a cryptographic system that relies on the Modular Learning With Rounding algorithm (Mod-LWR). It is lattice-based and faces similar challenges to its cousins that are in the contest. It has a restricted range of values that can be used (NTT-friendly only) and more broadly, shares the same limitations as other Learning With Errors systems.
SIKE
SIKE (Supersingular Isogeny Key Encapsulation) is a cryptosystem that relies on the supersingular isogeny walk problem. Essentially, one has to compute elliptic curves that “fit” between two other defined elliptic curves by matching specific properties of the source curves. This is a relatively new form of cryptography and is an active area of research in the cryptography community. This will be an interesting project to watch as it will have both unique challenges and advantages as the competition progresses.
SRTPI
SRTPI was withdrawn from the competition by the team.
Three Bears
Three Bears is a Ring-LWE cryptosystem.
Rambus – I still do not forgive them for getting the world to adopt the DDR memory standard and then suing all of the memory makers for royalties. I (and this is my personal speculation) mistrust their motivations for being involved with the contest.
Titanium
Titanium was eliminated in round 1.
