SIKE Broken

SIKE is one of the new algorithms that NIST recently added to the post-quantum cryptography competition.

It was just broken, really badly.

We present an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH), based on a “glue-and-split” theorem due to Kani. Our attack exploits the existence of a small non-scalar endomorphism on the starting curve, and it also relies on the auxiliary torsion point information that Alice and Bob share during the protocol. Our Magma implementation breaks the instantiation SIKEp434, which aims at security level 1 of the Post-Quantum Cryptography standardization process currently ran by NIST, in about one hour on a single core.

News article.

Tags: algorithms, cryptanalysis, cryptography, encryption, NIST, quantum computing

Posted on August 4, 2022 at 6:56 AM • 26 Comments

Comments

Peter Galbavy • August 4, 2022 7:54 AM

I read the article on The Register yesterday and while I haven’t the first clue about the underlying math it read to me like someone who’s installed an amazingly fancy and highly secure (oxymoron alert) digital door lock but forgot to fir the door itself into the frame.

Yetti • August 4, 2022 7:59 AM

Btw, is codecrypt utility still secure enough to use it?

codecrypt is a GnuPG-like Unix program for encryption and signing that only uses quantum-resistant algorithms:

McEliece cryptosystem (compact QC-MDPC variant) for encryption.
Hash-based Merkle tree algorithm (FMTSeq variant) for digital signatures.

Please, feel free to express your thoughts.

Clive Robinson • August 4, 2022 10:27 AM

@ Peter Galbavy, ALL,

“while I haven’t the first clue about the underlying math it read to me like someone who’s installed an amazingly fancy and highly secure”

The fundamental protocol for SIKE is “Supersingular Isogeny Diffie-Hellman”(SIDH). Which is a tads difficult to fully explain even by mathmaticians…

The problem is that even mathmaticians can be unaware of the more referified parts of their art…

So it turns out it was not “secure”, and it had been known by some mathmetitians how to attack it since the late 1990’s…

Which is kind of a decade or two and some before anyone decided to use SIKE as a one way function for crypto. Which kind of makes it realy “face palm” embarrassing…

From the ARS Technica article,

“The research paper published over the weekend shows how SIDH is vulnerable to a theorem known as “glue-and-split” developed by mathematician Ernst Kani in 1997, as well as tools devised by fellow mathematicians Everett W. Howe, Franck Leprévost, and Bjorn Poonen in 2000. The new technique builds on what’s known as the “GPST adaptive attack,” described in a 2016 paper. The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians.”

But as I said the other day this is not the real issue…

The issue is “One Way Functions”(OWFs) that have “Secret trap doors” to make them appropriate for Key Exchange” and “signing”.

We do not realy know if OWFs realy exist in a form that is “Quantum Computing”(QC) proof.

Firstly because there is no proof that the supset of OWFs suitable are actually secure. Secondly if we do get QC’s up and running, what new algorithms might pop up to ruin a cryptographas day…

Perhaps rather than chase “Post Quantumn Algorithms” that we have no idea how long before they get broken, we should actually take a different direction and look at how to do the “keye exchange” and “signing” functions in entirely different ways…

David in Toronto • August 4, 2022 11:09 AM

The statement “The math behind the latest attack is guaranteed to be impenetrable to most non-mathematicians” is a massive understatement. A bit like the dentist saying, this will be a bit uncomfortable.

I know several people who, while not career level mathematicians, have used and explored advanced maths throughout their careers and have opined on the rather significant effort to understand the math.

I await further insight from people more capable than I. 🙂

@Clive – good questions. Of course the next question is what might a new way to do key exchanges even look like. The old ways of exchanging keys scales poorly (to say the least).

The main problem is Shor’s not Grover’s. Double all key lengths and symmetric algorithms will continue to work. Asymmetric crypto on the other hand …

Notably a couple of weeks ago when NIST announced some of their PQC picks, it left open the asymmetric algorithms which is what we most need. A candidate algorithm face-planting is one thing, having an announced algorithm fail is quite another. The last time this happened was with Format Preserving Encryption which is a much more limited use case. Maybe this needs more time?

ADan • August 4, 2022 11:49 AM

@Yetti,

Btw, is codecrypt utility still secure enough to use it?

codecrypt is a GnuPG-like Unix program for encryption and signing that only uses quantum-resistant algorithms

