Post-quantum algo ‘SIKE’ dead: Did math geeks find key-encap back door?

Here’s more on NIST’s search for post-quantum cryptography (PQC): This week, is it in trouble? Breathless headlines would have you believe it, because researchers found a way to easily break the SIKE key encapsulation algorithm.

But no: SIKE wasn't one of the algorithms chosen by NIST last month. It was, however, one of the candidates for the next round of approvals. Devs are still advised to ensure they have “crypto agility”—the ability to swap in new algorithms with ease.

Researchers Wouter Castryck and Thomas Decru are eligible for a chunky bug bounty. In this week’s Secure Software Blogwatch, we’re glad to see the system is working, not broken.

Your humble blogwatcher curated these bloggy bits for your entertainment. Not to mention: Freedom.

[ Get key takeaways from a survey of 300+ professionals on software security. Or, download the full report: Flying Blind: Firms Struggle to Detect Software Supply Chain Attacks ]
 

NIST nixes PQC postulant

What’s the craic? Laura Dobberstein reports—“NIST's nifty new algorithm looks like it's in trouble”:

“Vintage processor”
One of the four encryption algorithms the US National Institute of Standards and Technology (NIST) recommended as likely to resist decryption by quantum computers has had holes kicked in it by researchers using a single core of [a 2013] Intel Xeon. … The Supersingular Isogeny Key Encapsulation (SIKE) algorithm was chosen by NIST just last month as a candidate for standardization, meaning it advanced to an extra round of testing.
…
Microsoft – whose research team played a role in the algorithm's development along with multiple universities, Amazon, Infosec Global and Texas Instruments – set up a $50,000 bounty for anyone who could crack it. … Wouter Castryck and Thomas Decru claim to have done just that.
…
Microsoft described the algorithm as using arithmetic operations on elliptic curves defined over finite fields and compute maps, also called isogenies, between the curves. Finding such an isogeny was thought to be sufficiently difficult to provide reasonable security – a belief now shattered by [a] nine-year-old … vintage processor.

 
And Dan Goodin adds in—“Leave it to mathematicians to muck up what looked like an impressive new algorithm”:

“SIKE is dead”
Last month … NIST, selected four post-quantum computing encryption algorithms. … In the same move, NIST advanced four additional algorithms as potential replacements, pending further testing. [SIKE] is one of the latter four additional algorithms. The attack has no impact on the four PQC algorithms selected by NIST as approved standards.
…
SIKE is the second NIST-designated PQC candidate to be invalidated this year. … The entire process requires only about an hour [of CPU] time. The feat makes the researchers … eligible for a $50,000 reward.
…
The version of SIKE submitted to NIST used a single step to generate the key. A possible variant of SIKE could be constructed to take two steps. … David Jao, a professor at the University of Waterloo and co-inventor of SIKE … said that it’s possible that this latter variant might not be susceptible to the math causing this breakage. For now, though, SIKE is dead.

 
ELI5? Steven Galbraith politely declines your request to explain like you’re five—“Is there a simple way to explain?”:

“We should keep our minds open”
Nope. Go learn about Richelot isogenies and abelian surfaces.
…
The theoretical foundations of the attack are described in a paper by Kani from 1997 (and … by Howe, Leprévost and Poonen from 2000). So in some sense the attack could have been noticed at any time. But … this is not an attack one is going to discover by thinking only about isogenies between elliptic curves. The attack deeply exploits Richelot isogenies and products of elliptic curves and I doubt the attack can be expressed meaningfully without that language. This is the power of generalisation and extension. So what was necessary to find the attack was to have a community of scholars studying “esoteric” subjects like extending isogeny crypto to abelian surfaces.
…
The correct response to this is not to attempt to minimise the impact, nor to reflexively declare the subject dead. Instead, we should keep our minds open and let the mathematicians work out the implications, wherever they lead.

 
The correct response? As Karellen explains, the system is actually working as intended:

“This is the kind of result [it] is meant to produce”
The only way to get good cryptosystems is to get as many cryptographers as possible, outside of the ones who invented them, to attack those cryptosystems in as many ways as they can think of.
…
One of the best ways we've come up with is [to] have people submit a bunch of proposals to a regulatory agency (like NIST), who then with advice from academia and industry create a shortlist of likely candidates, and finally advertise those as the ones that as many people as possible should try to break. And for any who do find weaknesses, you get to publish a paper about it and receive a bunch of recognition.
…
This is the kind of result that standardising encryption algorithms is meant to produce. It's meant to leverage widespread expertise to find the weaknesses … before they start to get widespread use.

 
How did we get here? @KennWhite rues the day:

What a strange path we've taken: In 10-20 yrs (or 50, or never) we might have practical quantum computers, so let's roll out replacement PQ crypto now. Which could be trivially broken today, on a laptop.
…
Obviously [I’m] glad that sunlight helped focus the analysis and it was caught prior to standardization. [But I’m] Deeply skeptical we're anywhere short of multiple decades from a practical general purpose quantum computer capable of non-trivial factoring.

 
And the skepticism runs deeper. WaffleMonster sees the dead hand of No Such Agency:

This is the whole point of post quantum crypto. Intelligence agencies have had four decades to break RSA and have mostly failed.
…
Now they want to social engineer the world into accepting complex gibberish justified by FUD—merely an unfalsifiable always true notion that something "could" happen in the future. Once there is a post quantum scheme they will pursue their goal of demanding everyone abandon RSA for the new scheme thru government sponsored standardization / regulatory means and everyone will be compelled to fall in line.

 
And deeper! Daniel J. Bernstein—@HashBreaker alleges a deliberate choice of parameter opened a secret back door:

“Throwing away a secret isogeny”
SIKE wouldn't have been broken (yet?) if the proposers had applied a secret isogeny to build a standard starting curve. The attack would instead have been showing that the secret is a back door.
…
Compare to NIST's submission criteria: "To help rule out the existence of possible back-doors in an algorithm, the submitter shall explain the provenance of any constants or tables used in the algorithm." Is it true that explaining the SIDH/SIKE constants rules out back doors?
…
[They] had the option of following a different path (ahem), generating the standard A at random by applying and then throwing away a secret isogeny. What's interesting about this is that then SIKE wouldn't (yet?) be broken. In other words … pushing for elimination of back doors created a SIKE weakness that could have been avoided otherwise. Now think about this situation from the perspective of attackers who secretly knew the weakness from the outset.

 
But it’s not a “sky falling” moment? No, but klyrs still sees it as a teachable moment:

Still makes a fun story, though. And, if nothing else, it should serve as a warning: Even professional crypto experts make weak crypto when they're trying their hardest. Don't roll your own!

 
Meanwhile, ColdWetDog shivers and shakes:

I tried to look up 'isogeny' — that didn't go well, even after two more cups of coffee. I can barely type now and I'm not any smarter.

 
And Finally:

Rest in campy peace, Nichelle Nichols

Hat tip: Happosai

Previously in And finally

You have been reading Secure Software Blogwatch by Richi Jennings. Richi curates the best bloggy bits, finest forums, and weirdest websites … so you don’t have to. Hate mail may be directed to @RiCHi or ssbw@richi.uk. Ask your doctor before reading. Your mileage may vary. E&OE. 30.

Image sauce: Natalia Yakovleva (via Unsplash; leveled and cropped)