Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“Quantum-Safe” Crypto Hacked by 10-Year-Old PC

spectrum.ieee.org

Post reply on HN
Print view View original

21–30 of 187 posts

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#21

Post by tptacek »

eterm wrote: post #11

I look forward to this being in the next set of cryptopals.

It's a little unlikely. It's a code-able exploit with a big payoff, which is right in the wheelhouse, but then there's this that Steven Galbraith had to say about how the exploit works:

    *What is this magic ingredient?*
    It is a theorem by Ernst Kani about reducible subgroups of abelian surfaces.

    *Is there a simple way to explain the magic ingredient?*
    Nope. Go learn about Richelot isogenies and abelian surfaces.
As I understand it, even by number-theoretic cryptographic standards, the math here is abstruse. The challenges I think have done pretty well sticking to things where writing the exploit pays off with good intuitions. I guess "don't reveal auxiliary torsion points when exchanging details of an isogeny graph walk" is a useful intuition, maybe.

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#23

Post by zmgsabst »

RcouF1uZ4gsC wrote: post #8

> One reason SIKE’s vulnerability was not detected until now was because the new attack “applies very advanced mathematics—I can’t think of another situation where an attack has used such deep mathematics compared with the system being broken,” says Galbraith. Katz agrees, saying, “I suspect that fewer than 50 people in the world understand both the underlying mathematics and the necessary cryptography.” And I bet 48…

That’s not fair — at least ten work for Chinese intelligence.

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#24

Post by thadt »

tptacek wrote: post #13

If you'd like to hear someone who can barely do long division† discuss this vulnerability with one of the leading isogeny cryptographer researchers and the world's most isogeny-enthusiastic cryptography engineer, have I got a podcast for you: https://securitycryptographywhatever.buzzsprout.com/1822302/... There's even a transcript, if you want to read things like: So I watched the, uh, I watched Costello's tutorial,…

Just listened to that episode yesterday - it was great thanks! Listening to Deirdre's description of how it got ported to Sage and accelerated in short order - so she could break it in a few minutes on her laptop - in Python, totally reminded me of the line from Iron Man.

"Tony Stark Was Able To Build This In A Cave! With A Box Of Scraps!"

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#26

Post by bem94 »

oipoloi wrote: post #2

"To me what is most surprising is that the attack seemingly came out of nowhere,” says cryptographer Jonathan Katz at the University of Maryland at College Park, who did not take part in this new work. “There were very few prior results showing any weaknesses in SIKE, and then suddenly this result appeared with a completely devastating attack—namely, it finds the entire secret key, and does so relatively quickly with…

> To me what is most surprising is that the attack seemingly came out of nowhere,

This wasn't my understanding at all. The specific issue in isogeny based cryptography which the attack exploits has been a source of worry in the cryptographic community for a while, and is exactly why NIST put SIKE in the "for further consideration & crypt-analysis" category when making their standardization decisions.

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#27

Post by jabbany »

mixedbit wrote: post #9

I wonder if someday we will see someone generating all the bitcoins on a laptop. How the article says, the math behind most cryptosystems were never proven to be unbreakable, it is just believed to be so, because no one managed to show otherwise.

Probably both yes and no.

As of right now bitcoin depends pretty heavily on SHA256 and with hash functions being quite important cryptography primitives, there's always ongoing work on breaking them (tremendous upside to anyone who can manage to break common ones), so it's pretty feasible that eventually it will be broken. (We've already seen the fall of MD5 and SHA-1 in recent-ish years)

However, cryptocurrencies are a human system as much as they are a computing technology. If weaknesses start being discovered SHA256 or the EC signing of bitcoin, then in all likelihood they'd just fork the chain and upgrade the hash or signing mechanism.

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#28

Post by RL_Quine »

jabbany wrote: post #27
mixedbit wrote: post #9

I wonder if someday we will see someone generating all the bitcoins on a laptop. How the article says, the math behind most cryptosystems were never proven to be unbreakable, it is just believed to be so, because no one managed to show otherwise.

Probably both yes and no. As of right now bitcoin depends pretty heavily on SHA256 and with hash functions being quite important cryptography primitives, there's always ongoing work on breaking them (tremendous upside to anyone who can manage to break common ones), so it's pretty feasible that eventually it will be broken. (We've already seen the fall of MD5 and SHA-1 in recent-ish years) However, cryptocurrencies ar…

It’s pretty unlikely that sha2 will ever broken in a way which actually has a meaningful security impact to bitcoin, especially considering that almost every value in the system is sha2(sha2()) which nullifies a lot of attacks against hashes which need careful control of the input. Some newer tools in the system use a single hash (it’s unclear why a double one was used in the first place), but all the same it remains highly unlikely.

Complete breaks of ECDSA are likely to be devastating as many keys in the data are re-used hundreds of thousands of times, but a weakening of it can be mitigated by moving to a new signature standard, which isn’t even consensus incompatible due to the upgradability built into the script language.

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#29

Post by Beldin »

mixedbit wrote: post #9

I wonder if someday we will see someone generating all the bitcoins on a laptop. How the article says, the math behind most cryptosystems were never proven to be unbreakable, it is just believed to be so, because no one managed to show otherwise.

That's the one actual value of bitcoin / cryptocurrencies: we can be fairly sure that no one broke the used hashing algorithms (1). The valuation of these coins is such that not just any individual, but even a state actor would just go for it.

(1) to such a degree that it would allow the attacker to create new blocks at will.

Assume 1 bitcoin is $50k; break it only once a day and make over 15 million × block reward a year. I doubt many governments could resist.

Re: “Quantum-Safe” Crypto Hacked by 10-Year-Old PC

#30

Post by Retr0id »

czbond wrote: post #10

You KNOW they first had to do this in the normal way (large scale, distributed servers)..... and cracked it in like a second. Then for grins, the engineer HAD to say "I wonder if I could do this on my old Mac mini". And it worked. And for embarrassment of the original design, the story, and clickbait... they did it on that old machine

Almost certainly not. They'd have started prototyping the attack with small numbers, and once it started working, slowly scaling it up.
Post reply on HN