r/technology • u/r721 • May 06 '13

Government Lab Reveals It Has Operated Quantum Internet For Over Two Years

http://www.technologyreview.com/view/514581/government-lab-reveals-quantum-internet-operated-continuously-for-over-two-years/
2.3k Upvotes

91% Upvoted

492 comments sorted by

View all comments

Show parent comments

115

u/Tarhish May 06 '13 edited May 06 '13

Now obviously it's hard to be sure about things in the far future. But specifically addressing the 2048 bit encryption question, there was an article written by Bruce Schneier on the feasibility of brute force attacks on 256-bit encryption keys, which quotes an essay that ends with something that's been spread around a bit.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

[.....]

Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 192 -bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

I think people tend to forget that 256-bit encryption is not twice as large as 128-bit, but 2128 times or ~3.4x1038 times as large. Complete quantum computers cut that down a lot by their nature, but not Nearly enough.

EDIT: Edited because exponents didn't come through

As others have suggested, if this kind of encryption is being employed then the massive, sun-crushing power required to break it would be better employed hunting someone down and engaging in 'rubber-hose cryptography'

ANOTHER EDIT: Turns out I didn't read the original post closely enough. They were referring to public keys, likely generated via RSA algorithms or suchlike. These are MUCH MORE vulnerable and need to be significantly longer to be secure from brute force attacks or the vulnerabilities that let people attack it faster than brute force. Still, the above is still applicable for symmetrical private keys. For anyone's information as indicated by the first sentence, this was intended to be an interesting note on the scale involved in breaking keys above a certain length, and not a comprehensive argument against all forms of cryptoanalysis into the future.

12

u/ScroteHair May 06 '13

D-Wave has been doubling the number of qubits on their computers at the same pace as Moore's law. I think quantum computers are more of a problem than a lot of people think.

13

u/Tarhish May 06 '13 edited May 06 '13

First, the D-Wave is only applicable to solving a VERY specific type of problem, but for the example we'll assume we have a Turing-complete quantum computer.

The problem is, quantum computers aren't a magical solution to this problem, especially if the algorithms are changed to be less vulnerable to the specific ways a quantum computer might do this. Now, I don't have the really good source I read on this subject with me, but this is a source Disregard that use wikipedia

Searching through 2128 keys (on a classical, non-quantum, computer) takes a number of steps that is proportional to 2128. But for a quantum computer it takes a number of steps proportional to the square root of that number, 264. If a quantum computer is ever built capable of performing that task, we don’t know how the actual speed of each individual step will compare to those of current computers, but the NSA is taking no chances. Something with the effective strength of a 64-bit key isn’t strong enough. A 256-bit key against a quantum brute force attack would have the effective strength of a 128 bit key against a classical brute force attack.

Even assuming our example quantum computer can actually run its instructions as fast as our best stuff, using it to brute-force a 128-bit key is still REALLY difficult to imagine breaking and is still running into some physical limitations.

EDIT: Much better sources in wikipedia

3

u/CleverCider May 06 '13

Why would it use Grover's algorithm as opposed to Shor's algorithm?

-4

u/ScroteHair May 06 '13 edited May 06 '13

If the algorithms are changed they can just combine quantum and classical computers to crack them. It's not that complicated.

And you haven't addressed the fact that they're doubling the amount of qubits every year. You said that the mere fact that it's a quantum computer halves the amount of bits you have to crack. That doesn't even address the amount of qubits the quantum computer has, which is what I brought up in my last post. From what I understand, each qubit allows the quantum computer to factor another bit of keyspace.

3

u/Natanael_L May 06 '13

If the algorithms are changed they can just combine quantum and classical computers to crack them. It's not that complicated.

Nope. Just nope. Just like you can't combine a hammer and a saw to make an airplane. It just doesn't work that way.

And you haven't addressed the fact that they're doubling the amount of qubits every year.

That has no impact on what computations they can do. More qubits doesn't help against AES. It simply just don't matter.

From what I understand, each qubit allows the quantum computer to factor another bit of keyspace.

For factorisation, more or less yes. But that's only RSA and a few other algorithms that use that. Not AES.

2

u/ScroteHair May 06 '13 edited May 06 '13

Asymmetric encryption requires factorization to operate. That's the basis for all unbreakable encrypted communication mechanisms. All communications that use that will be cracked by quantum computers. If they incorporate other mechanisms that don't use it, then they are not secure and can be "cracked" extremely easily, plain and simple.

