Post-Quantum Cryptography - Round One

See also round 2 and round 3.

After NIST’s post-quantum crypthography call for proposal, we have quite a few submissions for round 1.

With almost 70 entries and considering these are all (almost) completely new algorithms, it’s hard to say which are going to be favorites. However, based on no science but name alone, I do have a few favorites.

First one is nod to Star Trek in form of CRYSTALS-DILITHIUM. It is a lattice-based scheme with slight performance advantage over other proposals. Sadly, it uses CryptoJedi as hosting for its white paper which I believe constitutes forbidden religion mix.

Further into the Jedi territory, there is a NewHope algorithm. As it’s unfortunately case with many proposal, there is no website for it, but there is a white paper. It’s again lattice-based algorithm with a focus toward forward secrecy. Not too bad and I would say quite a favorite considering it’s already present in Chrome.

One I like is NTRU Prime. It is (again) lattice-based, but it takes special care to avoid issues other lattice systems might have - the most important being constant-time execution to make classic side-channel attacks more difficult.

Another one to check might be Falcon. It is again lattice-based but with special care given to small memory footprint and stellar performance.

If lattice-based does not work, my money is on DAGS algorithm using quasi-dyadic codes. Its small key size compared to other code-based candidates and possibility of asymmetric key exchange where you get to fine-tune load on server as compared to client make it ideal for IoT (often both energy and performance deprived) applications.

Lastly, RLCE-KEM seems interesting as its RLCE-based encryption gives high performance - even when compared to traditional algorithms. It is a bit finicky algorithm, especially when it comes to padding, but its speed might make it worth.

It is way too early to make serious predictions but I personally really like thought that went into DAGS. It seems to be something that could nicely work for both current and post-quantum scenarios. And fine tuning of server/client work ratio seems to be god-given for battery operated devices. Of course, with great flexibility comes a great responsibility and (generally-speaking) more flexible algorithms allow security downgrades a bit more of a risk.

We shall see what round 2 brings next year. :)

Post-Quantum Cryptography – Round Two

See also round 1 and round 3.

After a bit more than a year since round one, we are now in the round two of post-quantum cryptography standardization process.

NIST Status Report trimmed original list of 69 algorithms to 26 that will be further studied. Based on the previous experience I would think there will be a third round in a year or so but NIST leaves open a possibility that we’ll immediately get the two finalists (one for public key exchange and one for signing).

My Star Trek key signing favorite (CRYSTALS-DILITHIUM) is actually still in the game and a further analysis is encouraged - probably as close as it gets to a positive review from NIST. It’s key exchange brother CRYSTALS-KYBER might have gone a bit too far with it’s “fishy” security proof but more analysis is needed there.

Star Wars universe is also strong with NewHope key exchange algorithm. Force is indeed strong within this one and I would dare to say it remains a strong favorite - especially due to it’s current use in Chrome.

NTRU Prime is still in there but NIST did notice a bit overly optimistic security level claims that might need to be adjusted in the future. I believe constant-time decryption this algorithm brings is a really interesting thing - especially when it comes to hardware and side-channel attacks.

I noted FALCON for its performance with a small memory footprint and that won it enough points to get into round two. However, difficulty of correct implementation and a huge potential for side-channel attacks might leave it here.

DAGS, which I loved for it’s tweakability of server/client load unfortunately stayed in round one. Likewise, RLCE-KEM noted for its performance was left behind too - largely due to complexity of (correct) implementation.

One algorithm I didn’t note in round one is Three Bears. Not only it has an awesome name and uses Mersenne primes but it also offers excellent performance. Might be a worthy challenger to NewHope.

Next update in 12-18 months. :)

Post-Quantum Cryptography - The Last Round

See also round 1 and round 2.

Well, after a long time, NIST announced the first four quantum-resistant cryptographic algorithms.

Both of my StarTrek inspired favorites are actually in. CRYSTALS-Kyber is the one selected for a key exchange purposes and I fully expect to see it in some future OpenSSH version. Since dealing with ED25519 would require a quantum computer much bigger than currently available, eliptic curves are still probably the best default choice. However, you don’t want to wait the last moment to switch. Considering there are still some system that only support RSA (yes Mikrotik, I’m talking about you), switch will take a while.

CRYSTALS-Dilithium, a part of the same family, got selected as one of three suggested digital signature algorithms. From practicality side, it will rarely, if ever, be used alone as its signature output is literaly larger than a KB. That said, there are a few suggested modes (e.g., Dilithium3-AES) keeping the reasonable key size AES provides while retaining quantum assurances of a lattice algorthm.

FALCON was also selected despite difficulty of a correct implementation and a huge potential for side-channel attacks. I guess a small memory footprint and impressive performance in embedded applications were enough to ensure its place among finalists.

Lastly, a SPHINCS+ came out of blue (at least for me) to take its place as the last of the finalists. Since it is slower and larger than either of the other two finalists, it’s hardly a first choice. Regardless, using a different math approach compared to other two finalists was valuable enough to get it in.

NewHope, one of the round two finalists and already used by Chrome ended up like the recent Star Wars sequels. An early succes but ultimately not good enough to pursue.

Warning Me Softly

I already wrote about post-quantum cryptography before. If you check the dates, you’ll see that this is not a new topic. However, it’s still quite common to see standard key exchange for SSH sessions. Well, this might be about to change.

With version 10.1, OpenSSH will present you with the following warning:

** WARNING: connection is not using a post-quantum key exchange algorithm.
** This session may be vulnerable to "store now, decrypt later" attacks.
** The server may need to be upgraded. See https://openssh.com/pq.html

In reality, this change nothing as everything will continue to work as before. But, knowing the human nature, I forsee a lot of people moving to a newer key exchange just to avoid the warning. In no time, projects will face their security review teams. And if security team doesn’t like warnings, projects will oblige.

My own network is in surprisingly good state. Most of my SSH connections already uses sntrup761x25519-sha512 key exchange algorithm. However, there are two notable exceptions: Windows and Mikrotik.

Mikrotik, I pretty much expected. It took them ages to support ED26619 so I don’t doubt I will see the warning for a long while before they update software. I love Mikrotik devices, but boy, do they move slow.

But Windows 11 came as a surprise. They still advertise curve25519-sha256 at best. I guess all that time spent making start menu worse prevented them from upgrading their crypto. I predict that, as always, when warning starts, Microsoft forums will be full of people saying that warning is wrong and that Windows can do no wrong. Only to eventually be dragged into the future.