NIST Round 2 and Post-Quantum Cryptography – The New Asymmetric Algorithms (part 3)

Posted on Feb 20, 2019 by Derek Zimmer
Share Tweet Plus

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.

 

About Derek Zimmer

Derek is a cryptographer, security expert and privacy activist. He has twelve years of security experience and six years of experience designing and implementing privacy systems. He founded the Open Source Technology Improvement Fund (OSTIF) which focuses on creating and improving open-source security solutions through auditing, bug bounties, and resource gathering and management.

VPN Service