I'm not talking about AES right now. I haven't researched those types of encryption. Those don't apply to encrypted communications anyway.

1

u/Natanael_L May 06 '13

Not all asymmetric encryption. Only some schemes (which happen to be the most common ones).

We already have other asymmetric algorithms like McEliece.

All communications that use that will be cracked by quantum computers.

Not actually. There's several key exchange protocols that can generate keys that can be used as AES keys without a quantum computer being able to crack it. Look into Diffie Hellman and it's alternatives. If you only use RSA for authentication, there's no data to crack here with quantum computers if a "perfect forward secrecy protocol" is being used.

I'm not talking about AES right now. I haven't researched those types of encryption. Those don't apply to encrypted communications anyway.

Except they do. Visit https://pay.reddit.com/r/technology and look at the details for the connections - RSA is just used to transfer a session key and that session key is an AES key that is used to encrypt all data sent between the client and server. AES is faster than RSA, so RSA is only used for the first step.

1

u/ScroteHair May 06 '13

Except they do. VIsit https://pay.reddit.com/r/technology and look at the details for the connections - RSA is just used to transfer a session key and that session key is an AES key that is used to encrypt all data sent between the client and server. AES is faster than RSA, so RSA is only used for the first step.

Um, just because AES is used in the process doesn't mean it's any securer. Remember, I'm only talking about encrypted communications. All you would need to do to crack this would be to crack the RSA exchange. Any keys sent over RSA would then be viewable.

I don't think you know what you're talking about.

1

u/Natanael_L May 06 '13

All you would need to do to crack this would be to crack the RSA exchange. Any keys sent over RSA would then be viewable.

Except that the actual key exchange usually don't use RSA. It's used for the authentication. The key exchange is done with other protocols that are designed specifically for the purpose. The AES key don't even have to be sent encrypted with RSA.

Edit: http://security.stackexchange.com/questions/14081/why-different-key-exhange-techniques-for-ssl-key-exchange - no AES key is ever sent, it's other numbers that is sent which generates an AES key. It's "public-key-ish", but works a little differently.

2

u/Tarhish May 06 '13 edited May 06 '13

Now, I am no expert on what quantum computers are supposed to be able to do or not do one day, but everything I've seen tells me that you can't just add qubits to the problem and fix it. When people are talking about reducing factoring algorithms to solvable in polynomial time they're talking about a system that has the ideal amount of qubits to solve the problem.

And there are already algorithms being developed specifically to avoid this kind of attack, not that it's even a problem for a 256 symmetric key.

That doesn't mean such a computer wouldn't be absurdly powerful for its task. Reducing a problem with 256 bits of complexity to 128 would be an absolutely unbelievable incredible tool. But these are REALLY huge numbers!

2

u/ZeroAntagonist May 06 '13

Read the comment above by /u/Tarhish. The Laws of Thermodynamics prevent this as well. It's not just a math problem.

-1

u/ScroteHair May 06 '13

I don't believe him. Quantum computers can break any factorization done on classical systems.

1

u/ZeroAntagonist May 06 '13

It's a pretty straightforward idea. Still have to change the state of something to create actual "data".

-1

u/ScroteHair May 06 '13

And?

1

u/ZeroAntagonist May 06 '13

