[HN Gopher] "Quantum-Safe" Crypto Hacked by 10-Year-Old PC ___________________________________________________________________ "Quantum-Safe" Crypto Hacked by 10-Year-Old PC Author : oipoloi Score : 239 points Date : 2022-08-19 17:07 UTC (5 hours ago) (HTM) web link (spectrum.ieee.org) (TXT) w3m dump (spectrum.ieee.org) | [deleted] | wikitopian wrote: | 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. | tptacek wrote: | That 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 wrote: | It was designed by a mathematician and broken by the | mathematical community. | formerkrogemp wrote: | > 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. | UncleOxidant wrote: | That 10-year-old PC is quite precocious. | rich_sasha wrote: | True to its name, i think no quantum computer in existence can | crack this cipher. | mirekrusin wrote: | Good point, using 10 year old classical computer doesn't seem | fair! | perfecthjrjth wrote: | Any NSA and NIST shenanigans here wrt isogeny PQC? Is this | "quantum-safe" crypt is in the current round of PQC selection by | NIST? | userbinator wrote: | I 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. | denton-scratch wrote: | Schneier had a less breathless account a few days ago: | | https://www.schneier.com/blog/archives/2022/08/nists-post-qu... | nottorp wrote: | Also, Schneier's site doesn't have me agree to tracking without | any possibility of rejection ;) | tptacek wrote: | He'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 wrote: | Why 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 wrote: | If 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. | bawolff wrote: | Well i agree generally, if we are talking about these | new, basically experimental, post quantum algorithms, i | feel like the balance shifts a bit since they are still | so new (on the other hand maybe using them is just | premature at this point) | tptacek wrote: | The universal answer to this concern is to run a | conventional key exchange alongside the PQC key exchange. | michaelt wrote: | Doesn't every major cryptosystem have multiple | ciphersuites, though? | | There's things like SSL, SSH and GPG, truecrypt, | bitlocker, /etc/passwd, ntpsec - even git is trying to | upgrade their hashes from SHA1 to something longer. There | are only a handful of exceptions, like TOTP. | | Isn't it a must-have feature? Or has the feature become | less important than it was 25 years ago when those | protocols were being designed? | tptacek wrote: | Yes, and every one of those major cryptosystems has been | a debacle, in large part because of the negotiations | imposed by ciphersuites. It is not a must-have feature; | it's a feature cryptography engineering best practice is | rapidly beginning to recognize as an anti-feature. See | WireGuard for an example of the alternative: you version | _the whole protocol_ , and if some primitive you depend | on has a break, you roll out a new version --- which, | historically, you've effectively had to do anyways in | legacy protocols. | Zamicol wrote: | Cryptographic agility means to support multiple | cryptographic primitives and to not be overly coupled to | a single primitive. | | WireGuard is a great example of a product with | cryptographic agility. https://www.wireguard.com/protocol | | Cryptographic agility says nothing about "version the | whole protocol". | tptacek wrote: | No, it's pretty widely recognized that WireGuard is in a | sense a repudiation of "agility". You can look at, for | instance, the INRIA analysis/proof paper to see how a | bunch of disinterested cryptographers describe it: "many | new secure channel protocols eschew standardisation in | favour of a lean design that uses only modern | cryptography and supports minimal cryptographic agility." | | If you want to say "minimalist agility is good and you're | just saying maximalist agility is bad", that's fine, | we're just bickering about terms. But that's pretty | obviously _not_ what Schneier is talking about. | Zamicol wrote: | All the works I've read of Schneier have given me the | impression of the above definition, "support multiple | cryptographic primitives and do not be overly coupled to | a single primitive." | | Serendipitously, I just tweeted about this 11 days ago: | https://twitter.com/CyphrMe/status/1556660870901403648 | | "The moral is the need for cryptographic agility. It's | not enough to implement a single standard; it's vital | that our systems be able to easily swap in new algorithms | when required." | | Do you have a link to something that in your mind | represents what Schneier is talking about? | tptacek wrote: | A modern cryptosystem wouldn't be designed to swap in new | algorithms; it would pick a single set of algorithms and | constructions, and version the whole system. Which is how | WireGuard works: you can't run AES WireGuard, or | WireGuard with the standard P-curves. | est31 wrote: | If you have multiple WireGuard versions, in a migration | setting, you also need to do some negotiation at the | start, no? Wouldn't that be potentially vulnerable to | downgrade attacks as well? | tptacek wrote: | No: you simply don't speak the old versions. | est31 wrote: | So the migration looks like "upgrade the client or you | won't be able to connect to the server any more"? What if | you use the client to talk to multiple servers, some that | use the old version, some that use the new version? Maybe | via a config variable adjustable per server? Then you do | out of band version negotiation, and you might get away | with this in the VPN setting, where entering arcane | config vars is commonplace, but not in e.g. the TLS | setting. | some_furry wrote: | I wrote a lot about a similar debate recently, but in the | context of encryption at rest rather than encryption in | transit | | https://soatok.blog/2022/08/18/burning-trust-at-the- | quantum-... | | For brevity, start reading at "Isn't cryptography fun?" | which contains the relevant portion. | tptacek wrote: | Entering arcane config variables is extremely not | commonplace with WireGuard. | est31 wrote: | I guess that's thanks to the fact that WireGuard is a new | system and new systems have little legacy bloat. Maybe | the WireGuard author had golden hands, and the system is | perfect, and indeed it it is quite good, but I think | instead that WireGuard will eventually require a new | version. Then one such solution will have to be chosen. | some_furry wrote: | When that happens, you will use WireGuard v2 which is | incompatible with WireGuard v1. | | I wouldn't expect it to happen before a crypto-relevant | quantum computer is built. | Spooky23 wrote: | Look at TLS/SSL. TLS 1.2 was out for years until public | vulnerabilities forced deprecation of SSL 3 and TLS 1.0. | [deleted] | Zamicol wrote: | I think this is the link: | https://www.schneier.com/blog/archives/2022/08/sike-broken.h... | oipoloi wrote: | "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." | tptacek wrote: | The 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 wrote: | For 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 | bem94 wrote: | > 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] | moffkalast wrote: | Well they for sure have picked a very ironic name for it. | | "The vault is completely unhackable." | | "SIKE" | chrisweekly wrote: | +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" | gwright wrote: | For additional cultural context, I think this usage was | popularized by Eddie Murphy in Delirious (NSFW language: | https://youtu.be/Ft4kEk5CHrE, you'll want to listen to at | least 2:15) | formerkrogemp wrote: | I often don't think to explain these things, so thank you | for taking the time to explain to others the context. | boomboomsubban wrote: | Further, "sike" has become a common spelling when used to | indicate "not really." At least, according to urban | dictionary and other online dictionaries. | cdelsolar wrote: | SIKE... that's the wrong number! | Sohcahtoa82 wrote: | OOOOHHHH!!!! | | https://youtu.be/9UAC2qkcrDY?t=66 | xt00 wrote: | so the cynical view here would be that the backdoor was | discovered before the algorithm could get widely deployed? | DarkmSparks wrote: | My 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 wrote: | Quantum 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 wrote: | Horseshit. 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 wrote: | It 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. | tptacek wrote: | No. Once again: the NIST PQC competition is a project to | standardize _post-quantum cryptography constructions_. It | 's not a protocol competition, any more than the AES and | SHA-3 competitions were. | | This is literally spelled out on the competition page. | I'm having trouble how anyone could have any confusion | about this. It literally says: do hybrid systems if you | want, that's outside the scope of this competition. | | How would it even have _made sense_ to pursue hybrid | systems in this competition? Like how would that have | actually worked? | api wrote: | NIST/FIPS allows HMAC(salt, key) where salt can be | anything, so a dual system is trivial: HMAC(PQ secret, | conventional secret). | jabbany wrote: | > Its felt like FUD based on FUD for a while. | | Not really...? Quantum stuff is real, there are real quantum | computers that have been demonstrated to really do quantum | operations. They're not close to being usable to break crypto | yet, but it certainly makes sense to get ahead of it. | | > There wouldn't be so much effort going into bridging air | gapped systems if even traditional encryption could be | trusted... | | These are completely different problems. Encryption just | keeps information confidential. By itself, it offers no | _security_ guarantees. Even the strongest encryption would be | moot against a keylogger. Crypto can be (and is being) used | to provide some security, like via signed code, secure | processors, and the such, but security is a multi-tiered | thing -- you want all the protection you can get, and like | keeping data encrypted at rest, air-gapping is just yet | another layer of protection. | spywaregorilla wrote: | quantum is used for problems like finding the factorization | of the number 4. | | Jumping is also real, but we need not worry about people | jumping out of the atmosphere. | jabbany wrote: | > Jumping is also real, but we need not worry about | people jumping out of the atmosphere. | | If people are jumping twice as high this year than last, | we would ;) https://www.researchgate.net/figure/A-chart- | shows-the-progre... | | (BTW this reply is not meant to make a point about the | state of quantum -- it's complicated -- but merely as a | response to the analogy) | spywaregorilla wrote: | I'm not much of a believer. It's worth pointing out that | as the number of qubits goes up, so too does the error | rate. | tptacek wrote: | I'm not a believer (I'm not qualified to have an opinion | but neither is almost anyone else here) in PQC, but to be | clear, the logic behind moving forward on PQC is | straightforward: everybody acknowledges that there are no | known useful QC attacks on cryptography, nor really any | on the horizon, but adversaries can easily stockpile | terabytes of recorded network conversations today and | keep them around to break when QC attacks do work. | | If you think QC attacks are 20 years away from real-world | demonstrations, then conventional cryptography has a | 20-year ceiling, which would be a hair-on-fire analysis | in any other context. How long are you willing to bet | conventional cryptography will hold out? 50 years is also | too short by cryptographic standards. And 50 years is a | _long time_. You willing to bet 100 years? I am, but, | like, nobody should listen to me on this. | | This is also why KEMs are a priority over signatures for | PQC deployment. | kibwen wrote: | _> My super cynical view is that the whole genre of "quantum | safe" cryptography is being promoted to try and encourage | adoption of weak encryption_ | | Not a cryptographer, but surely if you're worried about this | then you could first encrypt your data using classical | algorithms and then encrypt the output of that via the PQC | algorithms, to produce a ciphertext that is at least no less | safe than the classical encryption alone. | stjohnswarts wrote: | This is a place where Hanlon's razor applies much better than | assuming they want weak encryption. | Blackthorn wrote: | Is there a description of how the proof applies to the | cryptosystem? IEEE is a bit light on the essential details. | Dwedit wrote: | For reference, 10 years ago, the newest Intel processor family | was Ivy Bridge (the Die Shrink of Sandy Bridge) | teaearlgraycold wrote: | Good times. That was one of Intel's biggest moves towards | making integrated graphics not suck. | jfghi wrote: | nashashmi wrote: | What 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? | lizardactivist wrote: | It'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. | infinityio wrote: | I'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 wrote: | You're sure many people are trying to deploy attacks on | supersingular isogeny Diffie-Hellman against Bitcoin? | RcouF1uZ4gsC wrote: | > 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 wrote: | That's not fair -- at least ten work for Chinese intelligence. | RcouF1uZ4gsC wrote: | And some may actually work for both! | lizardactivist wrote: | The 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 wrote: | 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. | Beldin wrote: | 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 x block reward a year. I doubt many governments | could resist. | jabbany wrote: | Not at all... | | I mean if you break either the hash or the signature, then | there are bigger fish to fry than just Bitcoin. You'd | essentially be on your way to breaking much of the crypto | used to secure significantly more valuable information -- the | kind of information you measure with human lives rather than | dollars. | | Actually, if you (or more likely a nation state actor) did | break either the hash or signature, you'd be crazy to reveal | that fact on something as trivial as Bitcoin. That'd be like | breaking ENIGMA and just using it to publish the German | weather reports lol. | ayende wrote: | That amount of money is not even a rounding error. | | And it is likely to be very obvious and public. | | You will crash the market, so can't really do that multiple | times. | | And if you can Crack this there are better targets | jabbany wrote: | 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. | RL_Quine wrote: | 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. | SV_BubbleTime wrote: | >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. | svnpenn wrote: | > will ever broken | kmeisthax wrote: | Consensus compatibility is nice, but Bitcoin has a unique | problem: those old signatures _own_ coins. Phasing out a | signature algorithm means confiscating the coins in | question, as the rightful owner will no longer be able to | spend them anymore. Leaving them open would just let | private actors break wallets to confiscate the coins | themselves, with the added bonus that burnt or lost coins | could be recovered, effectively increasing the supply of | coins on the market. And Bitcoin has a _lot_ of early- | adopter money supply locked up behind dead hard drives - it | would crash the market. | | Other systems that use ECDSA don't have this problem | because they rely on CAs and central authorities. For | things like, say, the TLS PKI; if you miss the flag date to | change ciphers you aren't forever locked out of your | domain. Your site just goes down until you bother to | upgrade your servers and rotate keys. | | Is there any known/stated policy as to how to handle | phasing out a signature algorithm in Bitcoin? | jabbany wrote: | No idea, but I could imagine something where you have a | period of time on the chain where both signature types | are allowed, and people can just migrate their coins by | transferring from the old wallet to one based on the new | signature system. Then after a certain cutoff, the chain | can phase out the old signature system entirely. | | Of course this only works if the old system is just | "weak" rather than "broken". There is no way to recover | if the signature system is completely broken, but if | ECDSA is broken then we have more to worry about than | just Bitcoins. | Spooky23 wrote: | Not only that, but bazillions of coins are dead. My 4 | bitcoins that were lost to a hard drive failure a decade | ago are gone, and "reanimating" them wouldn't even be | theft. | kevincox wrote: | > especially considering that almost every value in the | system is sha2(sha2()) | | Why does this give a meaningful improvement? Is this just | security through obscurity? Presumably if this had | significant benifits sha2 would have been defined this way | to start with right? Or is it just that other users will be | broken before this "double strong" version so that you have | more warning? But isn't shaw defined as a number of rounds | anyways? | copperx wrote: | I'd love a mathematical explanation because my intuition | also says it cannot be more secure. | jabbany wrote: | My guess is the grandparent refers to this kind of | attack: | https://en.wikipedia.org/wiki/Length_extension_attack | | Basically, many cryptographic hashes support fixed-length | hashes of variable message lengths by breaking the | message into blocks, chaining their hashes* and taking | the final hash. | | The weakness here is if you know the length of a prefix | and its hash, you can generate more valid hashes of | messages that contain the unknown prefix but with custom | suffixes. This is relevant if you use the hash for | authentication (i.e. MAC) as it allows producing certain | types of custom messages that would also validate. | | However, this has largely been a non-issue for a long | time now as it takes very little tweaking of the protocol | (stuff being authenticated) to make adding suffixes | useless. Double hashing is one such mitigation, because | the outer hash is now working over a fixed size input, | meaning to attack it you'd need to the signed message | instead of just appending to it. | | *: This approach of chaining hashes of blocks is also | used in other contexts that you may be familiar with ;) | RL_Quine wrote: | It's a historical thing people used to do for length | extension attacks, but it's irrelevant where it exists in | bitcoin, for example as branches in a merkle tree where | every input is of a fixed length (another hash). For | Bitcoin a good portion of all the CPU time involved in | verifying is just doing hashes of hashes, so it just is | what it is. | | It has the side effect of making some attacks where you | need control of certain bytes of the input (see the md5 | commission tool) harder because you've now got to find an | exploit which makes it through both hashes. | athrowaway3z wrote: | 'breaking' a hash can mean many different things. Among | many others, two types of attacks are: | | - a specific prefix/suffix data can be created to force a | collision. | | - A message of exactly N bytes can quickly create a | collision. | | Both attacks would be reported as a hash being broken. | But its assumed to be unlikely that a well designed hash | would have a flaw that breaks the hash in both ways. | Keyword being assumed. But with good reason. | | AFAIK sha has only been broken by a variable length | suffix attack. | | With sha2(sha2()) it would have to be broken both ways. | 323 wrote: | Even if you don't reuse keys you will be vulnerable the | moment you do the first transaction - it will be the miner | who sees your public key first. Even if you mine your own | transactions you will be vulnerable, because the block | could be orphaned, and anyone could then see your public | key. | karl_gluck wrote: | Can 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 wrote: | SIDH/SIKE is a key exchange mechanism, not a signature scheme. | avodonosov wrote: | I initially read "Hacked by 10-Year-Old", as if a child hacked | it. | [deleted] | jasonkimberson wrote: | Me too, lol | avodonosov wrote: | Probably 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) | czbond wrote: | 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 | Retr0id wrote: | Almost certainly not. They'd have started prototyping the | attack with small numbers, and once it started working, slowly | scaling it up. | tashbarg wrote: | Mathematicians 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 wrote: | I 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. | undersuit wrote: | Why 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. | er4hn wrote: | if anyone would have a sense of the number of operations | required, you'd hope it was a mathematician. | [deleted] | born-jre wrote: | It was not in NIST final competition, right ? Just alternate | candidate. | aidenn0 wrote: | IIUC, 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 wrote: | No, 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. | nimbius wrote: | sort 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. | robocat wrote: | Your 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/ | demopathos wrote: | My 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. | CoastalCoder wrote: | Yeah, 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. | jupp0r wrote: | If 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. | cat_plus_plus wrote: | Well, it's Quantum-Safe, not Turing-Safe | eterm wrote: | I look forward to this being in the next set of cryptopals. | tptacek wrote: | 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. | amirhirsch wrote: | Even 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 wrote: | You 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 wrote: | Ease 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 wrote: | Well, back to the old drawing board... | | https://youtu.be/UaR6aqL-L3Y?t=10 | aidenn0 wrote: | Being cryptoanalyzed makes me very angry, very angry indeed! | [deleted] | andai wrote: | Can 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 wrote: | No. | tptacek wrote: | 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, 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 wrote: | 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!" | staticassertion wrote: | Can anyone do long division other than children and those who | pursue math academically? Seems impossible to imagine. | scatters wrote: | You 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. | KenoFischer wrote: | Just FYI, your 1038.pdf hyperlink at the bottom goes to the | 975.pdf paper ;). | NewEntryHN wrote: | > 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-qu... | snapetom wrote: | SIKE. This was reported weeks ago, right? There are still three | more candidates. ___________________________________________________________________ (page generated 2022-08-19 23:00 UTC)