9 ms·
NSA seeks to build quantum computer that could crack most types of encryption
- tptacek 13y ago1. $80MM isn't even in the ballpark of what it would cost to build a quantum-theoretic machine that could break IFP (RSA) or DLP (DH, DSA) crypto. 2. $80MM is way, way past the threshold believed to be required to break the most widely deployed public-key crypto, RSA-1024. Put differently: there are venture capitalists who could successfully fund an effort to break the most widely-deployed public key crypto. 3. If it is feasible to build a quantum-theoretic machine to break RSA, it is vitally important that the NSA attempt to do so; such work is at the very core of their mission. I have no insight into what's actually happening behind this disclosure, but the price tag on it suggests to me that it's just a research project. Since NSA is the kind of organization that historically spends $80MM on paper clips, the number suggests to me that quantum-theoretic attacks on IFP and DLP crypto aren't currently a serious thing. But that's a wild guess.
- Snail_Commando 13y agoWhat do you think would be the correct order of magnitude of cost to build "a quantum-theoretic machine that could break IFP (RSA) or DLP (DH, DSA) crypto"?
- tptacek 13y agoJudging from the current state of quantum computing? For the USG to allocate funds with the expectation of a reasonable chance of success? Billions of dollars.
- dl8 13y agoWhy exactly would it cost so much?
- tptacek 13y agoBecause it involves a result that would be new to computer science and electrical engineering?
- b6 13y agoI wish people could make requests for supporting information like the grandparent post did without getting this kind of snarky reply. Sometimes questions are just questions, not attacks.
- HCIdivision17 13y agoIn this case, it would be easiest to simply read the sentence as though there's no snark, as I'd bet it's the correct answer. Quantum computing is brilliant at certain types of computation, it's not a Singularity-level silver bullet. Simplified to the point of lie, it can transform certain classes of computation by taking shortcuts; the oft referenced Shor's algorithm, for example, can factor a prime in polynomial time, which is immensely faster. [0] But that wouldn't necessarily be enough to break crypto, as anything that wasn't based on factoring a polynomial would need another algorithm. Also, while fast, the algorithm is not instant nor easy to run: a lot of qubits would be needed, and the current state-of-the-art can't support that level of computation against large numbers without a prohibitive amount of expense (qubits are not naturally stable at room temperature). For comparison, factoring a 1024 bit number would take 1024 qubits together, while only a few have ever operated together under ideal lab conditions (Wikipedia notes IBM's accomplishment factoring 15 with 7 qubits, and notes the number 21 was factored in 2012). There is a huge amount of work in the pipe, and there's plenty of room to be shocked and amazed by new developments. But it will require innovations that would revolutionize whole industries. This is still very new tech, decades from maturity (though naturally not from commercial early-adoption). At least, I think that's what tptacek meant. Sorta. [0]http://en.wikipedia.org/wiki/Shor's_algorithm http://en.wikipedia.org/wiki/Shor's_algorithm
- deleted 13y ago[deleted]
- Snail_Commando 13y agoI know next to nothing about quantum computing, is such a thing even possible with the current state of QC + billions of dollars? Does the current state of quantum computing excite or keep security researchers awake at night?
- tptacek 13y agoIt's a long-term concern. One way to gauge it is that many researchers working seriously on post-quantum cryptography are far more seriously engaged in pre-quantum work like secure elliptic curve.
- Snail_Commando 13y agoOk thanks, last question and I'll leave you alone. Could you recommend some relatively accessible reading for the layman on how the security world would react to a sudden shift into the post-quantum world? And, in your opinion, how concerned should average Joes and Janes, like me, be concerned about a sudden shift to a post-quantum world? Edit: For example: Would my bank be safe? Would my health records be safe? (On this hyperbolic fear legitimacy scale: Y2K <----> Cryptopocalypse)
- deleted 13y ago[deleted]
- jerf 13y agoNobody really knows. It has not been proved that useful QC is possible. (All existing QC is practically useless, and it is not clear that it is even possible to scale it up. This is not snark; if it ever will be useful, we must of course walk before we run.) It is possible that there is no amount of money that will make it useful. It has also not been proved to be impossible, and interesting and tantalizing breakthroughs have been made over time such that it's hard to look at them and firmly promise it's impossible, either. (I fall on the skeptical side myself, but it's what I call "true" skepticism; produce it and I won't try to argue out it out existence, I'll just update my beliefs and move on. And celebrate whoever produces it for doing what I believed to be impossible.) This is rather like commercial fusion research; it has not yet been shown to even be possible to economically use fusion for power generation, yet it has not been proved impossible either. Contrast this to nuclear fission research, which at this point is more like engineering; modulo lawsuits and administrative compliance, we could probably take a pretty good guess at what it would take to, say, bring a commercial thorium reactor online.
- deleted 13y ago[deleted]
- sillysaurus2 13y agoWhat would you use as an RSA replacement? Beyond that, is there a technique that's still relatively simple like RSA (humor me) but impervious to publicly-known quantum attack vectors like Shor's algo?
- tptacek 13y agoHere's a good place to start: http://pqcrypto.org/ http://pqcrypto.org/ (This is Daniel J. Bernstein).
- betterunix 13y agoThe Learning With Errors problem is promising: https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors When last I checked there was still a lot of debate about choosing secure parameters for LWE-based cryptosystems, so it would be pretty risky to start using that right now.
- rdtsc 13y agoI was going to jump in and say ECC https://en.wikipedia.org/wiki/Elliptic_curve_cryptography https://en.wikipedia.org/wiki/Elliptic_curve_cryptography but, searching I found that it is apparently vulnerable to quantum computing attacks (wikipedia points me to: Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202) and also found this: http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurvequantum.pdf http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurve...
- yk 13y agoIn one of the crypto talks at the 30C3 the speaker mentioned that quantum computers are actually a greater danger to ECC, because of the smaller key sizes. ( I think this sounds plausible, but I am not an expert.)
- scythe 13y agoElliptic curve cryptography is logically equivalent to prime-factorization cryptography in a sense: both are special cases of the hidden subgroup problem. DLP is also a version of the hidden subgroup problem. Any variant of HSP can be broken by a quantum computer using a variant of Shor's algorithm.
- pnathan 13y agoQuantum computing is undergoing active research and productization (there's a company in Vancouver, BC - D-Wave - working on making a quantum computer product). Historically, quantum computers are considered to be have crypto-breaking applications. > If it is feasible to build a quantum-theoretic machine to break RSA, it is vitally important that the NSA attempt to do so; such work is at the very core of their mission. This is a key thing to remember - expect groups tasked with breaking crypto to be working on breaking crypto. In other news - Pope is Roman Catholic, water is wet. :-)
- eli 13y agoThere are also more than a few people who think D-Wave is selling cold fusion: http://en.wikipedia.org/wiki/D-Wave_Systems#History_of_controversy http://en.wikipedia.org/wiki/D-Wave_Systems#History_of_contr...
- dekhn 13y agoIt would generally seem they've silenced all but a few of their most vehement critics with the latest round of publications (which seem to suggest they are doing better than some of the best CSAT solvers on uninteresting problems). There is some suggestion the next round of hardware will have enough q-bits to do something "really interesting", but I'm still quite skeptical that the device, even if a truly functioning quantum adiabatic machine, shows any sort of true entanglement in a way that would satisfy the non-adiabatic QM aficinados.
- tptacek 13y agoD-Wave is what makes the $80MM number look so small: nothing D-Wave has done has come close to threatening cryptography of any sort, and D-Wave has taken almost $80MM themselves.
- fiatmoney 13y agoD-wave's system is fundamentally not amenable to cryptography. As they describe it it's a quantum annealing system; good for finding optimal parameters to some loss function, but not for instance Shor's algorithm.
- philipn 13y agoIf you're curious (as I was) about the estimated cost of breaking RSA-1024 check out this paper: http://tau.ac.il/~tromer/papers/cbtwirl.pdf http://tau.ac.il/~tromer/papers/cbtwirl.pdf tl;dr - estimate is ~$10M
- jaibot 13y agoNote that this is $10M _per RSA-2014 key_, whereas the hypothetical quantum computer can crack all of them.
- MichaelSalib 13y agoIs it really $10M per key? DJB points out that if you're willing to spend a lot of money building parallel hardware, you can get some surprising performance benefits allowing you to crack large numbers of keys at once. http://cr.yp.to/snuffle/bruteforce-20050425.pdf http://cr.yp.to/snuffle/bruteforce-20050425.pdf
- Crito 13y agoPer that paper, it would be $10M per 'device', with one device managing one key per year. Of course you might as well build more hardware while you are at it.
- MichaelSalib 13y agoI'm not sure about that; the paper talks about parallel machines that can search out many keys at once. Its focus is on known plaintext attacks against AES, but it seems like the techniques described could apply to IFP for RSA. I'm not a cryptographer so I could be totally off base here.
- Crito 13y agoI only had time to skim it, so you might be right. Either way, I think it is only safe to operate with the assumption that 1024bit keys are well within the grasp of projects with modest funding.
- haberman 13y ago> Put differently: there are venture capitalists who could successfully fund an effort to break the most widely-deployed public key crypto. Are you talking about the hardware cost to brute-force a particular keypair, or the cost of somehow compromising the algorithm completely for everyone?
- tptacek 13y agoHardware cost and engineering cost to build the hardware.
- ams6110 13y agoWhat's the < $80MM way to break RSA-1024? $80MM of GPUs? If its just a matter of that amount of money, then the NSA has almost assuredly already broken it, no?
- tptacek 13y agoYes.
- chm 13y agoI've just recently set up GPG for my family using 4096 bit keys. How long do I have, assuming no hole is found, before needing to change?
- tptacek 13y agoThat's a better question for 'pbsd, but 4096 bit keys are infeasible to attack (outside of quantum computing) using any technique currently known to science. I'm fond of saying that the thing that takes out RSA-2048 is likely to take out RSA altogether, so, over the medium term, look to Elliptic Curve instead of RSA. New systems should be designed with ECC instead of classical IFP/DLP crypto.
- kro0ub 13y agoECC is invulnerable to quantum attacks? According to pqcrypto.org, ECC is "dead, dead, dead."
- tptacek 13y agoYes, ECC is vulnerable to quantum attacks; we aren't talking about quantum attacks on this subthread.
- kro0ub 13y agoIs it unreasonable to call a thread that decidedly ignores quantum attacks worthless? I mean, absolutely speaking, given that quantum attacks really are or will be out there, is it not bad advice to suggest systems be built with quantum-vulnerable algos?
- aet 13y agoDefense budget is $500 billion+
- MacsHeadroom 13y ago"Aren't currently seriously a thing" as of 3-5 years ago. Aren't the most recently dated revealed Snowden docs almost 3 years old with the bulk being ~5 years old?
- scythe 13y agoHi! I do research in quantum error correction and topological quantum memory. There is absolutely no way that the NSA or anyone else is going to build a quantum computer in the next twenty years. The reason is that the overhead of error correction is, while feasible to meet long term, too large. The number of physical qubits that must exist in a system that can work with K logical qubits is O(K log(E)^c), where E is the logical error rate, which must be inversely proportional to the total runtime of the maximal feasible algorithm, and c is a constant that depends on the memory architecture (quantum error-correcting code, in general a subsystem of a degenerate ground state of an effective Hamiltonian on the qubits). Shor's algorithm requires ~3N logical qubits and O(N^3) steps, where N is the length of the number to be factored. The minimum feasible size for a computer that could perform this calculation on a typical 2048-bit semiprime is several hundred thousand physical qubits. By contrast, the largest quantum computer thus far constructed has less than ten qubits. Even if we double every 18 months (not at all likely), that's a good 22 years away with the most optimistic outlook for quantum stability. Far more than 80 million dollars has already been invested into quantum computing research. I think it's money well spent, but it's not going to change the nature of the problem.
- salient 13y agoThe problem is that if quantum computers are viable in 20-30 years, then we need to start using quantum-resistant algorithms today. The NSA has already admitted that they are especially holding on to encrypted data for longer periods of time (and after the Utah data center, probably forever). In 20 years time they can start decrypting all that data with a quantum computer. Think about it. Today's 20 year olds, could be tomorrow's 40-50 year old politicians. All sort of juicy data could be abused then to discredit, or worse, blackmail those politicians. Right now the best weapon against it seem lattice-based encryption, so we should start working on it, so we can start using lattice-based cryptosystems within 5 years, which is a pretty small amount of time to verify this type of encryption and make it very usable, but I don't think we can afford more than that. Homomorphic encryption using lattices is something companies like Google should already be researching and trying to implement, if they really care about user privacy (and they should, because I predict an increasingly hostile movement towards Google's data mining in the future, and they need to take steps to "fix" all the privacy invasions they are currently doing with their data mining).
- GotAnyMegadeth 13y agoSorry, slightly off topic, but why do people sometimes put $80M and sometimes $80MM? What is the difference? Thanks
- beagle3 13y agomm and bn are standard financial notation for million and billion. M and B are used by everyone else.
- GotAnyMegadeth 13y agoThanks. I think I'm going to start using £10M and £10G
- EthanHeilman 13y agoThis is the first leak that lower bounds the NSA's capabilities. It suggests that the NSA does not have a quantum computer. If the NSA did have a quantum computer they might fund a project like this as it would be suspicious not to. EDIT: The more I think about this, the less it says about the NSA capabilities. They may attempt multiple paths to QC. The classification document that WashPo released (http://apps.washingtonpost.com/g/page/world/classifying-nsa-quantum-computing-efforts/692/ http://apps.washingtonpost.com/g/page/world/classifying-nsa-...) outlines Level A (public) and Level B (classified) research. All this shows is that the NSA is dedicating at least ~0.8% of their budget to QC.
- dnautics 13y agoI think you mean "upper bounds" the NSA's capabilities.
- EthanHeilman 13y agoYou are correct, but now hn will not let me edit it.
- jrwoodruff 13y agoFull version of the article, with sane paragraph measures and distracting teasers and social features. http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html http://www.washingtonpost.com/world/national-security/nsa-se...
- ck2 13y agoWhen the limit to breaking encryption becomes only cost and not technical hurdles, we have a huge problem. Because there is no limit to tax dollars the government would be willing to spend to spy on it's own citizens. Congresspeople are already happy to line up to throw money at the spy machinery which is the new arm of the industrial war complex.
- joshfraser 13y agoIt's not even tax dollars. The Federal Reserve is at the root of many of our problems -- congressional spending, the industrial war complex & NSA spying -- none of it would be possible if we weren't able to create money out of thin air.
- samstave 13y agoThus illustrating exactly who is running the world and why when Occupy started up they actually drafted plans to have LEOs assassinate the "leaders" of Occupy. This underscores the need to revive Occupy.
- orthecreedence 13y agoNot to be a jerk, but Occupy was ineffective. Let it RIP. It spent so much time being leaderless they couldn't decide what the hell they wanted. We have to be more targeted about the changes we want. "We're pissed off about lots of stuff and you better fix it all or else!" isn't going to work. At this point though, it's almost like the house is completely engulfed in flames. Which section do we put out first? - The corrupt banking and money system? Our capitalist system is an immense ponzi scheme. Economists act like you can have infinite growth. Forever. They're delusional. At some point, you run out of people's back to crawl on top of and your system collapses. - On top of that, we have a one-party system: the capitalist-imperialist party. It is impossible to get a non-capitalist-imperialist elected in the United States! We need a voting system overhaul, but good luck getting that when everyone is bickering about abortion and gay marriage. The system has successfully turned us against ourselves on issues that do not affect the overall outcome of the nation, leaving the people in charge to do whatever they feel like. - We have a government agency with a bottomless pit of money spying on everybody, effectively cutting off our freedom of speech (who is going to speak out against the government when a giant eyeball hovering over them at all times?) At this point, there's no ring to cast into the volcano either. Even if the NSA's activities are ruled unconstitutional, who's going to stop them? - Our country's leaders are spending millions to create more terrorists by bombing countries in the middle east with drones. You take out some kid's house and family with a drone, what do you expect is going to happen? They'll thank you for keeping the streets safe? No, they grow up to be a "terrorist." I hate to be one of those "the sky is falling" nerds, but if it takes as much work and pressure as it has to get the people around you to barely even raise an eyebrow at what's going on, you know you're not headed for something good.
- deleted 13y ago[deleted]
- topynate 13y agoBoth NSA and GCHQ have quite the history of co-opting smart mathematicians to create secret theoretical advances in cryptography and cryptanalysis, which could well be relevant given a quantum computer with the following three properties: * Fully general. By this I mean capable of solving BQP problems in polynomial time. This excludes D-Wave machines, for example. * Sufficiently large. 100 qubits would probably enable qualitative advances in cryptanalysis. * Low enough error rate. This is a slightly redundant requirement, as too high an error rate would provably prevent the computer from being asymptotically faster than classical - which is what we care about. The last requirement is due to the quantum threshold theorem[1]. Briefly, there is an error rate below which quantum computing is possible and above which it is not. The precise value is not known but it is probably over 1% and, at least for some kinds of circuits, under about 40%. That means that at the theoretical level, the task is to create a model of computation that has as high a threshold limit as possible, and then to design an error correcting scheme that comes close to that limit. This is something that a secret agency could plausibly do in-house. However, there is then the question of implementing the model of computation in a physical system, with a sufficiently low error rate. NSA, GCHQ etc. are not known to have this sort of experimental expertise - they would probably have to contract it out (and indeed this is the major piece of new information in the article). The history on fundamental advances over civilian technology shows that this normally depends on co-opting basically the entire research community working in the field - as in radar, nuclear weapons, stealth etc. This is not at all the case for experimental quantum computing, which is not in practice treated as a 'sensitive' field. Thus it is my opinion that the NSA may well already have some theoretical tricks up its sleeve that it can use in the future for a decent edge, but is unlikely to get the opportunity to use them before quantum computing becomes considerably more feasible in the unclassified world. [1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem https://en.wikipedia.org/wiki/Quantum_threshold_theorem. Bounds lifted from http://arxiv.org/abs/0802.1464 http://arxiv.org/abs/0802.1464. Qualifications: I studied the mathematics of quantum computing as a Masters student, although I can't claim to still be current on the state of the art.
- Snail_Commando 13y agoIf you had to pick, say, three books (or the online equivalent) on quantum computing that are relatively accessible to an educated layman, which ones would you recommend?
- redthrowaway 13y agoGood. That's their job. I'm not worried about the NSA using quantum computing, as fiscal realities dictate that it would have to be narrowly targeted at a small subset of the encrypted information out there. I'm fine with them recovering plaintext from pgp-encrypted emails sent between suspected al-Qaeda members. I'm not fine with them break encryption en masse and compromising the integrity of the Internet.
- bashinator 13y agoI thought the whole point of using quantum computing to break crypto, is that you can break encryption (e.g. RSA private keys) en masse for the same or less cost than traditional computing requires to break them one-at-a-time.
- PavlovsCat 13y agoApologies for being extremely clueless, I don't even understand advanced math, not to mention encryption, not to mention "quantum stuff" - that's why I ask here: is it theoretically possible (or could it be in the future) to use quantum computers for encryption, too? If so, would that reduce options for breaking it to "brute force on the quantum level"? Does this question even make sense?
- topynate 13y agoI don't know of any research into this area, but it's conceivable that you could have an encryption algorithm that is polynomial time (given the key!) on a quantum computer but exponential time classically, and that has some better security guarantees given certain common assumptions. However, quantum algorithms of any sort are difficult enough to invent that we'll likely end up using classical algorithms that 'look' hard to break with quantum computers, i.e. ones where prime factoring doesn't help. The real quantum defence appears to be something rather different. Quantum cryptography (https://en.wikipedia.org/wiki/Quantum_cryptography https://en.wikipedia.org/wiki/Quantum_cryptography) uses polarised photons to create very strong guarantees that your communication is secure. We can say that if you do the engineering correctly, the laws of physics would have to be violated to intercept your messages.
- tptacek 13y agoThe "quantum cryptography" you describe here isn't a defense against quantum cryptanalysis; it's more like a novelty act. http://rdist.root.org/2008/10/24/quantum-cryptography-is-useless/ http://rdist.root.org/2008/10/24/quantum-cryptography-is-use...
- gamebak 13y agoI didn't know when it was going to happend but i knew it would. That 80m investment is nothing, imagine if they will use it to crack sha256 from bitcoins ? A 9-10 billion "business" opened for them. Plus, privacy = lost
- f_salmon 13y agoOr: How to reduce the value of the Internet as much as possible for everybody. Nice, really nice.
- crystaln 13y agoThis is the sort of code-breaking the NSA should be doing. If breaking encryption algorithms is possible with quantum computers, we should figure out how to do it before any other nation-state or hacker does. This discovery would hopefully push forward encryption standards toward less breakable encryption. What we should not do is use those discoveries to illegally spy, but rather to improve our security. Unfortunately, the NSA has lost credibility in contributing to encryption standards, so how that would happen is unclear. Breaking encryption with new technology is entirely different than subverting encryption technologies intentionally or using their asymmetrical powers to tap into communication systems. Any attacks that can be discovered will hopefully first be discovered by relatively good actors (US intelligence) rather than relatively bad ones (Chinese intelligence.)
- yuliyp 13y agoIf the NSA was able to break RSA, there's about a .1% chance they'd tell people about it.
- chronic25 13y agoI'd argue it is 3.50%
- crystaln 13y agoIf the NSA broke RSA, they'd know that it was only a short matter of time before other intelligence agencies did the same, so it would be pretty stupid of them to not hint to industry that they should upgrade their algorithms. While the NSA wants communications to be vulnerable to them, they certainly don't want communications to be vulnerable to others.
- dionyziz 13y agoYou don't need a quantum computer to break encryption in order to know that it's breakable. This has already been proven (Shor's Algorthm). You also don't need quantum computers to construct stronger cryptography, immune to quantum cryptanalysis. This has also already been done as well (post-quantum cryptography).
- BostX 13y agoRLY? OMG, who would expect that?!?!
- throwawayusa 13y agoI honestly don't understand why the NSA bothers with this. All they have to do is claim that someone is a threat and they are then able to seize said person, secret them away, and make them an unperson in some government facility that we've yet to learn about.
- msoad 13y agoWhat they want is information of such person BEFORE they were accused with the crime. Therefor they need all the information of everyone!
- 2810 13y agoso Bitcoin is doomed?
- dionyziz 13y agoIf we have quantum computers, yes. By that time, we'll upgrade our elliptic curve algorithms to post-quantum cryptography however.
- bitsteak 13y ago"Physicists and computer scientists have long speculated about whether the NSA’s efforts are more advanced than those of the best civilian labs. Although the full extent of the agency’s research remains unknown, ___the documents provided by Snowden suggest that the NSA is no closer to success than others in the scientific community.___" Nothing to see here but false outrage and surprise, move along.
- cowardlyanon 13y agoPSYOPS101 - Make it public that you seek something you already have.
- veganarchocap 13y agoWait what? The NSA is still going? Surely it should be shut down after its discovery, and the mass outrage it caused worldwide. The fact they're continuing their work, is blatant contempt and disregard for not just the citizens of the U.S. but for the rest of the world, too. American tax payer money goes to fund this, it's absolutely criminal. They're expecting you to pay for them to spy on you, for you 'safety'. We need counter measures or to target them directly. They need taking down. It's absolutely insane, 'okay, you caught us! But we don't care!' is the message this act emits.
- dandare 13y agoI, for one, welcome our new quantum overlords. Seriously, I don't think it's illegitimate to pursue new technologies that would render the old ones obsolete.