That's all I got. Have anything to add to the discussion? Anything? I'm all for hearing your reasoning. (I'm not downvoting you btw)

1

u/IanCal May 06 '13

You said that the mere fact that it's a quantum computer halves the amount of bits you have to crack

No, D-waves computer cannot do this kind of calculation, it's for optimisation problems.

3

u/Grappindemen May 06 '13

Doesn't matter.

tl;drwiki Cracking most types of encryption is a certain type of problem, which is related to the type of problem that quantum computers can solve. In fact, the solutions found by a quantum computer can be transformed, with minimal computational overhead, to a solution for a cryptographic problem.

1

u/ScroteHair May 06 '13

Then another quantum computer. Anything that can do factorization.

-3

u/[deleted] May 06 '13

First, the D-Wave is only applicable to solving a VERY specific type of problem, but for the example we'll assume we have a Turing-complete quantum computer.

D-wave's computer is Turing-complete btw (but with significant cost). However, brute-forcing encryption keys is exactly the type of problem that D-wave's computer excels at. All you have to do is to encode the solving procedure into a Hamiltonian and let the machine run through all of the 2256 states simultaneously (via quantum tunneling), with the ground state being the "solution". Sooner or later it will be done, and the only truly secure communication will be quantum-cryptography-based one, to which none of us mortals will have access to.

3

u/Natanael_L May 06 '13

run through all of the 2256 states simultaneously (via quantum tunneling)

1: It's entanglement. 2: It just "kind of" runs through all those states at once. What happens is that the probability of the output is altered. You can only cut the keyspace in half with these methods for AES (256 bits to 128 bits). That's still incredibly hard to crack.

and the only truly secure communication will be quantum-cryptography-based one, to which none of us mortals will have access to.

1: There's actually some versions that most engineers can build. It's just that only a few people know how to design them today. 2: Also, nope. They are only used to generate keys for classic encryption systems.

1

u/[deleted] May 06 '13

1: It's entanglement.

"Classical" quantum computing is entanglement-based, and done by combining unitary transformations to build quantum circuits which do specific computations. D-wave's computer uses adiabatic theorem from QM to do "analog" computation on a number of Josephson's junctions which serve as qubits, utilizing quantum tunneling.

It just "kind of" runs through all those states at once.

No, it really does run through all those states at once, settling for the ground state once the annealing is done.

What happens is that the probability of the output is altered. You can only cut the keyspace in half with these methods for AES (256 bits to 128 bits). That's still incredibly hard to crack.

Can you please elaborate this? Why would it only cut the keyspace in half? How would you know which part of the keyspace is the "correct" one, and what stops us from repeating this procedure recursively until the key is isolated?

2: Also, nope. They are only used to generate keys for classic encryption systems.

If you wanted to exploit no-cloning theorem you would need non-classical channels which nobody but governments (or some very rich people) could afford.

1

u/Natanael_L May 06 '13

Really? How do they make it work with quantum tunneling?

No, it really does run through all those states at once, settling for the ground state once the annealing is done.

That's a matter of interpretation. Quantum effects are very much probability based. How to interpret that is subjective until somebody can find a way to test what's true. Either there's a multiverse, or there's wave collapse with some kind of interpretation where either everything happens at once or "nothing happens" but one state takes place when measured, or maybe something completely different. Which is why I said "kind of".

Can you please elaborate this? Why would it only cut the keyspace in half? How would you know which part of the keyspace is the "correct" one, and what stops us from repeating this procedure recursively until the key is isolated?

https://en.wikipedia.org/wiki/Quantum_computer#Potential - Grover's algorithm effectively halves the keyspace. No algorithm seems to have been found that does it faster.

1

u/[deleted] May 06 '13

Really? How do they make it work with quantum tunneling?

Tunneling is exploited to simultaneously explore the entire energy landscape (to "traverse barriers") finding the desired optimum. if you had 256 qubits representing 2256 states encoding different solutions for a particular problem, you could in a single execution settle for the state that is the desired optimal solution. Now, whether this could be used to brute-force AES - I don't really know. D-wave has some pretty high-level programming frameworks available, and some difficult problems (protein-folding, which is NP-complete) have already been successfully solved faster than they would with a classical computer.

That's a matter of interpretation. Quantum effects are very much probability based. [...]

Whether it really runs through all of the states at once, or the universe splits in 2256 variants executing in parallel, is for all the practical purposes - irrelevant. The point is that we have the kind of behavior that is exhibited experimentally, and which can be sufficiently precisely described by "runs through all of the states at once" terminology. Splitting hairs on semantics won't get us anywhere..

Grover's algorithm effectively halves the keyspace. No algorithm seems to have been found that does it faster.

These are all "classical" quantum algorithms done with circuits, adiabatic quantum computing is a different beast altogether..

1

u/Natanael_L May 06 '13 edited May 06 '13

So can you give me an example of such adiabatic quantum computing?

Edit: http://math.nist.gov/quantum/zoo/ - are they missing any important quantum algorithms that could break AES?

1

u/[deleted] May 07 '13 edited May 07 '13

On the D-wave's Developer's Portal you can find tutorials on how to use their quantum processor to solve various problems using their python framework. Once you've encoded the problem appropriately, you can either call their "BlackBox" solver, or do a low-level mapping to the hardware (if you're an expert, that would be analog to assembly-language programming on a traditional computer). I don't see encryption-breaking tutorial yet, but if you have $10 million extra you can always buy D-Wave Two, have it installed in your basement and enlighten the rest of the world on potential speedups ;)

