Post-quantum encryption contender is taken out by single-core PC and 1 hour
arstechnica.com
arstechnica.com
I don't think that follows from the published attack at all.
As Bruce Schneier wrote nearly a quarter century ago "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break."[0] 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.
But people come up with cryptosystems all the time. How do researchers decide which ones are worth attacking? And, how do we know that enough researchers have spent enough time attacking any given cryptosystem to conclude that, if none of them have found a flaw by now, then it's plausible that the system might hold up for another 10-20 years or so in widespread use?
One of the best ways we've come up with is, 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 - rather than finding a weakness in a system no-one cares about and getting nothing.
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 in systems before they start to get widespread use.
[0] https://www.schneier.com/crypto-gram/archives/1998/1015.html...
Maybe not - but from a layman perspective, the fact that a supposedly quantum-computing-proof algorithm isn't even classical-computing-proof does sound worrying.
Imagine someone said a cage is tiger-proof but then a house cat goes and destroys it in an hour :)
I guess the field will take a long time to mature, which is OK since practically useful quantum computers are probably far from being available.
or just squeezes out between the bars. "Wait, that's cheating..."
> We should try to come up with Tiger-proof cages
> This one might work
> Nope, it fails in this way
> Ok, onto the next idea....
Taking that line of reasoning further, given Godel's Incompleteness Theorem you could say that mathematics as a field will never have matured.
Worse, crypto is defined by essentially having the added requirement to at least not be the weakest link in keeping jewels locked in a safe. In that sense the addition of axioms becomes a liability in a way they are not in broad math.
Put another way, math as a field was able to mature because it lacked this hard requirement that crypto has. If mathematicians suddenly decided add this requirement of jewel-keeping to math broadly then-- bam-- math instantly becomes the same "immature" field that crypto currently is.
https://www.quantamagazine.org/the-scandalous-history-of-the...
We have some problems (factorization, and discrete log) that no one has found a way to efficiently solve on a Turing machine; but we don't really have a solid reason to think these problems are difficult. All we know is that our best mathamaticians have been stuck on them for generations.
The bigger problem is that even these reductions to assumed difficult problems represent only a small portion of cryptography. We prove things like AES and SHA512 are secure by publishing them and waiting a few years to see if anyone publishes a break. No meaningful reduction to well researched problems, just a hope that we wont discover we missed something after making it a standard.
Be humble to admit your mistakes or shortcomings and back to work trying to learn from what went wrong, we need this kind of people.
This was an algorithm that was in the process of being evaluated. It seems like the process worked the way it should have and is weeding out the algorithms that don't work. There is nothing wrong with trying an idea that doesn't work out!
Their concern that something that made it through multiple rounds turned out to be so easily broken is very valid, but as of today I wouldn't refer to SIKE as a "contender" anymore.
Falcon, SPHINCS+ were also standardized btw, not just Dithium.
If there are any others, I'd like to know.
There are plenty of real world things I can be pretty confident won't exist in 100 years... For example we won't be able to make an atom-perfect cloning machine. We won't have solved teleportation for people, we won't have cured all diseases.
Well I just want an encryption algorithm we won't have broken into.
You have to consider making it cost prohibitive in that target future for a near state actor to break it using classical computing, QC (maybe - it's still an unsolved manufacturing problem), FPGAs, and ASICs.
10M rounds of AES512 perhaps or perhaps not enough.
For digital signatures, the 3 standardized schemes are Falcon, Dilithium, SPHINCS+.
Falcon/Dilithium can be used in blockchains though they are much larger compared to elliptic curve ones. SPHINCS+ is way too large.
There is likely going to be a newer NIST program for signature schemes with smaller signature size.
Now, did the NSA find the attack on their own, kept it secret and hoped for standardization? One can only speculate.
Also, the NSA does not always try to backdoor everything like they did with DUAL_EC_DRBG. For instance, they modified the S-box of DES during the NIST standardization and refused to elaborate on why. The reason was later found, as people invented differential cryptanalysis and found that the NSA-modified S-box was resistant to it, when the original S-box was not: the NSA actually made DES stronger on purpose.
https://arstechnica.com/information-technology/2013/09/the-n...
https://www.theregister.com/2021/11/29/china_quantum_ai_offe...
Or as the Californian youth used to say: SIIIIIIIKE
It turns out that it was appropriately named!
Florida Atlantic University
Amazon
IBM Research
Microsoft, Microsoft, Microsoft, more Microsoft
Lousiana Tech University
Texas Instruments
yikes... these are who we already rely on every day to keep our data, our services, and our softwares safe and secure.
Even if they were the same people, the skill sets of each job are quite different. Being flawed at inventing new algorithms doesn't mean you're flawed at applying state of the art security to existing software.
"One unexpected facet of the attack is that it uses genus 2 curves to attack elliptic curves (which are genus 1 curves). A connection between the two types of curves is quite unexpected. To give an example illustrating what I mean, for decades people have been trying to attack regular elliptic curve cryptography, including some who have tried using approaches based on genus 2 curves. None of these attempts has succeeded. So for this attempt to succeed in the realm of isogenies is an unexpected development."
Also, while the attack here is devastating there is no blame to put on SIKE authors: the field is immensely vast, complex and abstract, no one can know everything. The attack relies on a somewhat recent result that is definitely not classical crypto textbook.
Furthermore the cryptosystems used by these companies are the ones that have been tested and standardized through the years, not the brand new algorithm designed by cryptographers (as new algorithms must be scrutinized first).
Also, as another commenter suggests cryptographers are not the ones in charge of the actual implementation at their companies.
Finally, you are making a big confusion between cryptography and security.
I think you found the offender.