SIKE Break is a Wow! Step Back Moment

[I apologize in advance for any typos. This article did not go through the normal editing process.]

Supersingular Isogeny Key Encapsulation (SIKE) is the most recently broken proposed quantum-resistant (i.e., post quantum) cipher to fall at the proverbial 11th hour just before it got announced as a new US/global standard. No matter how optimists, of which I am one, try to spin this, it’s a huge step back moment for the industry.

Note: Arstechnical, as always in all that they cover, does an awesome job covering the recent SIKE announcement: https://arstechnica-com.cdn.ampproject.org/c/s/arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown

Summary Recap

Quantum computers are steadily advancing toward the moment when sufficiently capable quantum computers will be able to render much of today’s most popular asymmetric cryptography (e.g., RSA, Diffie-Hellman, Elliptic Curve Cryptography, etc.) useless. For more background on the quantum cryptographic threat read my book on the subject, Cryptography Apocalypse ?(https://www.amazon.com/Cryptography-Apocalypse-Preparing-Quantum-Computing/dp/1119618193),

or these free primers:

Want to understand quantum physics and computing better? Try my primer

https://www.dhirubhai.net/pulse/quantum-mechanics-computing-primer-roger-grimes/

Quantum Supremacy Achieved and What It Means To Your Company

https://www.dhirubhai.net/pulse/quantum-supremacy-achieved-what-means-you-your-company-roger-grimes/

You Should Start Preparing for the Coming Quantum Crypto Break Now

https://www.dhirubhai.net/pulse/you-should-start-preparing-coming-quantum-crypto-break-roger-grimes/

Some PQC History

The United States National Institute of Standards and Technology (NIST) has been trying to get everyone to prepare for moving to quantum-resistant cryptography since at least 2016 (https://cryptome.org/2016/01/CNSA-Suite-and-Quantum-Computing-FAQ.pdf ), when they told everyone (see clip of the document below) to start preparing NOW!

NIST also started a public contest looking for the quantum-resistant cryptography that we all would need to defeat the coming quantum attacks, with their announcement in 2016 of the NIST Post-Quantum Cryptography contest (https://csrc.nist.gov/projects/post-quantum-cryptography ). People and teams from around the world submitted 82 ciphers and key exchange algorithms. Those 82 got narrowed down to just 26 candidates (shown below) in 2019.

In July 2022, just a few weeks ago, the Round 3 finalists were selected along with a further, new, previously unannounced, Round 4. The following PQC standards were announced (https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms ). The Round 3 finalists are:

Asymmetric encryption – CRYSTALS-Kyber

Digital Signatures – CRYSTALS-Dilithium, FALCON, SPHINCS+

BTW, let me say I’m beyond nerd stoked that one of the PQC finalists is named after something from a Star Wars movie (CRYSTALS-Dilithium) and another is from a Star Trek (CRYSTALS-Kyber) episode. Somehow it just makes my geek spirit just a little happier.

Even with the final selected PQC algorithms selected, the official NIST standard’s release is 1-2 years off.

NIST also started another search in Round 4 (https://csrc.nist.gov/news/2022/pqc-candidates-to-be-standardized-and-round-4) that included four asymmetric algorithms that were in the earlier rounds, but did not become finalists in Round 3. They were/are:

·????????BIKE

·????????Classic McEliece

·????????HQC

·????????SIKE

This was because of the four finalists from Round 3, only 1 selection, SPHINCS+, wasn’t a lattice-based cipher. SPHINCS+ is a hash-based cipher. NIST recognized that having 3 finalist selections that were lattice-based would be a problem if attackers learned how to better crack lattice-based ciphers. It’s better and lower risk to have more PQC algorithms based on different underlying technologies (e.g., Code and Isogeny). Classic McEliece was invented in 1978, and although it seems among the most quantum-resistant ciphers (and has been tested for decades), it is often considered as a last resort PCQ algorithm because it requires large key sizes and would be among the slowest solutions possible. And I think there is some weird, natural resistance to using something invented half a century ago when we are surrounded by all these new shiny toys.

What Happened to SIKE

SIKE (https://sike.org/) is a relatively new encryption algorithm. SIKE uses mathematical-created curves and how hard it is to predict factor the math behind any particular curve as part of its protection. With SIKE, two curves are created, one representing the private key and one presenting the public key. Both curves are related to each other mathematically, but anyone getting only the public key curve can’t easily figure out the related private key curve that led to the public key curve. It’s similar to what Elliptic Curve Cryptography (ECC) does, but with different math that was thought to be highly resistant to quantum computer attacks.

Encryption, like SIKE, based on supersingular isogeny, has been seriously discussed at least since 2006 (https://eprint.iacr.org/2006/145.pdf ). SIDH, upon which SIKE is based, was discussed since 2016 (https://eprint.iacr.org/2016/413 ) and proposed to NIST as SIKE in 2019. Between 2006 and just a few weeks ago, no serious flaws were discovered. And it’s not for lack of trying. Many different teams have tried, but none of the attempts seriously weakened it. As more people tried to attack it, and failed, it gained reputation as something that could possibly be the “it” quantum-resistant protocol.

SIKE, for an encryption protocol, especially for a PQC algorithm, is very small (small key sizes) and fast. Everyone was hoping that it would survive the NIST PQC contest, even if other slower and bigger finalists were selected. I was even a little disappointed when it was not immediately selected as a Round 3 finalist. Turns out NIST was right to wait and to force it into a 4th round.

SIKE Break

Then a few days ago, a team forever broke SIKE (https://eprint.iacr.org/2022/975.pdf), introducing a new, innovative, attack that the previous attackers (or creators and defenders) had not thought of. They even broke one of the smaller SIKE key sizes in about an hour using a standard laptop. No super computer was needed. Eons of time were not needed.

How did the SIKE attack work? Well, it really was mathematics being used to better factor (i.e., discover) the mathematical components used to make up the SIKE curves. Or as Dr. Steven Galbraith (https://www.math.auckland.ac.nz/~sgal018/), one of the co-discovers of an earlier technique (called GPST adaptive attack) that the new attack is based on, described the attack on SIKE like this:

“A car starts at location A and drives for a specific distance D through a dense city and ends up at location B.?You know A and B, and you want to work out the path the car took. So, drive a short distance T from A until you come to the first junction. Should you turn left or right? It would suffice to know the answer to this question: "If I turn left, is there a path of length D-T to B?"?Once you know the correct way to turn, drive a little further to the next junction and repeat the process.”

So, driving the mathematical attack car and finding the right, shortest, directions to follow breaks what was previously thought to be an unconquerable cipher…in an hour!

This is a Wow! step back moment. Even fairly old legacy protocols (e.g., DES, 3DES, etc.) don’t fall in an hour. Legacy protocols with very small key sizes (e.g., RSA-768 bit) don’t fall in an hour from an attack launched on a laptop.

What’s the Big Deal?

Part of the problem is that another previous, well-loved, leading PQC contender, RAINBOW, was broken (https://eprint.iacr.org/2022/214.pdf) in the 11th hour, likely just before it was to be released as one of the 3rd round finalists. That break required a weekend on laptop to accomplish. That was startling news and startling fast (before the even faster, lightning, quick crack of SIKE). RAINBOW’s break, by itself, before the more recent SIKE break, caused a lot of drama in the NIST PQC contest. Encryption contests are usually quite boring and any progress is made slowly on the shoulders of other previous breaks, each just a slight to moderate improvement over the other.

But both of the recent NIST PQC candidate breaks were huge jumps forward in cracking speed and simply made the ciphers unusable as PQC finalists (unless they are hugely modified and improved). Since there are other candidates and finalists that don’t need to be modified and improved to remain secure, it’s unlikely that the broken ciphers would be used even if improved and fixed. Thems the breaks.

Lots of NIST defenders, including me, like to point out that the NIST PQC process worked. Even though two beloved PQC algorithms were broken just before they were released as new NIST standards, it’s crucial to point out that they were not broken after becoming selected as NIST standards. They were caught as part of the contest evaluation process, which is why the contest is held in the first place. Since the process worked as designed, critics might be seen as quibbling over timing.

What to Do Now?

I defended NIST after the RAINBOW break, and I still do today. The process is working as designed…but even I lost a little faith after the second 11th hour break. I really don’t blame NIST at all. They are likely doing cipher investigation the right way. It’s a question of whether a “quick” contest, held only over a handful of years, can really ferret out all the potential problem ciphers. Is there a better way to select cryptographic standards?

I don’t think anyone would be surprised if another one of the NIST finalists from Round 3 or 4 were broken. A Round 3 finalist algorithm break would be far more serious because it has been announced as an official NIST PQC standard. We are supposed to be able to rely on it. If a Round 3 finalist protocol got broken, it would absolutely shake the faith of everyone in the process…everyone who still has faith in it.

It's also important to realize, as most cryptographers already know, that all non-quantum ciphers will eventually be broken. It just takes time. We expect most of our official cryptographic standards to be slowly broken over time. We expect that time to time some of our previously trusted cryptographic algorithms will quickly fall to some new, innovative attacking technique that no one else thought to use before. It happens. Personally, I think even quantum-based cryptographic algorithms will end up with flaws, hacks, and attacks. Nothing is unhackable.

So, what to do?

Become Crypto-Agile

Make sure all your software, hardware, and firmware is crypto-agile. Crypto-agile means that the cryptographic algorithm(s) used can be easily updated from one cryptographic algorithm to another without needing to replace the software, device, or firmware, or requiring an incredibly hard or complex update process. Make sure all your software, hardware, and firmware is crypto-agile. Ask your hardware, software, and firmware vendors if their products are crypto-agile. If they don’t know what that term is, educate them. Tell them you are requiring that their current or future products be crypto-agile or you’ll buy something else that is. Ciphers will absolutely change over time. Your software, hardware, or firmware doesn’t have to, if correctly designed.

And I’m hoping that all the remaining PQC finalists and candidates live long, healthy lives before they get broken. Because I’m already starting to get the feeling that the only quantum-resistant cipher we'll be left with at the end is Classic McEliece. And that would mean a whole lot of the world wasted a lot of time for something we already invented in 1978.