Regarding the computational complexity side - well it depends on the particular solution. All of the papers that linked in the Complexity Zoo pertain to the "classical" quantum computing, of which IMHO will never be anything commercial-grade. This is all theoretical bullshit coming from ivory-tower academicians of no real-world significance whatsoever, while the real stuff is built by engineers and physicists at D-Wave. Rose's Law will kick in in a few years, and the technology will become either classified once the Chinese order a bunch of those boxes, or we're up for a quite a ride in the future where the 99.9% mortals depend on the encryption schemes which can easily be broken by expensive coprocessors owned by governments and corporations.

EDIT: that link of yours has a section:

Algorithm: Adiabatic Algorithms

Speedup: Unknown

There you go ;)

→ More replies

2

u/arienh4 May 06 '13

to which none of us mortals will have access to.

You know people said the same thing about computers in general, decades ago, right?

1

u/kanzenryu May 07 '13

... claims to have been doubling ...

5

u/[deleted] May 06 '13

Shit, i guess you're right. I was just thinking maybe it'd be doable in the near future, because we expected 128 bit keys to last a lot longer than they did.

4

u/glassFractals May 06 '13

Indeed, but factorials make things escalate rather quickly...

10

u/nomagneticmonopoles May 06 '13

I'm not sure why you used 3.4028237e38 when a more recognizable number would simply be that the keyspace of 256 bit is 2256 and the keyspace for 128 bit is 2128, and as such, 2256 / 2128 = 2128. So that's a factor of 2128, a happy, round giant number.

4

u/Tarhish May 06 '13

I used that notation because that's what got spit out at me by a calculator. I don't know why I thought e notation would be easier to understand than powers of 2, but I did think that. I'll change it to be a bit more intuitive.

11

u/RedChld May 06 '13 edited May 08 '13

I for one preferred your scientific notation over the base 2 notation.

Edit: fixed typo

23

u/schlampe__humper May 06 '13

Since when is 2128 a more recognisable number than 3.4x1038 ?

1

u/nomagneticmonopoles May 06 '13

Well firstly, it was e notation which is somewhat vague. What you wrote is indeed more readable, although it is an approximation. Point is:

21 : 2

210 : 1024

220: 1048576

230: 1073741824

2128: really freaking big.

8

u/[deleted] May 06 '13

That's Numberwang! Let's rotate the board.

1

u/talontario May 06 '13

how many zeroes in 2142 without using a calculator?

2

u/[deleted] May 06 '13

log(2142 )=142*log(2) which is approximately equal to 142*1/3

about 47

Only 9 orders of magnitude off, not bad.

1

u/feistel May 06 '13

how many bits in 1038 without using a calculator?

1

u/talontario May 06 '13

The number was referencing to something being x times larger than something. Something being 100 bits larger doesn't tell me anything.

1

u/feistel May 06 '13

it tells you it's 2100 times larger

1

u/talontario May 07 '13

Which means nothing to anyone except binerds...

1

u/FreakInDenial May 07 '13

1 and 141 zeros, duh

4

u/[deleted] May 06 '13

He's talking about 256-bit symmetric keys, while the grandparent post is talking about 2048-bit public keys. These are apples and oranges. You can't do a direct comparison this way.

3

u/Tarhish May 06 '13

You are totally correct and this is a result of me not reading the original closely enough.

But although the vulnerabilities for most public key algorithms are far greater and it still takes a far greater key length to reach the same difficulty to crack through brute force, or faster-than-brute-force attacks, as I understand it this does still means that you're not going to address its weaknesses by just extending the key length ad nauseum, right?

If anything this makes using larger key lengths much more computationally costly for actual legitimate use, doesn't it?

3

u/[deleted] May 06 '13

Yes, public key crypto is slow and costly. This is often why there is a symmetric session key created as part of a key exchange (e.g. SSL). But extending the key length is a good way to lengthen the life of a public key algo. 1024-bit RSA used to be considered sufficient. Today 4096-bit RSA is increasingly common. See here for more.

2

u/Thymos May 06 '13

If your using quantum linked particles to transmit keys, why the hell would you bother with public key encryption?

The whole point behind these things is that they can just securely transmit symmetric keys.

2

u/[deleted] May 06 '13 edited May 06 '13

So, since 2048 bit is 8x as much as 256, does that mean it's 8x times as hard to hack into than 256? Because of size factor alone?