I wouldn’t recommend using anything with only post-quantum algorithms. It’s more common to combine them with better-tested methods like Elliptic Curve Cryptography, such that both algorithms need to be broken to break the security. While ECC etc. are theoretically vulnerable to quantum computers, they’re believed to be safe from all existing computers—which, as you’ve seen, is harder to say about these newer post-quantum algorithms. The general belief is that no quantum computer exists, nor will in the next decade or so, that can crack any strong cryptography much faster than classical computers.

Additionally, codecrypt is unmaintained.

I’m not familiar with fmtseq, but took a quick look at the paper and some references. It looks to be based on the Merkle signature scheme, for which it’s important not to reuse keys (although the papers are not explicit about this, or about what happens if we do). That is, it requires the signer to maintain state and update it after every signature, which is something we don’t really want: we’ve seen severe cryptosystem failures in the past from improper entropy or state-maintenance. I wonder whether such methods could be (or already have been?) made deterministic in some way, or random-but-stateless based on a very low probability of leaks.

That said, Merkle’s scheme is well understood and believed to be secure when used correctly. I don’t know if that generalizes to fmtseq. I also don’t know enough about MDPC McEliece to comment, except to note that codecrypt’s original McEliece algorithm was broken.

Most people should probably stick to something more traditional, and move to a smartcard or hardware security module (HSM)—or multiple of these with secret-sharing—if they want to improve security; and, if possible, keep them offline. Under realistic threat models, attacks based on improper patching or zero-day exploits, or idiocy like checking private keys into git(hub), tend to be much more worrying than quantum attacks.

SpaceLifeForm • August 4, 2022 12:04 PM

@ Clive, Winter, ALL

Kolmogorov complexity and One-way Functions

‘https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/

Conversely, if calculating the approximate time-bounded Kolmogorov complexity is too hard to solve efficiently for many strings, then Liu and Pass showed that true one-way functions must exist.

Quantry • August 4, 2022 12:22 PM

“…how to do the “key exchange” and “signing” functions in entirely different ways…”

Key exchange without a recognizable middle man or process? Sounds like number stations from various indistinguishable sources. Internet white-noise, plus less secrets: wagingpeace.org

Winter • August 4, 2022 2:25 PM

@SLF

Kolmogorov complexity and One-way Functions

I believe someone posted a link to the original paper here some time ago. It is still sitting in my reading list. I think I will move it to the top of the list.

David in Toronto • August 4, 2022 2:49 PM

Would this be it https://eprint.iacr.org/2020/423.pdf

SpaceLifeForm • August 4, 2022 2:51 PM

@ ALL

Symmetric and Asymmetric

I do not trust AES or RSA.

Move to ECC with a SafeCurve.

There are reasons why there are players that want you to chase the PQC Ghost.

It is to distract and waste your time.

We need Asymmetric PKI of course, but we need to know that it is not MITM-ed.

There are alternative methods for Symmetric, but if the TLS Handshake is MITM-ed, then that will fail also.

We definitely need better internet cryptography protocols. We need to be able to detect a MITM and treat it as a double bit error.

You must assume a MITM at all times.

Clive Robinson • August 4, 2022 5:09 PM

@ SpaceLifeForm, ALL,

Re : Move to ECC with a SafeCurve.

Err the maths behind this attack on SIKE is also being looked at for breaking ECC (read ARS article for more details).

So far the search for an ECC attack of use is “ongoing”. This attack on SIKE is almost certainly going to renew attempts to break ECC. Doing so would give the successful person(s) a “Golden Ticket” C.V.[1]

Let’s put it this way I suspect ECC now has a very short shelf life… Maybe half a decade at most life left would be my advice to the cautious. So looking for a replacment should begin right away.

It could be a heck of a sight less, as there is a chance a successful attack may already have been discovered but not yet recognised. So it might come fast very fast.

Hency my earlier comments about thinking on how to replace the curent asymetric “Key Exchange” and “Signing” systems.

Because if we loose them before we replace them to a non QC algorithm then it’s going to be brutal very fast…

Think no secure online,

1, Banking / Finance.
2, Online Shoping/Commerce.
3, Software Patching.
4, Secure Communications.
5, Privacy.

You might remember I’ve been talking off and on about replacing privacy wrecking CA heirarchics for years, as well as private/secure “Rendezvous Protocols”. Because it’s been kind of obvious that Asymetric Crypto has a serious flaw in the “Secure Trap Door” assumption that was always weak. Worse the statments of David Deutsch[2] in the mid 1980’s about “Quantum Computing”(QC) and his proof that it was going to be significantly improved compared to “Clasical Computing”(CC) was a large “Red Flag”…

