Breaking RSA with a quantum computer?
schneier.com
schneier.com
One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2].
The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by hoping potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA".
How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them.
Is there somewhere where I can bet money that this doesn't amount to anything?
1: https://arxiv.org/abs/quant-ph/9508027
2: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2...
Or, to put it a different way, most papers focus on being right. To many publishers, "being right" means being true in what the paper is saying. In some other cases, "being right" means that the action you take is correct. Trying reading it as not a paper on "is RSA-2048 cracked" but "is RSA-2048 still safe".
I guess I'd also be a lot more sympathetic if the paper had a paragraph in the abstract, or at least the intro and conclusion, where they explicitly positioned the paper as a wild idea that could work but probably won't but is still worth considering because of the risks.
I don't think there was a comparison between Schneier and Shor, or I missed it.
I'm aware of both Microsoft and Google publishing papers claiming astounding quantum feats, then later retracting them (I have to assume there were similar instances with lesser known companies). I think your skepticism is valid.
Do you have a reference for a Google quantum paper being retracted? I don't recall an instance of that (disclaimer: I am on the Google quantum team; my views do not represent them).
The real number was 2.5 days, and the computing breakthrough involved in the huge speedup was... using SSDs to store your intermediate state instead of recomputing it every iteration.
One side will publish the public keys for RSA and the private key signature can take the money.
The other side will likewise lock up some money, but that money can be moved by a smart contract method after a certain date, if the first account still has money in it. You can have multiple dates, for removing some or all of the money in the multiple bets against it. For example, "$200 that it's cracked by 2004".
The main problem with bets and contests is that the side which knows the private key can simply withdraw the money itself. That’s why you need the private key to be generated by all parties involved in a ceremony.
Schor proved upper bound.
Neither are Schor.
EM worked in practice, so they spent a long time trying to prove convergence. Modern proofs are simpler.
Could be the case that this method also works in practice. I haven't the faintest idea whether it will.
If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA.
IBM expects to get there by 2025. [1]
[0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co...
E.g. forge email (most dkim keys are 1024 bit rsa). Break ssh (depends on key algo chose). Break pgp (depending on settings). Mitm https connections, Etc.
(I don't think my contacts aren't going to know what SSH or PGP is, if that helps.)
For the vast majority of HTTPS (say, for example, Google or Hacker News) RSA is not used to agree the encryption. So although quantum computers would be a threat for other reasons, breaking RSA in particular doesn't just "remove HTTPS".
However, RSA is used to prove the identity of the server for most web sites even with a newer key agreement. So if an adversary can get on path between you and the server, they could get in the middle and masquerade successfully as the server - arranging key agreement with you, and then providing a convincing fake proof of identity, if they do so live.
In TLS 1.2 optionally, and to a greater extent in older versions (which are no longer used by popular web browsers) you can also use RSA to agree the encryption, and for sites using that breaking RSA would allow an adversary to interpose in real time, or to decrypt communication after the fact, but I'd be astonished if anywhere important still does that when talking a halfway modern browser.
> If only someone archived it in a data center in the desert.
Uh oh
https://en.wikipedia.org/wiki/Utah_Data_Center
Good think I declared moral bankruptcy this year, all that is the old me :-)
For example, using the surface code, a back of the envelope estimate would be that you need a code distance of d = ln(number_of_operations). Each logical qubit will use 2d^2 physical qubits. So for a million operations you'd need around 400 physical qubits per logical qubit and for a trillion operations you'd need around 1500 physical qubits per logical qubit. So, way more than 5.
(A major practical obstacle to using almost-anything-that-isn't-the-surface-code is that the surface code has forgiving connectivity and maximum-allowed-physical-noise requirements.)
Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower.
...but don't forget that "if the paper is correct" bit.
Expectations of a Moore's law type improvement rate are going to be left wanting.
More realistically [1], you'd have a factor of around 1,600 for a distance-27 code.
Which is to say that Osprey has 433 qubits, so should be capable of 86 fault tolerant error corrected qubits, so they should be able to factor (not bothering with the math) AT LEAST ONE NUMBER using Shor's algorithm, and yet they cannot.
1) If the paper is right, they are claiming they need 300ish physical qubits that can sustain about 1000 gates before decohering. No need for scalable error correction.
2) Independently of the veracity of the paper, if you actually need logical error corrected (and fault tolerant) qubits, you need error correcting codes with much more severe overhead than the 5-qubit code. The 5-qubit code is a pedagogical example, not something that would actually work under realistic conditions. And even the 5-qubit code needs quite a few extra ancillary qubits for fault tolerance (which is more expensive than simple error correction).
The researchers indicate use of a computer built with superconducting qubits in the abstract, to that, superconducting qubits present barriers such as
- limited coherence time due to common atmospheric muon events, and resulting phonons
- limited topological connectivity, further increasing needed coherence time.
[0] https://ai.googleblog.com/2022/01/resolving-high-energy-impa...
"just". So how do you do the key exchange?
Again, we're talking about some "world ending" scenario that OP mentioned - where all "normal" forms of encryption are already broken. If OTP is the only unbreakable encryption around, them I'm sure we'd find a way to distribute keys.
Apparently, some cesium based list of numbers, again, was 20 years ago.
Point is, it was a one time pad...
They are often called OTPs though (i.e. one-time passcodes), just to cause confusion.
The argument against OTP is that by securely distributing the key of the same length as your message, you ostensibly already have a secure messaging mechanism; why would you need the OTP?
Also: my bank access is done entirely through an app that obscures its internal implementation. It could already be using OTP and it wouldn't make any difference to me, nor would I be able to tell(my point is that the user wouldn't need to keep a piece of paper that they would need to type in anywhere - the internal implementation of tools we use every day would change, but most users wouldn't even notice)
Actually this could be a nice service to offer now. We might worry that someday public key crypto will be broken, and we wouldn’t want all our old bank statements to become public at that point I guess.
Yes, it was inconvenient, but hardly an impossible thing to do. Banks manage to communicate the PIN for your card safely every time you open an account, I'm sure this could be done as well.
And most banks still have brick-and-mortar stores where customers could come and identify themselves and collect their one time pad.
And a GByte of keypads would cover your banking need for a long time.
The problem is more that it works for some one-to-many relationsships such as banks, but not many-to-many relationships, such as emails, websites, etc. There have to be second or third parties.
On the hand, a lot of people seems to log in everywhere with Google Sign In or similar anyway.
And we could instead all have Google or Amazon devices with GBytes of one time pads. And that could be used to set up symmetric encryption, which should be more resistant to quantum computer attacks.
The only drawback is that we would have to trust the third party and everyone who could compromise the third party and every government that could put pressure on the third party :-)
So if it was literally the only remaining unbroken type of encryption on the planet, it would have no effect? How so, exactly? We would just go with no encryption whatsoever rather than bear the inconvenience of distributing OTP keys?
But how would the movie end?
Nobody notices or cares what has happened, and critics are met with "well it dOesN'T mATteR because they aren't using the information for anything bad."
P !== NP is a theory that has never been proven, so it very well could happen in reality.
This is one of those things that keeps me awake, like Carrington events [2].
To rephrase if this is not the case - what value does solving P = NP provide?
Even if that algorithm exists and was found, it could be that such an algorithm is O(n^123456789), which would not break RSA in any practical sense, though it would be mathematically asymptotically faster than O(2^n).
> To rephrase if this is not the case - what value does solving P = NP provide?
P vs NP is a question of enormous practical interest. But it's also a very interesting question of pure mathematics. A proof that P != NP, or a proof of P == NP that didn't provide an algorithm would still be a huge deal in the math and computer science world.
* P != NP. In practical terms, nothing changes.
* Nonconstructive case. The resulting algorithm looks something like some primality test algorithms (which I'll describe): essentially, if a number n is composite, then there is some (X + a)^n = X^n + a in Z/nZ (X is a polynomial here). If you test "enough" a's, then you can prove whether n is prime or composite. A nonconstructive case would mean we have a proof that you only need to test poly(lg n) a's to confirm truth, without necessarily telling which a's you have to test. In this world, there is no practical change to problems--the proof doesn't yield an effective algorithm to actually solve any NP-complete problem.
* Combinatorial algorithm for an NP-complete problem. The good example here is what has been done to prove L = SL. The result is "technically" in L, but the factors in the algorithm run very quickly into "more than the number of atoms in the universe" phase. The goal is to find a memory-less algorithm (can't use a visit stack) that can prove a path between two points in an undirected graph, and it turns out that you can transform the graph into another one that will guarantee that you will visit every node in a certain amount of time. The found result has a new graph that replaces every node with more nodes than exist atoms in the universe, so it technically meets the requirements but is completely and totally impractical. Sometimes people handwave this possibility by saying that once an algorithm is found, people will find better results, but this result hasn't been improved on in close to two decades.
* "Simple" algorithm for an NP-complete problem. This is the result that really, really changes things. Once you get a simple algorithm for one NP-complete problem, you can generally find analogous ways to get simple algorithms for other NP-complete problems. However, the research done to date does suggest that this is perhaps the least likely solution: looking at the "hard" instances of SAT problems, it does seem that there is a certain complexity that is at best reducible via some sort of combinatorical nightmare construction rather than the kinds of decompositions that yields "simple" algorithms.
P means you don't have to try every single possible answer.
But lots of algorithms fit that description while still being impractically slow. Keys might still be uncrackable.
https://scholar.google.com/scholar?cluster=14678868687868063...
A classic paper that explores what happens if various scenarios come to pass. Would be worth exploring some of the updated versions and fictionalizing them.
In the end, as the world burns, I will helpfully explain how I was right.
It would be fun fodder for a sequel, but I feel like it'd come across as histrionic disaster-porn.
For now, I am taking it with a spoon of salt but with an interest of any follow-ups and peer review.
It seems like we're safe for now.
Yeah, that alone is impressive. Schneier led a group that wrote Twofish, which was one of the AES finalists before losing Rijndael.
Not writing this to dunk on Schneier so much as to relate that cryptography is specialized, and that generally there aren't a lot of people that you'd expect to be ultra up on PQ key exchanges and modern block cryptography.
It also contains some links to critique of the Schnorr's algorithm paper. It looks like either much more p_n-smooth integer pairs are needed or the size of the p_n-smooth integers should be much bigger than estimated by original Schnorr's paper. Or both estimations are off.
As the paper discussed Schneier relies on the assumptions of the (classic) Schnorr's algorithm, it may also be off in the calculations as well.
Until we switch to quantum resistant algorithms, we can keep doubling the key length for some time no?
8192 bits should still be acceptable speed wise (if we consider that 2048 bits is broken, then I'll take slower operations over broken keys any day of the week).
If a quantum computer can break 2048-bit RSA, what about elliptic curves?
https://en.wikipedia.org/wiki/Post-quantum_cryptography
https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...
>In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper.
In Ukraine, I hear inside, one law enforcement agency asked big provider ~ in 2000 to gather all emails. Co-owner said, "ok, you will got it". Than he few weeks gather old hdds from everywhere, and once sent to this agency small truck with few hundreds hdds, filled with data.
After that, at least 10 years, nothing similar asked.
Colleague said, he considered to build internet in Uzbekistan, even visited country. What he see, they have all very unfriendly or extremely conservative (Afghanistan) countries around, so he cannot just buy external internet channel.
Internet there extremely slow, most time near impossible to use, only email working (but could delay for few hours).
To send tweet or whatsapp, start app, push "send" and lay phone/tablet alone turned on, and in few hours will see "message delivered".
Would like to hear informed thoughts on any state's pros and cons of sharing such obviously weaponizable discoveries.
If I were a country who could easily just drop bombs on people to cause destruction, then I'd rather leak something that I have no defense against in the hopes it gets patched rather than save it as a tool to use.
If you want to be safe, you might almost consider standard cryptography on one of the three-remaining post-quantum algorithms to be (hopefully) safer. Also this might be bad news for Bitcoin in the ultra-long-term...
Since your wallet address is a sha256 hash of the public key, you would need to meaningfully break sha256 to be able to go after a public key or generate a false signature.
Once the public key is broadcast to spend the funds, that wallet shouldn't be reused, and a new wallet address should receive the change.
To explain why, we need to talk about a type of nonstandard transaction people used to do as a sort of puzzle: hash-only outputs. This is a Bitcoin transaction whose outputs can only be spent by someone who knows the input that gives a particular SHA-256 output. Cute, right?
Problem is, this is a proof of knowledge, not a proof of identity. Anyone else can replicate it once the problem is solved and the solution does not restrict itself to whoever is identified as the first solver. Which means that the only thing that keeps people from claiming THEY were the first to solve it is the Sybil-resistance that keeps the blockchain from being reorg'd.
In Ethereum we call this the "dark forest" problem[0] - anything in the mempool that is not cryptographically locked down can and will be manipulated to the benefit of others. Smart contracts make it way more lucrative to scan the mempool for manipulable transactions, because instead of looking for the one guy solving old SHA-256 puzzles you now have potentially millions of arbitrage opportunities to find. But this isn't limited to Ethereum. It's whoever mines[1] the block wins.
So if quantum computing breaks RSA, that turns all existing coins into SHA-256 puzzles on a blockchain whose users haven't internalized the maximal extent of transaction malleability. The only way to avoid having your coins stolen would be to coordinate with trustworthy miners to include your signature transition transaction into a block - almost certainly with a very large fee, effectively a cooperative confiscation[2]. Those who rely on the kindness of strangers (read: the mempool) will find quantum computer owners and miners fighting to see who can steal their coins first. And the only protocol-level change to fix this would be to just invalidate all RSA signatures and treat all old wallets as burned.
[0] https://www.paradigm.xyz/2020/08/ethereum-is-a-dark-forest
[1] The Ethereum term for this is Miner Extractable Value, which reportedly has even incentivized miners to reorg blocks (i.e. a short-term 51% attack) if and when they can get away with it.
[2] This is, again, another thing Ethereum's ecosystem already thought of; they call it Flashbots.
Regarding changes that still maintain or even enhance this goal of long-lived store of value, I bet they'd be fine with that, even if the work effort of BTC transactions increased.
I see what you did there. And I approve.
But it's also just the case that any "new" (for values of "new" that include "old but never deployed at a scale sufficient to attract scrutiny") encryption primitive, PQ or not, stands a decent change of being breakable by a laptop, at least in its initial implementation parameters. That's what happened with the supersingular isogenies you're referring to. That's just to say: there's nothing special about the "PQ-ness" of these protocols that makes them risky; all cryptography is risky. It took a surprisingly long time --- well into the 2000s --- to figure out how to safely deploy RSA.
Virtually every serious PQ implementation proposal pairs the PQ key exchange with a "conventional" key exchange, for this reason.
If you believe that QC is going to break "conventional" cryptography, Bitcoin is toast; I don't think there aren't a lot of extra "ifs" to that. Smarter people than me think there might be a window of time where RSA falls and ECC survives; maybe you could hope that Bitcoin would react quickly enough inside that window.
You use post-quantum with a vetted algorithm in a hybrid scheme, usually this just involves concatenation or hashing.
Since the "recipient" address of a UTXO is expressed as a hash, a user does not broadcast their public key until after they spend the funds. If you follow good practice, you make a single transaction, sending funds to the recipient, and the "change" to yourself, in a new wallet address (addressed by the hash of its public key). This means the public key is never visible to an attacker until its balance is zero.
Therefore, to attack this and steal funds through false transactions, you effectively need both a pre-image attack on SHA256 (so you have a valid public key to match the UTXO address), and a way to solve the discrete logarithm problem, breaking ECDSA (on the Secp256k1 curve), so you can sign using the private key corresponding to that public key.
SHA256 would come under Grover's algorithm, I believe, which would give you 128 bits of security under a quantum attack. That is still pretty good going.
This part is just a tad questionable. To spend funds, you have to get the transaction recorded in a block. The usual way to do that is to broadcast it through the whole network until a miner picks it up.
So there's more than a bit of wiggle room between "I broadcast everything about this tx" until "the money is already spent and I'm safe.
It certainly does (in the usual case where the vast majority of the network and your connection to it is not under the attacker's control) limit the time an attacker has to compute, but it's not exactly pretty or reassuring.
Because Bitcoin is centralized, if it would get cracked tomorrow, the major miners could decide to save everyone.
It might not be magic, but it might as well be ( and may end up being next hype train ).
My own lesson from the Snowden revelations is that if we're close enough to a security break that the possibility is well understood, there's a very high chance someone is already doing it.
[1] https://blog.cloudflare.com/post-quantum-for-all/
[2] https://cloud.google.com/blog/products/identity-security/why...
[3] https://www.amazon.science/blog/preparing-today-for-a-post-q...