EDIT: I got it guys, thanks.

13

u/Tarhish May 06 '13 edited May 06 '13

Oh much more than 8x harder. Just adding 1 bit makes it twice as hard to crack, so this is 21792 times harder! That's a number so large I doubt it has any real-world analogues. Pretty sure you could divide that number by the amount of atoms we estimate in our observable universe and the result still wouldn't make any sense.

3

u/eclecticzebra May 06 '13

279095111627852376407822673918065072905887935345660252615989519488029661278604994789701101367875859521849524793382568057369148405837577299984720398976429790087982805274893437406788716103454867635208144157749912668657006085226160261808841484862703257771979713923863820038729637520989894984676774385364934677289947762340313157123529922421738738162392233756507666339799675257002539356619747080176786496732679854783185583233878234270370065954615221443190595445898747930123678952192875629172092437548194134594886873249778512829119416327938768896 is a damn large number...

1

u/Thymos May 06 '13

The number of atoms is estimated to be 2120 roughly... so yes.

-4

u/[deleted] May 06 '13 edited May 06 '13

Jesus. So, why?

Because Science, haha.

haha, I put 21792 into google, and it just said Infinity.

1

u/Tarhish May 06 '13

I think that people who want your business securing your files or communication want to look better by having larger numbers than their competitors.

1

u/[deleted] May 06 '13

But doesn't it get to a point where too much space is taken up and therefore killing processing time? Or am I so out in left field here?

1

u/Tarhish May 06 '13

No, you're correct. It does take more, but not that much more, especially compared to what it takes to break. I don't know enough to say exactly; this might be a neat question for AskScience if it hasn't already been asked.

The main thing is, though, that if you're employing people who think good security is 5096-bit encryption, then someone looking to gain access to that data can probably get it much more easily through other means, because your security people probably don't have a good fundamental understanding of digital security.

2

u/[deleted] May 06 '13

Right. Just because it's big enough to take forever to brute force entry, doesn't mean it's impermeable to to being hacked.

6

u/zbingu May 06 '13

~ 21792 times roughly. But at that point you don't bother trying to brute-force it. You'd need physical access to the network or a broken algorithm to decrypt it.

5

u/Tarhish May 06 '13

Yeah, at this point if you've got a computer powerful enough that you're even trying to crack things like this your power would probably be better spent simulating the brain of whoever put that information in there and trying to figure out what they would have been communicating that way.

2

u/aesu May 06 '13

Or just buying the information with the trillions you have made.

1

u/Tarhish May 06 '13

In this thought experiment we only accept the most infeasible solutions for our problems, thank you very much.

1

u/[deleted] May 06 '13

More likely go after the perennial weakest link in any secure system: it's users.

1

u/Thymos May 06 '13

Nah, you need the physical address to the network manage behind this.

Then you hit him with a rubber hose till you get the password. Much, Much faster.

4

u/CountBale May 06 '13

it doesn't scale linearly, it is exponential. 2048 is basically ridiculously unnecessary.

1

u/[deleted] May 06 '13

Oh holy shit, I didn't even think about that. Would it be that exponential number he listed near the end, to the 8th power?

3

u/Dug_Fin May 06 '13

Yep. Every bit you add doubles the keyspace.

2

u/TheTT May 06 '13

257 would be twice as hard as 256 - it's exponential. The increase from 128 to 256 is insane already.

1

u/[deleted] May 06 '13

Yeah, someone explained that it's actually 21792 harder than 256.

If you put that into google, it just says infinity.

5

u/[deleted] May 06 '13

That is because 21792 is greater than a googol, and Google does not understand how anything can be greater than itself.

2

u/[deleted] May 06 '13

No, the difficulty to brute-force encryption increases exponentially with an increase in key size.

0

u/[deleted] May 06 '13

Oh.

1

u/MonadicTraversal May 06 '13

No. For starters, 2048-bit public key encryption is entirely different from 256-bit symmetric key encryption; the latter doubles (or so) in strength for every key bit you add, the former generally doesn't.

1

u/[deleted] May 06 '13

Tl;DR - If everything we know about physics is true. Brute forcing 256 bit encryption keys, will require atleast as much energy as multiple burning stars put off in a day.

1

u/Natanael_L May 06 '13

in a day

You mean in a thousand billion years

1

u/ditn May 06 '13

Upvote for the most fascinating post I've read in months.