Hacker News Reader

Comment by tptacek | Hacker News Reader

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

View on HN

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

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

If 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

tl;dr - estimate is ~$10M

Note that this is $10M _per RSA-2014 key_, whereas the hypothetical quantum computer can crack all of them.

Is 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‎

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

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

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

So, say, throw $80 million or so at the problem?

Yeah basically. But if this is what the NSA were actually doing, I suspect they'd be throwing way more than $80M at it for a handful of devices, and instead be throwing half a billion at it for half a datacenter full of them. Why build a dozen or two crackers when you have the money for hundreds?

I think this sort of budget indicates more of a research project.

That paper does not apply to integer factorization, and number field sieve computations in general. DJB himself, in another paper [1, §5], argues that is more cost effective to factor one number at a time.

[1] http://eprint.iacr.org/2012/318

No, it's $10MM per key/year. Or, it was, back in 2001.

Huh, apparently I've already developed muscle memory for typing "2014". This is going to make writing certain powers of two difficult.

The thing is, we can never know how much many is put into what, as long as we accept that the government is allowed to take and hide money from the taxpayer like this: http://www.washingtonsblog.com/2013/11/8-5-trillion-taxpayer...

That paper is about 10 years old, or at least the research is. The most current source cited is from 2003. I like to think we've made significant progress in a decade, but in reality inflation would probably be enough by itself to throw those numbers completely out the window.

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

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

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

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

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

What 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?

Here's a good place to start: http://pqcrypto.org/

(This is Daniel J. Bernstein).

The Learning With Errors problem is promising:

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.

I was going to jump in and say ECC

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

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

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

How broken is the question - NSA cracks 2048 keys we just double the key size and are safe for 3-4 more years, or making it so trivial it doesn't matter how big the key size is.

Lamport signatures.

What'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?

Yes.

I'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?

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

ECC is invulnerable to quantum attacks? According to pqcrypto.org, ECC is "dead, dead, dead."

Yes, ECC is vulnerable to quantum attacks; we aren't talking about quantum attacks on this subthread.

Is 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?

See: scythe's post https://news.ycombinator.com/item?id=7004561

Assuming nothing changes, 4096-bit RSA has around 160 bits of security, roughly equivalent to 320-bit elliptic curves.

Depending on how Moore's law progresses and our understanding of the Universe, you may never need to change (ignoring all other possible ways your key can be acquired).

4096 is secure. Better to setup 256 bit ECDSA, just for thesmaller size however.

If you're interested in seeing how to implement it, the NSA apparently has a nifty guide:

http://www.nsa.gov/ia/_files/ecdsa.pdf

What 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"?

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

Why exactly would it cost so much?

Because it involves a result that would be new to computer science and electrical engineering?

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

In 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

> the oft referenced Shor's algorithm, for example, can factor a prime in polynomial time, which is immensely faster.

Actually, Shor's algorithm is for factoring composites, not factoring primes.

Don't feel bad about that little word mixup. You are in good company. Bill Gates did it in his book "The Road Ahead".

Not gonna lie, I feel a bit dumb for that. Factoring primes is as useful as a one-input mux, as a college roomie would say.

True, but sometimes questions also don't show a whole lot of effort on the part of the asker, and so the answerer is not inclined to put in much of their own. If I'm going to ask a question and want a thorough answer, I try to at least provide a little background on what I already know.

I 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?

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

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

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

Well anyone with photovoltaics can demonstrate working economical fusion power at a certain large scale. At least there is an existence proof at the extreme there, which QC does not have.

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

Hardware cost and engineering cost to build the hardware.

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

Sorry, slightly off topic, but why do people sometimes put $80M and sometimes $80MM? What is the difference? Thanks

mm and bn are standard financial notation for million and billion. M and B are used by everyone else.

Thanks. I think I'm going to start using £10M and £10G

Defense budget is $500 billion+

Reply on news.ycombinator.com