Even our host @Bruce Schneier some time ago (around AES comp time ending) made the point we realy needed to stop playing with crypto algorithms and get on with the far harder task of “Key Managment”(KeyMan). Which even today is mostly not done (seen by some as either impossible or a career killer).

The best we have for Private/Secure key transfer in emergancies is the provably secure yet both fragile and awkward to scale “One Time Pad”.

Every system so far thought up that does not use asymetric crypto, needs a “Secure Side Channel” to at the very minimum set up a “Root of Trust”.

A Two-Party “Root of Trust” transfer without OWF’s with Secure Trap Door functions is currently assumed not to scale[3]. The alternative three or more party systems are provably not secure under the usuall assumptions (it’s why we spend time talking about “End To End Encryption”(E2EE)).

[1] As some know the sort of mathamatician who is most likely to do this is of PhD Research age, so upto middle to late 30’s. So a “Golden Ticket” is their most likely route to “secure academic employment” for the rest of their life.

[2] Basic bio of David Deutsch,

https://quantumzeitgeist.com/david-deutsch-the-father-of-quantum-computing-but-who-is-he/

[3] I’m of a different opinion, think of three impartial entities, that randomly select some “Number Used Once”[nonce] and send them to the two parties that wish to communicate. The two parties then use those points as being on the circumference of a circle and use the radius or center they calculate as a symetrical key. This system shows it is possible to have a system where none of the impartial third parties can know what the key is. But also that the scaling problem can be significantly reduced, to the point where OTP can be used by individuals to the impartial third parties.

Winter • August 5, 2022 12:47 AM

@David in Toronto

Would this be it

That is the one.

Bernie • August 5, 2022 1:58 AM

@Clive Robinson

Is the https://www.schneier.com/blog/archives/2022/08/sike-broken.html/#comment-408576 really by you? If so, I hope you are feeling ok. Granted, I don’t read every comment of every post — and I’ve been having some cognitive difficulties — but that comment doesn’t quite match what I’m used to in your comments. Maybe you were simply in a hurry and didn’t have time to proofread it. I just want to make sure no one it trying to impersonate you.

JokingInTuva • August 5, 2022 2:16 AM

@Clive

“we should actually take a different direction and look at how to do the “keye exchange” and “signing” functions in entirely different ways…”

But what “other ways” are you thinking about?
Just leaving the “mathematical based Asymmetric Crypto” forever? And going for an “all-symmetric” Crypto world (Key Exchange: PPKs, KDFs, etc… Signing: HMACs, CMACs, etc…)?
(this seems quite hard from current perspectives: PKIs and so on…)

Or looking for other kind of asymmetric mathematical challenges?
(but this is the current NIST PQC approach: lets go for othe mathematical challengas…just not being hit by Shor & Co)

For the Key Exchange we still have the QKD shot, but it still relies in Symmetric Authentication.

Clive Robinson • August 5, 2022 4:28 AM

@ Bernie,

Re : Impersonation.

Yes it’s me. I’m in part changing the way I post, as the blog software has problems as you might have seen with @SpaceLifeForm testing away.

If a comment gets “held for moderation” the probability is quite high that it will not ever get to see the light of day…

So that calls for “re-commenting in parts” which is not just messy but very time consuming (as well as I suspect upsetting the other readers).

Clive Robinson • August 5, 2022 7:09 AM

@ All,

Re : One Way Functions (OWFs)

In crypto there are two basic types of OWF used.

1, OWFs with reversing trap-doors.
2, OWFs with no known reversals.

They are both mapping functions, however the first has a hidden pattern in the map that alows it to be easily reversed. If you have the key to that hidden pattern then it’s not a one way function to you.

Currently the first type are what are used in asymetric crypto and are “maths based”.

The second type are approximations of “random maps” where there should be no intentional hidden reversing patterns. Such maps can be done by logic or maths as long as certain criteria are met (like complexity, avalanche ettect, etc). They are used in the rounds and similar of symetric crypto.

As far as Quantum Computing (QC) is concerned the non-random maths based OWFs with hidden reversing are exceptionaly vulnerable. Whilst the OWFs without hidden reversing appear so far not to be as vulnerable.

From a 20,000ft perspective you might assume that it is the intentional reversing pattern or Trap-Door that makes the major difference… As always things are a little more complicated than that.

