“Quantum-Safe” Crypto Hacked by 10-Year-Old PC (opens in new tab)

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!"

Just FYI, your 1038.pdf hyperlink at the bottom goes to the 975.pdf paper ;).

Huh? Long division is easy. I just type the numbers into google

Can anyone do long division other than children and those who pursue math academically? Seems impossible to imagine.

Also, Schneier's site doesn't have me agree to tracking without any possibility of rejection ;)

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.

I think this is the link: https://www.schneier.com/blog/archives/2022/08/sike-broken.h...

Good point, using 10 year old classical computer doesn't seem fair!

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/

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.

Never underestimate the old eyecrometer

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.

Well they for sure have picked a very ironic name for it.

"The vault is completely unhackable."

"SIKE"

> 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.

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.

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.

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

The authors of the the attack are primarily theoreticians. The only implementation they provided was a Sagemath one. I don’t think there was ever any distributed impl for this algorithm.

if anyone would have a sense of the number of operations required, you'd hope it was a mathematician.

Good times. That was one of Intel’s biggest moves towards making integrated graphics not suck.

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.

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.

Thats true, its a critical risk to Bitcoin, Ethereum etc. The digital signature scheme protecting Bitcoin accounts use elliptic curves which can also be broken using quantum computers.Transactions can be forged using broken accounts.

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.

This is inevitable for all coins with published public keys, which all the early coins are. So, e.g. all of Satoshi's coins. For coins where the public key is hashed, perhaps not inevitable.

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).

We'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.

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.

It was designed by a mathematician and broken by the mathematical community.

> 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.

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.....

Does 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.

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

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!

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.

SIDH/SIKE is a key exchange mechanism, not a signature scheme.

Yes, many, including the lattice algorithm NIST chose in the first round of the PQC competition.

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.

no, but an insider can leak your security through obscurity, at which point any publically known rammifications that were overseen are easily exploited.

No.

Being cryptoanalyzed makes me very angry, very angry indeed!

OOOOHHHH!!!!

https://youtu.be/9UAC2qkcrDY?t=66

Me too, lol

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.

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?