14 ms·
“Quantum-Safe” Crypto Hacked by 10-Year-Old PC
- deleted 4y ago[deleted]
- oipoloi 4y ago"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 without any quantum computation."
- moffkalast 4y agoWell they for sure have picked a very ironic name for it. "The vault is completely unhackable." "SIKE"
- chrisweekly 4y ago+1, funny -- but for the sake of non-native English speakers, FTR, it's pronounced the same as "psych" and is colloquial for a sarcastic "ha-ha, just kidding"
- formerkrogemp 4y agoI often don't think to explain these things, so thank you for taking the time to explain to others the context.
- gwright 4y agoFor additional cultural context, I think this usage was popularized by Eddie Murphy in Delirious (NSFW language: https://youtu.be/Ft4kEk5CHrE https://youtu.be/Ft4kEk5CHrE, you'll want to listen to at least 2:15)
- earleybird 4y agoGiven that Eddie is telling a story from his youth it's probably fair to say it was in common use 10+ years earlier - which is consistent with my vernacular at the time.
- boomboomsubban 4y agoFurther, "sike" has become a common spelling when used to indicate "not really." At least, according to urban dictionary and other online dictionaries.
- descriptivist 4y ago> it's pronounced the same as "psych" It’s actually spelled “psych.” It’s a derivative of “to psych out.”
- chrisweekly 4y agoWe're agreed in how and why to spell it that way. But the bastardized phonetic spelling "sike" is fairly common too.
- brabel 4y agoIf you're going to address non-native English speakers, using acronyms like FTR (I suppose that refers to for-the-record, but one can never be sure on the Internet... could easily be something like for-the-retarded in some circles) may not be the best idea, BTW (by the way :D).
- plugin-baby 4y agoThanks. Native speaker, no idea it was used like this.
- tptacek 4y agoThe funny bit about this is that the principles that broke SIDH were in the literature --- they owe to a late-1990's theorem† by Ernst Kani, a mathematician in Ontario. We spoke to Steven Galbraith about this (I wouldn't know who Kani was if I hadn't read Galbraith, just to be clear) and he'd even talked to Kani long before any of this came out. But Kani isn't a cryptographer and apparently isn't even especially interested in cryptography, so the dots didn't get connected until much later. † That's the "25-year-old theorem" from the article.
- ShroudedNight 4y agoFor those curious, here's the full publication from Kani's website (The one linked to in the article is behind a paywall): https://mast.queensu.ca/~kani/papers/numgenl.pdf https://mast.queensu.ca/~kani/papers/numgenl.pdf
- bem94 4y ago> 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.
- deleted 4y ago[deleted]
- Dwedit 4y agoFor reference, 10 years ago, the newest Intel processor family was Ivy Bridge (the Die Shrink of Sandy Bridge)
- teaearlgraycold 4y agoGood times. That was one of Intel’s biggest moves towards making integrated graphics not suck.
- deleted 4y ago[deleted]
- wikitopian 4y agoIt was designed by engineers to be quantum resistant without enough deference to mathematicians who could see that it was not resistant to more conventional approaches.
- tptacek 4y agoThat is true only in the banal sense that any number-theoretic crypto break can be attributed to paying insufficient attention to mathematical research, but isn't true in any useful sense, since a small army of mathematicians worked on isogeny Diffie-Hellman.
- jacksnipe 4y agoIt was designed by a mathematician and broken by the mathematical community.
- formerkrogemp 4y ago> It was designed by engineers to be quantum resistant without enough deference to mathematicians who could see that it was not resistant to more conventional approaches. Ie, they didn't take enough time and money to consult with every cryptography and mathematics expert.
- xt00 4y agoso the cynical view here would be that the backdoor was discovered before the algorithm could get widely deployed?
- DarkmSparks 4y agoMy super cynical view is that the whole genre of "quantum safe" cryptography is being promoted to try and encourage adoption of weak encryption... Its felt like FUD based on FUD for a while. Not that I really trust traditional encryption that much either. There wouldn't be so much effort going into bridging air gapped systems if even traditional encryption could be trusted... Hate making cynical comments tho, they always seem to get down voted :( like being cynical when it comes to encryption is a bad thing.....
- olliej 4y agoQuantum safe crypto isn’t FUD, NIST’s steadfast refusal to specify a dual system, especially given their historical laundering of NSA back doors is super questionable, but there exist (at least one that I know of) crypto systems that have no exploitable bias. The problem is the impractically large key sizes. Afaict a lot of pqc work is trying to reduce the key sizes to something reasonable.
- tptacek 4y agoHorseshit. It's literally not NIST's job to design a "dual system"; the project was to standardize PQC constructions, not whole protocols. Everybody that deploys PQC anywhere is going to deploy "dual systems". This complaint is like claiming NIST is corrupt because they didn't standardize an authenticated key exchange along with SHA-3.
- olliej 4y agoIt is literally NIST’s job to define the standards that people are meant to use. What you’re saying is that NIST not considering a dual system standard is fine because no one would consider relying solely on the standardized PQC algorithms and would obviously implement their own version of a dual system, only with less understanding of potential pitfalls or analysis for weaknesses.
- RcouF1uZ4gsC 4y ago> 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 of those people work for the NSA.
- zmgsabst 4y agoThat’s not fair — at least ten work for Chinese intelligence.
- RcouF1uZ4gsC 4y agoAnd some may actually work for both!
- zaroth 4y agoOuch.
- lizardactivist 4y agoThe smartest people in the world are always Americans. No wonder the rest of the world can't make things on their own, and always steal American technology!
- mixedbit 4y agoI 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.
- jabbany 4y agoProbably 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.
- RL_Quine 4y agoIt’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.
- SV_BubbleTime 4y ago>a single hash (it’s unclear why a double one was used in the first place), but all the same it remains highly unlikely. Because of one of something is good, more is always better. This is how my brother in law cooks, and it's... "flavorful" in a bad way.
- czbond 4y agoYou 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
- Retr0id 4y agoAlmost certainly not. They'd have started prototyping the attack with small numbers, and once it started working, slowly scaling it up.
- undersuit 4y agoWhy would you know that? They used an Intel Xeon CPU E5-2630v2, it's in the paper. What if in the process of crafting the attack on their old workstation PC they found that it was seemingly possible to do low key sizes very quickly and scaled up from there to a practical attack. Or maybe they have quite the competency in Mathematics and realized their attack was not that computationally expensive. >Ran on a single core, the appended Magma code breaks the Microsoft SIKE challenges $IKEp182 and $IKEp217 in about 4 minutes and 6 minutes, respectively. A run on the SIKEp434 parameters, previously believed to meet NIST’s quantum security level 1, took about 62 minutes, again on a single core. We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively.
- tashbarg 4y agoMathematicians do not have funding for „large scale“. A 10-year old mid-range server is exactly the kind of system I would expect Magma to run on in the average case. Perhaps even just a desktop pc. Source: worked with algebra researchers using Magma.
- czbond 4y agoI was being a bit facetious, but not by much. Maybe because they're mathematicians and had found a theorem - but a pen tester wouldn't have. It costs less than a few hundred bucks to do numerous, multi compute AWS server spot instances for cracks on large dictionaries with large hash rates, on random seed password lists (where each password has it's own seed). If it was trying to crack a quantum-safe where by design the classical computer shouldn't be able to even solve it (except for potentially with a theorem hole) - you'd think they'd start higher.
- eterm 4y agoI look forward to this being in the next set of cryptopals.
- tptacek 4y agoIt'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.
- amirhirsch 4y agoEven before being broken, the abstruse mathematics is one of the reasons to not go with SIKE or Rainbow. It’s not surprising they are broken. NTRU is the easiest of the NIST PQC finalists to understand, and will probably beat Kyber because even a relatively new-to-cryptography programmer will be able to understand it and implement it.
- tptacek 4y agoYou can see why people love it, though; the nuts and bolts of SIDH are extremely elegant. Like, it's a neat trick. I don't understand Richelot isogenies and abelian surfaces and can't speak to the elegance of the break; it's the break that exceeds the threshold for "abstruse" (of course, the abstruse mathematics of things that break cryptosystems do make the underlying cryptosystem abstruse! you have to grok them to use it!)
- olliej 4y agoEase of understanding isn’t the same as good though. For example RSA is much easier to explain and implement than ECC, but it is much worse.
- ChrisMarshallNY 4y agoWell, back to the old drawing board... https://youtu.be/UaR6aqL-L3Y?t=10 https://youtu.be/UaR6aqL-L3Y?t=10
- aidenn0 4y agoBeing cryptoanalyzed makes me very angry, very angry indeed!
- tptacek 4y agoIf 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/11123170-hot-cryptanalytic-summer-feat-steven-galbraith 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, like the, the broadcast he did for, um, for Microsoft. And I kind of worked my way through the, the tutorial paper. So like, is it, is it true that like, in sort of the same sense we're... † Looks back and forth around the room furtively
- thadt 4y agoJust 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!"
- KenoFischer 4y agoJust FYI, your 1038.pdf hyperlink at the bottom goes to the 975.pdf paper ;).
- staticassertion 4y agoCan anyone do long division other than children and those who pursue math academically? Seems impossible to imagine.
- hodgesrm 4y agoThis is news to me that people can't/don't do long division. It's simple. I use it regularly to estimate quotients--just run the process to a couple places in your head.
- scatters 4y agoYou need to be able to perform long division to take quotients in algebraic structures, e.g. polynomials. Yes, Wolfram Alpha can probably do it, but not always.
- UncleOxidant 4y agoThat 10-year-old PC is quite precocious.
- rich_sasha 4y agoTrue to its name, i think no quantum computer in existence can crack this cipher.
- mirekrusin 4y agoGood point, using 10 year old classical computer doesn't seem fair!
- denton-scratch 4y agoSchneier had a less breathless account a few days ago: https://www.schneier.com/blog/archives/2022/08/nists-post-quantum-cryptography-standards.html https://www.schneier.com/blog/archives/2022/08/nists-post-qu...
- nottorp 4y agoAlso, Schneier's site doesn't have me agree to tracking without any possibility of rejection ;)
- tptacek 4y agoHe's wrong about the "cryptographic agility" stuff, at least the way he's framed it. But then, another place where I'd part company with him is about the urgency for getting PQC slotted into real-world systems.
- emn13 4y agoWhy do you think he's wrong? He's essentially saying IT systems need to be designed with the expectation that cryptographic algorithms will be attacked and may need to be replaced, as I understand it.
- tptacek 4y agoIf by "crypto agility" one means "we should research diverse cryptographic primitives and constructions so that we can be ready if something we rely upon breaks", nobody disagrees with that. But that's not what Schneier means. What he says instead is that "it’s vital that our systems be able to easily swap in new algorithms when required". That approach has a virtually unbroken track record of failure. It demands negotiation, which introduces bugs, and even after you get past that, it doesn't work: you literally always end up with downgrade attacks (see, for instance, the DNSSEC work at Black Hat this year). Sometimes those downgrade attacks introduce vulnerabilities for parties that would never have even attempted to use the legacy crypto.
- 4y ago
- nashashmi 4y agoWhat is the possibility that cryptowallets can succumb to these kinds of attacks? How is it possible that Satoshi's wallet has still, after so many years, not been hacked using a brute force mechanism?
- infinityio 4y agoI'm sure many people are trying. On a slightly related note - I wonder what the market effect would be on bitcoin (and possibly crypto as a whole) if anyone managed to transfer money out of the wallet, would it crash the currency?
- tptacek 4y agoYou're sure many people are trying to deploy attacks on supersingular isogeny Diffie-Hellman against Bitcoin?
- lizardactivist 4y agoIt's because the search space (number of possible keys to guess) is astronomic; 2^256. If you had a billion people, each person owning one billion computers, each computer capable of guessing a billion keys per second, then a billion years would still not have exhausted one-billionth of all the possible keys.
- nashashmi 4y agoThat makes sense. So his wallet will be broken in about 10 years plus 10 years marking the time for advancement of CPU and time for brute force to spend calculating with the advanced CPU.
- nimbius 4y agosort of offtopic but it reminds me of the first auto shop I worked in. I just got certified on a new laser alignment tool and had a chip on my shoulder for almost a week, until an old timer manually dialed in an alignment that checked out perfect on my shiny new gizmo. I'd never felt so humbled in my life and spent that whole summer practicing manual alignments.
- CoastalCoder 4y agoYeah, pretty off-topic, but I'm glad you shared the story. It reminded me of a story my dad told about a similarly skillful shop owner he'd run into. My dad passed away a few years ago, so I'm grateful for you reminding me of a nice thing.
- robocat 4y agoYour seem to be using “chip on the shoulder” to mean “being overly proud”: is your usage common in your circles or is it a mistake? https://grammarist.com/idiom/chip-on-your-shoulder/ https://grammarist.com/idiom/chip-on-your-shoulder/
- demopathos 4y agoMy anecdotal usage is a combination of these two. Until I saw your provided definition I would have described chip on my shoulder to mean a sense of superiority that leads to me be rude or difficult to interact with.
- kQq9oHeAz6wLLS 4y agoNever underestimate the old eyecrometer
- cat_plus_plus 4y agoWell, it's Quantum-Safe, not Turing-Safe
- perfecthjrjth 4y agoAny NSA and NIST shenanigans here wrt isogeny PQC? Is this "quantum-safe" crypt is in the current round of PQC selection by NIST?
- Blackthorn 4y agoIs there a description of how the proof applies to the cryptosystem? IEEE is a bit light on the essential details.
- jupp0r 4y agoIf the algorithm is weak then the difference between a supercomputer and a 10 year old phone is negligible when compared to algorithms that are solid.
- userbinator 4y agoI think the beginning of the title lead me to believe it would say "10-Year-Old Kid" as I was hoping for some sort of "emperor has no clothes" situation, or brilliant amateur insight. Yet I still think there's a good "look beyond your strengths" lesson here.
- snapetom 4y agoSIKE. This was reported weeks ago, right? There are still three more candidates.
- cdelsolar 4y agoSIKE... that's the wrong number!
- Sohcahtoa82 4y agoOOOOHHHH!!!! https://youtu.be/9UAC2qkcrDY?t=66 https://youtu.be/9UAC2qkcrDY?t=66
- jfghi 4y ago
- born-jre 4y agoIt was not in NIST final competition, right ? Just alternate candidate.
- aidenn0 4y agoIIUC, NIST did not select a winner for post-quantum public-key-encryption, but rather winnowed the field to 4 potential candidates, and this is one of them.
- tptacek 4y agoNo, it selected the CRYSTALS-Kyber KEM and then proceeded for an additional round to consider alternatives/understudy KEMs, of which SIKE was one potential one.
- avodonosov 4y agoI initially read "Hacked by 10-Year-Old", as if a child hacked it.
- deleted 4y ago[deleted]
- jasonkimberson 4y agoMe too, lol
- avodonosov 4y agoProbably it's because of the word "hacked". I mostly saw it used in meaning the [human] activity of designing an approach, rather than executing code. Computers do not hack. (Unless we speack of AI, maybe)
- andai 4y agoCan a quantum computer crack your encryption if it doesn't know the algorithm (ie. if you created it yourself and it is unknown to the outside world)?
- tptacek 4y agoNo.
- DoctorOetker 4y agono, but an insider can leak your security through obscurity, at which point any publically known rammifications that were overseen are easily exploited.
- NewEntryHN 4y ago> Remember, this is a demolition derby. The goal is to surface these cryptanalytic results before standardization, which is exactly what happened https://www.schneier.com/blog/archives/2022/08/nists-post-quantum-cryptography-standards.html https://www.schneier.com/blog/archives/2022/08/nists-post-qu...
- karl_gluck 4y agoCan someone remind me why Merkle trees of Lamport signatures aren’t the solution for postquantum asymmetric signing? Sure the signatures are huge, but they’re secure unless you can trivially invert the hash function.
- tptacek 4y agoSIDH/SIKE is a key exchange mechanism, not a signature scheme.
- cookiengineer 4y ago> paper: https://eprint.iacr.org/2022/975.pdf https://eprint.iacr.org/2022/975.pdf Does this mean that probably all SIDH key exchanges are affected? What about TOR? Do we have to assume that key exchanges can be intercepted and recovered? A RUSTSEC advisory was already published and they removed all SIDH algorithms there [1] [1] https://rustsec.org/advisories/RUSTSEC-2022-0045.html https://rustsec.org/advisories/RUSTSEC-2022-0045.html
- tptacek 4y agoDoes Tor use SIKE/SIDH? The proposals I've seen for PQC Tor all seem to run a PQC construction alongside a conventional one (the only sane way to do this right now), and so, no, a break in the PQC wouldn't let you recover sessions. Yes, this impacts all of SIDH.
- dtrizzle 4y agoThe idea that encryption algorithms need to be well tested over time is why many security experts do not trust Telegram's encryption algorithm (MTProto).
- elevaet 4y agoSo, do there exist other "quantum-safe" crypto algorithms still considered to be reliable?
- tptacek 4y agoYes, many, including the lattice algorithm NIST chose in the first round of the PQC competition.
- trentnix 4y agoThis headline, “Quantum-Safe” Crypto Hacked by 10-Year-Old PC, was pretty awesome until I got to the "PC" part.
- bartimus 4y ago10-year-old PC makes it sound dramatic. Yet single core speed hasn't increased that dramatically over the last 10 years.
- jongjong 4y agoThat's why I like simple hash-based cryptographic algorithms such as Lamport OTP for digital signatures. Hash-based algorithms are broadly believed to be quantum-resistant and this makes sense intuitively because hashing destroys information. The statefulness of Lamport OTP adds some implementation and usability hurdles but IMO, the simplicity and intuitiveness of the algorithm makes it worthwhile. Source: I worked on a quantum-resistant blockchain which is based on Lamport OTP and Merkle Signature Trees (for key reuse) - https://capitalisk.com/ https://capitalisk.com/
- tptacek 4y agoWe're discussing key exchange mechanisms, not signatures. The distinction is important: KEMs are what we need now if QC is a real threat, because they're what enable us to protect traffic from retroactive decryption.
- jongjong 4y agoThe encryption side of things does appear to be a lot more challenging. I like solutions which allow complexity to be side-stepped somehow but I'm not aware of anything like that for encryption.
- DjlbrilH 4y agoWhere the FG-2$?