But the point is, this attack clearly demonstrates how quickly an assumed secure OWF with intentional trap door becomes vulnerable, and all that is based on it –which is almost the entire web– becomes vulnerable in hours, not years.

It’s going to take decades to find an alternative if the current progress on PQC is anything to go by, which is why we should be actively exploring either new ways or alternatives to,

1, Key Exchange
2, Signing

That are based on OWFs with intentional trap-door reversing functions.

Can we do it? That is an open question, thus I’d favour looking at alternatives.

For an alternative to work it needs two basic things to be met,

1, Easily scalable.
2, Secure from third party channel.

So that some form of “root of trust” can be established.

The laws of physics have as far as we know solved the second problem with “Quantum Key Distribution”(QKD) but it is currently not even remotely scalable in any meaningful way outside of a 1-10kM area. Yes I know you can do it through a satelite in LEO but that is not scalable to every home PC user, office desktop user in a small town or even highstreet, and it won’t work with mobile smart devices which we are all rapidly moving towards.

There are other parts of the problem solved, but we’ve not yet worked out a way to link them up effectively for static users, as for mobile…

I can tell you how I might do it but whilst it is scalable and will work with mobile devices it has fragility issues security wise with “betrayal” to third parties by third parties.

SpaceLifeForm • August 5, 2022 7:14 AM

@ Clive

re: Circle Points Crypto

While it could work, it is a non-starter to me.

It seems like it just makes the problem worse.

If Alice and Bob, need to have a shared secret key, they can do that with PKI. But, they have to hope it is not MITM-ed.

But, with the Circle Points Crypto, you have made it more complex to use, and created additional points for traffic analysis to come into play. Maybe Alice and Bob do not care if others know they are communicating, but maybe they do. It depends upon their respective threat models.

I can not justify turning a 1:1 problem into a 2:3 problem.

If I am Alice or Bob, how can I trust Larry, Moe, and Curly to flip coins and report results accurately?

Furthermore, how would it be coordinated without additional traffic? How would Larry know to send his Nonce to BOTH Alice and Bob? He would have to know, which then leads to a possible betrayal problem in that Larry could reveal that Alice and Bob are communicating.

Alternatively, it would make more sense for the Larry, Moe, and Curly to just broadcast al la Numbers Stations, and Alice and Bob have an agreed upon ruleset that says, for example, we will grab N bits from Larry every day at a certain time, N bits from Moe at a different time, and N bits from Curly at some time, and use them to construct their shared secret key.

If Eve does not know what the ruleset is that Alice and Bob are using, Eve will have a difficult time.

Security is recursive. I would not make the protocols more complex.

Clive Robinson • August 5, 2022 8:55 AM

@ SpaceLifeForm,

You’ve made a fatal assumption with,

“If Eve does not know what the ruleset is that Alice and Bob are using, Eve will have a difficult time.”

But with no prior contact how do Alice and Bob securely establish “the ruleset”? Which after all forms part of the root of trust…

If they can securely transfer part of the root of trust, then they can securely transfer all of it at the same time.

Remember three things,

1, PKI is assumed compromised / broken.
2, Alice and Bob have never ever met or interacted before, so have zero knowledge and zero trust.
3, They have no secure side channel.

TimH • August 5, 2022 9:37 AM

Isn’t there an elephant in the room here? This is an algorithm that “NIST recently added to the post-quantum cryptography competition”. Now they MUST due some checks for joke entries, but if the fault in this approach has been known for 2 decades, a question is begging.

If I submitted ROT13, would that pass the gate and make the list?

Bernie • August 5, 2022 10:44 AM

@Clive Robinson
Thanks for the info. I’m glad it is you. Someone impersonating you here would be worse than someone impersonating Bruce. Worse in the sense that I imagine a Bruce impersonator would be detected sooner. After all, I don’t come here just for the Schneier and the calamari. (Using my incorrect pronunciation, spoken out loud that sounds like a squid gave a blackeye to a cook when the squid refused to become an appetizer, which ironically is the basis for a new movie-plot threat.)

SpaceLifeForm • August 5, 2022 11:29 AM

@ Clive

re: how do Alice and Bob securely establish “the ruleset”?

This is the problem in a nutshell.

I realize this is a very hard problem.

I am just saying to not make the problem more complex.

Complexity is just going to add more attack surface, and more room for human error.

SpaceLifeForm • August 5, 2022 1:51 PM

@ TimH

