“Quantum-Safe” Crypto Hacked by 10-Year-Old PC
spectrum.ieee.org
spectrum.ieee.org
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!"
There isn't any reason for 99.9% of mathematicians - even in abstract algebra - to know long division.
Both in the trivial sense, and the 361 = 3x10^2 + 6x10 + 1 sense
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...
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.
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?
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.
I wouldn't expect it to happen before a crypto-relevant quantum computer is built.
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".
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.
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?
You're arguing against runtime agility. That makes sense; in fact, the more runtime agility you have, the less design-time agility you have, because all that dynamic negotiation is quite the constraint - and as you point out, a source of flaws.
Even negotiation has flavors. Classic TLS tried to make supporting old ciphers "secure", but even negotiation in which you assume the attacker _can_ control the cipher can be useful - the point then being not to do so long-term, but merely as a technique to allow non-instantaneous roll-out world wide. There's a difference between trying to support but never use legacy stuff and also refusing to specify the current gold standard, and merely having a protocol that supports multiple ciphers only to the extent necessary to occasionally replace a single old configuration with a single new one.
I'm not sure whether there's a huge difference between merely supporting research diversity, and having non-runtime but design-time agility. Perhaps those are the same thing. I guess it gets interesting where encryption primitives aren't just ephemeral communication tools, but a more intrinsic part of the software (such as in signing, and especially in stuff like blockchains) - is there a way to have at least the option of swapping primitives without weakening the guarantees today?
In any case; thanks for the clarification!
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"
It’s actually spelled “psych.” It’s a derivative of “to psych out.”
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.
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?
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.
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?
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.
- 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.
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 ;)
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.
(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.
Jumping is also real, but we need not worry about people jumping out of the atmosphere.
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.
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)
Genuine question. I've no idea.
Generally, the number of physical qubits scales linearly with the number of logical qubits.
[0] https://journals.aps.org/prx/abstract/10.1103/PhysRevX.11.04... [1] https://www.nature.com/articles/s41586-022-04566-8
Assuming they will exist.
And assuming there exists math that can't be solved easily by quantum computers that solve all math solution finding problems easily.
Surely it makes no sense to adopt encryption no one but a few individuals of questionable motives understand, to protect against a technology that is a long way from even proven yet. IMHO.
Anything else requires several leaps of faith that should be no where near "in use" encryption - research is of course a very different story, but stories like this are hardly confidence inspiring.
If anything these stories should be more confidence inducing. They show that the rollout is conservative and that the system works. PQC algorithm has a flaw and it is found. FWIW the way existing traditional crypto is proven safe is pretty much the same -- get a bunch of people to work on attacks and weed out the bad stuff.
And this article only reinforces the idea that the solutions they are coming up with are just obfuscation that is at best no harder than existing problems.
It could be a factorisation problem, or any other.
for cryptography find x and y when f(x,y)=z given z
That is what "post quantum computing" means, aiui. It starts with x and y in all possible values of x and y, then spits out only the values that give z.
All encryption is only as strong as the difficulty of finding x and y given only z.
AIUI anyway. well aware I could have been misled - FUD.
Think of it as being able to simultaneously calculate a bunch of inputs but only being able to report the "sum" of those calculations to you. So to make it useful you'd need to be able to reconstruct problems such that the incorrect answers when computed cancel each other out. Otherwise your desired answer would just be mixed in with garbage and you won't be able to get anything useful out.
It's not actually that easy to make useful quantum algorithms that work and there's only a handful of them around...
what makes that hard now is the search takes so much time.
In a theortical post quantum world that search wont take much time.
So the only way I see that post quantum encryption can be secure is if it is impossible to guess a solution and test it for correctness - which for whatever reason... never seems to get addressed.
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.
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.
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?
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.
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.