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
"Tony Stark Was Able To Build This In A Cave! With A Box Of Scraps!"
I did pursue mathematics academically but I don't know if it ever came up in university math; more so in physics and computer science.
EDIT: apparently what I do is "short division", which is just long division but you don't write down all the steps.
https://www.schneier.com/blog/archives/2022/08/nists-post-qu...
https://www.schneier.com/blog/archives/2022/08/nists-post-qu...
† That's the "25-year-old theorem" from the article.
"The vault is completely unhackable."
"SIKE"
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.
And for embarrassment of the original design, the story, and clickbait... they did it on that old machine
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.
Source: worked with algebra researchers using Magma.
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.
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.
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.
(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.
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.
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
It's fairly easy to underestimate the time required to change a non quantum resistant to a quantum resistant one.
To protect Bitcoin from quantum computers, the blockchain has to be forked as early as possible, with all blocks re-signed with quantum resistant digital signature schemes. Devil is in the details though.
The Doge Protocol project will fork Bitcoin and move it to a quantum resistant hybrid scheme.
Depending on how you look at it, it's either the built-in doomsday for Bitcoin, or it's a built-in multi-billion dollar bounty for exposing the existence of a quantum computer capable of cracking the private key given a Secp256k1 public key (that's the EC curve bitcoin uses).
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/
Ie, they didn't take enough time and money to consult with every cryptography and mathematics expert.
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.....
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.
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.
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]
Yes, this impacts all of SIDH.
And I bet 48 of those people work for the NSA.
*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.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.
Yet I still think there's a good "look beyond your strengths" lesson here.
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.