I would go with ROT2, ROT3, ROT5, ROT7, ROT11, ROT13, ROT17, ROT19, and ROT23.

Your secret sauce is the order.

You may be able to get a Software Patent.

Magic 🙂

Clive Robinson • August 5, 2022 3:45 PM

@ SpaceLifeForm, TimH, ALL,

Re : ROT N

Ahh the good old days pre the Web, of bad/course jokes on UseNet being obfuscated by ROT13 back in the 1980’s[1]. So common that many could read it by sight…

Apparently still in use by Microsoft in the Registry[2]…

But ROT like IntADD, XOR, and bit shifting with carry around are linear and will “sum up and roll over” just like the mechanical odometer and “trip-meter” in a car where those old enough used expressions like “Distance on the clock”.

But… Even if you mix ROT, IntADD and XOR operators up you end up with a simple mapping function, or substitution cipher. Therefor the only security gained on the map is to make the alphabet size to large to build look up tables, subtables, or their equivalent. So the usual way of getting security is to pre-mix or “whiten” either the input or output with one of the operators, and another value such that it changes with every use of the mapping function. You can see this if you draw it out, and it is the basic idea behind the Feistel Round[3] that is used in many block ciphers.

Whilst the Fiestel Round and it’s many variants are common, usually the “round subkeys” remain constant for any given block cipher key.

A little thought will make you realise that each round is a mixing function the same as used in a stream cipher… Thus you could ask yourself the question of “What if you actually used a stream generator for each function?”

One upside is you can significantly reduce the number of rounds. A second is that in hardware you can run stream generators in parallel and thus get a very high speed of operation…

[1] For those young enough not to know, the old jokes, the result of multiple ROTs is a single ROT of the sum of the individual rots mod the alphabet size.

So ROT13, ROT13 is ROT26 with the Latin alphabet size of 26 gives ROT0 or the ciphertext is the plaintext.

[2] Dider Stevens even wrote a decoder for it back in 2006,

https://blog.didierstevens.com/2006/07/24/rot13-is-used-in-windows-you’re-joking/

[3] See more on Horst Feistel’s work,

https://en.m.wikipedia.org/wiki/Feistel_cipher

David Leppik • August 6, 2022 2:26 PM

There seems to be a lot of talk about how impenetrable the math is for SIKE. That probably contributed to it getting so far before being thwarted so thoroughly.

One advantage of RSA and other classic algorithms is that they require little more than high school math. Using well-understood math reduces the places a flaw can hide, plus it also reduces the barriers to entry for budding cryptoanalysts. Looking at the lattice-based approaches, they aren’t exactly easy, but they appear approachable to anyone with a math major. It’s basically polynomial equations using integer constants. These are among the NIST finalists that are still in the running.

TimH • August 6, 2022 7:36 PM

@David Leppik

Again, the issue here per young Clive, “The research paper published over the weekend shows how SIDH is vulnerable to a theorem known as “glue-and-split” developed by mathematician Ernst Kani in 1997, as well as tools devised by fellow mathematicians Everett W. Howe, Franck Leprévost, and Bjorn Poonen in 2000. The new technique builds on what’s known as the “GPST adaptive attack,” described in a 2016 paper.”

So, why didn’t the experts that NIST employ know that the proposal was flawed?

Standards involve trust of underlying expertise. Security standards… a lot more trust. If NIST doesn’t produce an autopsy plausibly explaining a mea culpa, that trust should not be deserved.

Clive Robinson • August 7, 2022 3:15 AM

@ TimH, SpaceLifeForm,

Re : Pachyderm Squatters

I’m still wondering when “Robbins pentagons”[1] will be looked at as a candidate one way function 😉

[1] Named after mathmetician David P. Robbins back in 2008, in the paper “Cyclic polygons with rational sides and area” authored by Ralph H. Buchholz and James A. MacDougall.

https://en.m.wikipedia.org/wiki/Robbins_pentagon

Robbins Pentagons have some interesting properties of which one springs out from the papers title, which is that every Robbins Pentagon is scaled from a base where it’s area and side lengths are all integers, less obvious is that there are also an infinite number of the bases. When you consider Crypto is after all being about integers and the mappings between them. Further consider that a circle of radius and center can be described by any three points (including the degenerate circle of zero area you might call a straight line). As some know the circle is a basic example of a secret sharing system that can be used for a key exchange system.

SIKE Broken

Comments

Leave a comment Cancel reply