First Exploit On Quantum Cryptography Confirmed

Vadim Makarov writes "Physics World reports on researchers demonstrating a full eavesdropper on a quantum key distribution link. Unlike conventional exploits for security vulnerabilities that are often just a piece of software, spying on quantum cryptography required a box full of optics and mixed-signal electronics. Details are published in Nature Communications, and as a free preprint. The vulnerability was known before, but this is the first actual working exploit with secret-key recording confirmed. Patching this loophole is in progress. Disclosure: I am one of the researchers who worked on this."

Comments

I think I get it

[alfplayer]

O_____>-|o _____O

Re:I think I get it

[grcumb]

O_____>-|o _____O

Two things:

1. Your box is two-dimensional;
2. That doesn't look anything like a cat.

Dammit, more quantum stuff... Should I understand?

[Anonymous Coward]

Quantum computing, quantum cryptography, etc. are pretty common categories here on /. and I really don't know anything about either. Now, the question is... should I be alarmed for not being up to date here? Or is this stuff that really won't become relevant for 90% of software engineers outside academia for quite a long while? (I mostly develop web services and mobile applications but I still expect to work in this field for quite a few decades and if this is something that software engineers should understand - whether we actually work with the technologies or not - I guess I should look into it) If I should study the subjects more, can anyone recommend any good resources (those don't need to be free).

Re:Oh well.

[Anonymous Coward]

No wait! The line is both perfectly secure and being eavesdropped on, at the same time. It's not until we hear the message that it becomes one or the other.

Worth noting

[Anonymous Coward]

This is not an exploit of quantum cryptography.

It is an exploit in the implementation of the detectors.

They can't tell the difference between the quantum signal they are supposed to be detecting and a faked signal using classical light pulses. Man-in-the-middle attacks are fairly straightforward for classic light signals since they aren't changed when someone else intercepts them.

Re:Worth noting

[lgw]

This is not an exploit of quantum cryptography

It is an exploit in the implementation of the detectors

LDO. People seem in t rush to point this out on every /. crypto story. "This wasn't a problem with the math, but a problem with the implementation". Yes, that's how almost all attacks work. Attackers don't generally go after the strongest link in your cryptosystem, you know.

My silly RSA tokens (2 on them cluttering my keyring now!) are worthless not because the math was bad, but because the attackers found a better avenue of attack. That's not in any way comforting.

Re:Worth noting

[Anonymous Coward]

But the attack wasn't on quantum cryptography as the title claims.

It is just as silly to say that the attack was on quantum cryptography here as it would be to say an armored truck was robbed when someone pretending to be from the armored truck company convinced the bank to give them the money before the truck arrived.

Re:Worth noting

[phantomfive]

The US national debt: $129,000 per taxpayer

It's ok, rich people can pay for it. If we tax them enough.

Re:Worth noting

[Dwonis]

This is not an exploit of quantum cryptography.

Correct. It's an exploit of the snake oil currently being sold as "quantum cryptography".

Re:Worth noting

[lgw]

Ha, nice one. That's been studied in depth of course: there just aren't enough rich people to make that work (and people have a historically proven tendancy to either hide or defer income, or just be lazy, if you crank the marginal rates up too high). I believe the medicare liability exeeds the combined net worth of all American citizens, companies, and corporations - but we'll just fail to pay that out, as opposed to the $130k each we're stick owing.

Re:Worth noting

[phantomfive]

I believe the medicare liability exeeds the combined net worth of all American citizens, companies, and corporations

Really? Do you have a citation on that? It would be good to know. That would resolve the question of whether we are (potentially) solvent or not.

- but we'll just fail to pay that out, as opposed to the $130k each we're stick owing.

Yeah, for all the talk of defaulting on the national debt, it is forbidden by the constitution. Unless we can get a constitutional amendment, we'll be letting old people die in the streets before we default.

Re:A permanent fix?

[jjetson]

hmm your comment sounds fairly 'once and for all' itself.

Re:A permanent fix?

[yarnosh]

Don't be too certain about that.

Math

[doublebackslash]

Why do they spend all this money, all this effort on systems that cost more and offer less security than a large RSA or ECC public key system?

Especially when RSA and ECC are so very well studied and don't rely on what amounts to lab grade optics with unknown exploits, weaknesses, and requirement for over paid professionals?

Why? I don't see the benefit. It is slower, harder to use, more expensive, the list goes on!

16K bit RSA keys are slow to generate but offer 256 bits of private key material equivalent security. Much less than that is needed for ECC. This all seems like a waste. It isn't even basic research anymore (which I endorse!) this is just some sort of dick measuring contest.

Re:Math

[TheTurtlesMoves]

This is really not true at all. Not only do they need at least a 1024 qbit computer at least, it still needs a massive amount of operations (both classical logic and quantum operations). Current optimistic estimates for a quantum computer still put it in the slower than classical or still so slow that it doesn't matter. And all you need to do is add a single bit to your key, since you cannot emulate a larger register than what you have in quantum computing.

I have a lot of friends in the field. Not one of them believes that quantum computing will ever be a viable way of cracking ECC and RSA. There is a very small minority who thinks it can. But most won't say it can't work too loudly lest their funding agency's get wind of it.

Re:Math

[gweihir]

There is no sane reason. RSA may be eventually broken, as there is still no security proof for it. But ElGamal has a strong mathematical security proof and is unlikely to ever be broken. ECC serves to reduce key-sizes and, afaik, has at least weaker security proofs. The important thing is however that they do scale, i.e. longer key gives better security. No such property is present in Quantum signaling. (No, it is not crypto.)

Then there is a second dirty secret: Quantum signaling is only for key distribution. The actual communication is done with conventional block ciphers like AES. This completely invalidates the concept, even if you assume Quantum signaling to be eavesdropper-proof, because RSA/ElGamal is likely much more secure (with reasonable key-lenghts) than AES. So this quantum signaling stuff is useless in practice, expensive, hard to implement, unreliable, unproven and incompatible with other networks.

The only reason I can see is a desperate desire to be "modern" with some management types on the customer side. And of course, the all time favorite on the sellers side: Make money from selling useless stuff to suckers.

Re:Math

[gweihir]

They are not. Even though this type of BS can be read in the press quite often. Unless you assume we get quantum computers than can hold arbitrarily long entangled state. If we do not have that, just make the RSA key length one single bit longer than the longest entangled state that computations can be done on and the quantum computer is useless. (Dirty secret of quantum computing: You cannot combine calculations on large elements from computations on smaller elements.)

Ad for symmetrical ciphers, brute-forcing with quantum computers requires 2^(n/2) tries instead of 2^n tries. You still have to do each try and you have to model the whole cipher, which requires, e.g. for AES-256 in a known-plaintext-attack (which is the easiest one) to hold 2x128 bits for known plaintext and ciphertext, 256 bit for the key. That is already 512 qbits you need. Then you need to represent AES internal state and do computation. This easily adds another 512 qbits of state. Then you need to do something like 8000 x 2^128 quantum computations, retaining entanglement. As far as I can tell, each of this computation steps will be vastly slower than a conventional step as you need to manipulate the entangled set of qbits from the outside. And you cannot parallelize! Throwing two quantum computers at the same problem takes exactly the same time as when using only one.

We are currently where? 5 entangled bits when actual computations are done on them? After 2 decades of research. This leads me to believe that if they will ever work at all, quantum computers will not be able to crack current crypto for a very, very long time.

Re:Math

[gweihir]

They do not have a quantum computer. They have something expensive with a label that says "quantum computer", but they really were ripped off.

Re:Math

[mysidia]

Then there is a second dirty secret: Quantum signaling is only for key distribution. The actual communication is done with conventional block ciphers like AES. This completely invalidates the concept, even if you assume Quantum signaling to be eavesdropper-proof, because RSA/ElGamal is likely much more secure

That's insane... what they should do is use public key crypto secured transmission of private keys.

And encrypt the data payload in a CBC mode, with random shared quantum inputs used to manipulate the block chaining (e.g. by XORing each block against a random hash value generated using shared quantum channel after XORing with the previous ciphertext block).

They should knowledge of the symmetric private key alone is not sufficient to eavesdrop on the communication channel and that compromise of the quantum channel alone is not sufficient to compromise the symmetric encrypted channel.

Re:Math

[WaffleMonster]

It might have to do with the fact that if/when someone gets a quantum computer RSA and ECC are effectively hosed. At that point, without a viable replacement, the world economy as we know it would disappear.

If we ever invent a real QC capable of running shors algorithm to break useful codes before our sun turns into a white dwarf the worlds economy is in for one hell of a roller coaster ride at warp 9 into the future.

My money is on it never being possible due to the decoherence tax. It stinks of something for nothing. I hope I'm wrong.

Re:Math

[BitZtream]

The fact that they had to invent a name for a bit on quantum computers is where I knew to jump off the train.

Its a bit, there is no need to call it a qbit, it represents the same thing, the smallest amount of information we use in computers. It is either 1 or 0.

The fact that it gets called a qbit instantly lets anyone with a clue know that this is a marketing gimmick and there is no useful value to quantum computing at this time. You don't have to call useful things by new entirely different wanna be trendy names in order for them to be useful, the fact that they've done so means their trying to convince normal people of its value by making it sound trendy than actually showing a useful value to it.

There isn't a current quantum computing implementation that has any practical value beyond research of quantum computing. The fact of the matter is, right this instant, anything we can do with a quantum computer we can do faster, cheaper, smaller, with less resources and in less time to build with standard hardware.

Anyone who buys into quantum computing at this point is an ignorant idiot at best, it gets worse from there, and yes, I realize a major defense contractor just bought one, and my point still standards considering who within that organization bought the device.

Re:Math

[BitZtream]

, because RSA/ElGamal is likely much more secure (with reasonable key-lenghts) than AES.

Show me someplace that uses RSA for encryption of raw data.

What you have in the real world EVERYWHERE is that RSA is used for key exchange/session key generation/identity verification ... and AES is used to encrypt the payload data.

Why? asymmetric encryption is extremely processor intensive, too much so to do on any practical scale.

So this quantum stuff is not useless for the reasons you state (although there are actual reasons why its useless) because the reasons you state are how pretty much every cryptosystem on the planet using asymmetric keys works already. What you describe as how quantum crypto works is pretty much how SSL works, except your using some sort of quantum bullshit in place of RSA for session identity verification and key exchange.

before you start telling people how cryptography works, you might actually want to learn how cryptography works.

Re:Math

[BitZtream]

Using what you describe, you have produced random unusable gibberish on the output.

You can't throw randomness into cryptography, contrary to common belief. Everything has to be known or calculatable in order for the original data to be extracted from the encryption.

Cryptography is VERY complex math, nothing more at this point, with the general idea intended to be to make it take a minimum amount of time to decrypt the data, but making that time long enough to prevent brute forcing from being viable and not allowing for any shortcuts in the math that would narrow down the possibilities for the brute forcer to try.

What you describe just does more of the same thing we do now, you simply don't understand how what your describing actually works. At best, you've just slowed the system down because you've required more calculations. At worst, you've added a why to sidestep portions of the process and possibly find ways to shorten the brute force time of the system.

Adding more to an encryption system is generally not regarded as the solution to the problem, 11 times out of 10, you'll add more bugs that can be exploited to weaken your security than you added additional security anyway. Its a rather common thing to have happen in the cryptography world.

Re:Math

[mysidia]

Using what you describe, you have produced random unusable gibberish on the output.

Not really. If you generate some random data and transmit it over the quantum channel, both endpoints to the communication have the shared quantum secret, with an agreed upon hash, and agreed upon method of using the data and proper synchronization of the two data streams, they will both come up with the same thing, and the recipient will be able to inverse a simple XOR.

The whole point of quantum crypto is it can't be brute forced. But using standard crypto over non-quantum channel of course can be brute forced, when it is standard and quantum channel is used only for distributing the initial keys.

The quantum channel is basically wasted.... instead of using the quantum properties to secure the communication, it's just a fancy key rollover system.

Re:Math

[Urkki]

Not ... will ever be ...

Historically, statements like that tend to be false.

Anyway, all it takes is qbit count to hit the "~doubling every ~two years" phase typical of many technologies, and we'll be in kiloqbit range in no time (well, to decades, but anyway). Of course it could be that in our universe, this is impossible, but if it's merely very difficult, then there tend to be workarounds found for practical problems, after technlogy becomes commercially profitable and regular R&D cycle gets properly started.

Re:Math

[TheTurtlesMoves]

Only thing is that complexity of a quantum computer is *not* linear with qbits, its quadratic or far worse (exponential). We are currently only seeing linear growth of qbits, and even that is a stretch since the number of logic operations is very very limited.

Of course there could be a breakthrough. But even then things like the factoring of numbers still needs a massive amount of qbit operations in addition to classical operations. On top of all that we have only a handful of useful algorithms on these things.

At any rate if experts in the field are so pessimistic, then i think its a good bet. After all these are the experts.

Re:Math

[doublebackslash]

Read up on Quantum Encryption. It is really REALLY cool.

In case you've tried and hit one of the many hand-waving walls here is the brief because I'm not the type to just be snide and say RTFM:

So you have a sender and a pair of receivers. You (sender) have one of the receivers. You send an entangled pair of photons down the lines. Here is trick one: those two photons will have the same polarization but you don't know what it is till you measure it.

Now polarization isn't just one direction, photons can be polarized in many directions. What you and the other side do is pick a bias for your receivers independently and randomly, "+" or "x". Now that you have both seen this unreproducible event you talk about it, publicly. The only requirement for this "conversation" is that you both can hear each other. MITM attacks, etc do not matter. Those will show up as errors and the whole thing discarded.

Here is what you talk about: at first you talk about which bias you used. + or x. Where you agree there is a good chance you saw the same thing and you use that bit. Where you disagree you discard it and try again. One you have a good number of bits you talk about their parity (XOR is parity). The algorithm works by saying something like, "The parity I have for that group is 1" and then they either agree or disagree. Should you agree that means that there is a chance you have the same group. Discard one bit from it. Since that bit was random and you only transmitted the parity you have leaked zero information. If your parity did not agree (really even if it did) you split the shortened group in half and do it again. (this is trick two). Once you have found where all the errors are and discarded those pieces and have verified enough of the parities (and discarded one bit each time remember!) you have "amplified" your privacy. Using this technique you can amplify your privacy to arbitrary levels so that an interloper can have an arbitrarily small chance of successfully faked a key (a VANISHINGLY small chance in practice. 2**-256 is a commonly quoted value). Now you've got a shared *random* secret (As bond would say if he was an rng: Random. Quantum random. It is that good.).

If anyone had been fiddling with your signal (either the discussion or the quantum channel) you'd have spotted them making too many errors and gave up on the communication.

Now, as you said, you COULD xor that key with the data and send that, safe in the knowledge that it is protected by the only 100% secure encryption system: a one time pad. You've got a 1mbps channel using the very latest and greatest technology. Hope you didn't have big plans for it.

That might be what you need! I'll bet that it isn't. Most data only needs to be secure for a tiny amount of time. Seconds or hours. Days perhaps. That is the data that falls comfortably into the realm of standard cryptography. Brute force it if you like. Useless now anyway.

That is why I contend that unless you have a real need for OTP security that a robust RSA based system is good enough. Change your keys, verify often, have good physical security, etc. rest safe in the knowledge that your data is protected by decades of, thus far, bulletproof math.

On the other hand, if you DO need to have real OTP security don't you dare rest all your hopes and dreams on the physical realizations of quantum encryption. If your data is that important then you could (more cheaply, no less!) have stores of one time pads sitting around safely using, for example, Shamir's secret sharing algorithm. It is provably secure and not just from brute force attacks. It requires that a certain number of pieces are present to reconstruct the original data. There is no loophole. Without the last piece you gain nothing. It could be anything. It is also better than XOR (which requires that ALL pieces are present) in that it has a threshold number of pieces that need to be present so that the keepers of the keys need not all be simultaneously present (guards with rotating schedules, as an e

Disclosure?

[dk90406]

"Disclosure: I am one of the researchers who worked on this."
Disclosure is an interesting word here. I would have used the word "brag" - and I think you are fully entitled to brag about that feat.

Re:Disclosure?

[FrootLoops]

I think "disclosure" is appropriate. His name appears in several of the articles, and it would be awkward had he not mentioned it in the summary.

Re:Disclosure?

[Vadim Makarov]

Agreed. This article will advance his career, so getting it on Slashdot leads, indirectly, to financial benefit for him. That said, I agree with the GP that it's deserved - and it really is news for nerds.

I'll bite this troll. I typed this submission because

1. I think what we do is cool, and is interesting to Slashdot readers (I read Slashdot daily myself).
2. I can formulate what we have done better and include most relevant links, comparing a random submitter who has just read a news story.
3. Yes! I am 37 and I do not nave a tenure yet! Every bit helps :). Unfortunately, really, I do not think anybody is going into science for money.

Re:Disclosure?

[BitZtream]

Its okay dude, what he was saying is that even if it was a slashvertisment, its okay because this one ACTUALLY BELONGS on slashdot as it truely is news for nerds, regardless of the slavertising part.

This sort of article being submitted to slashdot in an attempt to gain attention for the subject of the article is perfectly acceptable because this is the kind of stuff we WANT to see.

Anyone bitching about slashvertisments in this cause is just being a douche, and the guy you were replying too is basically saying that.

Keep submitting articles like this, slashvertisement or not, this is what want to see ...

What we don't want to see is the article spread out over 20 pages with a paragraph on each page, surrounded by literally 25-30 flash ads that we have to page through.

What we don't want is some random Apple app advertisment, or some go spaming his blog where he makes up some 'top ten' list of 'important events in computing' and you can tell by the list this guy has been using computers all of 15 minutes.

If you don't link to anything that considers itself a 'blog' thats a good start. If you don't link to any 'computer magazine' webiste, then you're doing good.

What not to do:
Link to anything OTHER THAN THE ORIGINAL STORY. No linking to someones blog which links to the original story. No linking to some random retards (yours included) comments about the subject matter ... which links to the subject matter.

I could go on, but the point is, the person your replying too isn't bitching about your post, he's defending it.

Impact on Bitcoin?

[turkeyfeathers]

Does this have any impact on the security of my bitcoin wallet? If not, who cares.

Re:Impact on Bitcoin?

[GameboyRMH]

That's not all there is to care about! What about the iPad supply!?

Re:Oh well.

[FrootLoops]

This is an attack on implementation details, not the underlying physics of quantum mechanics. The title could have been a little better. This is (apparently; my only source is the submitter, as he's also the source in the article) the first working exploit of a quantum cryptography system that was able to steal the key without being detected.

Re:Oh well.

[Anonymous Coward]

The problem is there are always implementation details.
The basic design of QC says:
1) Assume that we can build these perfect emitters and detectors
2) Now we've got something that's perfectly secure

It's like saying:
1) Assume I can create an invincible dragon
2) Lets use it to distribute crypto keys

This is not to say s that QC is useless, but rather that it's capabilities are severely overhyped.

To put it another way, these "implementation details" are all part of the "underlying physics". Every piece of physics that gets from a human usable bit on one end to a human usable bit on the other end is "underlying physics".

You may as well claim to have designed the starship enterprise and the call the warp drive "implementation details".
What color to paint the walls... that's an implementation detail. The basic technology to make something work... that's an integral part of the problem.

So much for "unbreakable"

[gweihir]

As with most recent vulnerabilities in Cryptography (no, the quantum stuff is not crypto, it is signaling with special physical properties), the attack goes against the implementation. This did not stop several companies and a lot of fanbois to claim "unbreakability". I hope you have learned something.

Re:So much for "unbreakable"

[93 Escort Wagon]

As with most recent vulnerabilities in Cryptography (no, the quantum stuff is not crypto, it is signaling with special physical properties), the attack goes against the implementation. This did not stop several companies and a lot of fanbois to claim "unbreakability". I hope you have learned something.

I seriously doubt it. In my experience, people's memories are selective - anyone who's made that claim (and yes, I remember reading several such statements) likely will deny it now.

Re:So much for "unbreakable"

[FrootLoops]

Unbreakable in principle and unbreakable in reality are two very different claims. One is reasonable, assuming some principles of theoretical physics, while the other is silly to mildly informed people.

Re:So much for "unbreakable"

[gweihir]

Also principles of theoretical physics are really hypotheses. They tend to change every few decades and often the old "principles" look quite silly then.

Re:So much for "unbreakable"

[token0]

I wonder what principle of quantum information ever changed? Or can you give any example of a few-decades-old principle of theoretical physics that looks silly today? Theories embrace new details, the underlying interpretation and math can totally change, but in 'normal' conditions (low gravity, low speeds or macroscopic scales, depending on the theory), they converge to classical principles. So all you need to assume in quantum cryptosystems is its pretty simple old principles and "Eve doesn't have a super mega flexible neutron star constellation with her".

Re:So much for "unbreakable"

[gweihir]

In terms of physical theory, Quantum Theory is not old. Nor is is well-proven, as there are a few new discoveries every year at the moment. So far, it mostly pans out, but there are no guarantees. Think mechanics. For a long time it was the perfect theory. Then some people started to measure more precisely than ever before, and suddenly it turned out to be a rough approximation. So, for example "Doc" E.E. Smiths idea of interstellar travel looks quite silly today. There is absolutely no reason Quantum theory is better than Classical Mechanics. In fact, there is quite a bit of evidence that it is not. For one thing it does not mesh with relativity. For another, it is completely non-intuitive, which means attacks on it can be equally non-intuitive. The attacks on mechanics were simple: Heavier, faster. Rather obvious. And all physical theories have broken so far when people took a long, hard, practical look. There is absolutely no reason to believe Quantum Theory is better. It is not the GUT, after all, that one is by now clear.

You also overlook that any Quantum Signaling (there really is not crypto in there, not even conceptually) System needs a practical implementation. Cryptosystems are typically not limited by that, the main practical limits are computational effort and randomness generation. Apart from that the implementation typically mirrors the mathematics 1:1, which is a main characteristic of digital systems. However, Quantum Signaling is very much analog. What may be a detail to theory, can mean unimplementability or large errors in practice. For example, if it proves practically impossible to make a reliable single photon detector, some some attacks will always work. And this does not even need any problem in Quantum Theory.

So, in summary, it is not a good idea to rely on physical theory, which has the status of Hypotheses when it comes to practical implementations, when we have actual mathematical theory (which is still hard fact when implemented digitally) that already solves the problem well. And no, quantum computers will not kill conventional encryption. They will make breaking a bit easier, so keys need to be a bit longer, but that is essentially it. You cannot break 2048 bit RSA with a 2047 bit Quantum computer. You will always need a Quantum Computer that you can fit the whole problem into in one go. You just need to make the problem 1 bit larger than the Quantum Computer's maximum entangled state and it becomes completely useless. That can be done with all cryptographic primitives. And if you look at the fact that they can do Quantum Computing on 5 entangled bits today after 20 years of research, this seems to be a problem that gets exponentially more difficult in the number of qbits. If you look at what entanglement means, that fits intuition really well. On the other hand, classical computers can divide problems into subproblems and combine partial solutions. Also, putting in larger problems is basically no more than quadratically more effort, mostly from communication overhead.

Re:So much for "unbreakable"

[swillden]

So, in summary, it is not a good idea to rely on physical theory, which has the status of Hypotheses when it comes to practical implementations, when we have actual mathematical theory (which is still hard fact when implemented digitally) that already solves the problem well.

Except that we don't really have "actual mathematical theory", either. No one currently knows how to factor products of large primes efficiently, but it has not been proven that integer factorization is NP-complete, nor are we entirely sure what NP-completeness means (c.f. P=NP). Worse, we haven't even proven that factorization is the only way to defeat RSA -- it's possible there's another way. Finally, RSA and other asymmetric ciphers also suffer from practical implementation issues. RSA in particular is very vulnerable to side-channel attacks like power analysis and thermal analysis. There are many other known weaknesses that we know how to work around (e.g. chosen ciphtertext attacks, which are defeated by using optimal asymmetric encryption padding -- though the original version of OAEP has proven to have some weaknesses, addressed by newer versions), and there are undoubtedly many weaknesses that we don't yet even know about.

I'm not knocking RSA, DSA, El-Gamal, ECC, etc., they are very valuable tools. But to say that this shows they are inherently better than quantum crypto is nonsense. Security is just plain hard. The ONLY cipher that we have real, solid mathematically-provable reasons to trust is the venerable one-time pad, and even THAT has proved in practice to be less than perfectly secure due to implementation errors (c.f. Venona).

Re:So much for "unbreakable"

[gweihir]

For RSA you are right. For ElGamal your information is outdated, as a solid lower bound proof exists. There are also proofs for other DLog based crypto. It is just a bit harder to implement and a bit slower. Also, I guess, RSA had more commercial backing with the (IMO bogus) patent on it.

Quantum Signaling has neither and is eminently impractical in addition. As to plain hard, when we at least have mathematics, that is something solid. For the Quantum stuff we do not have complete observations, we have implementations that must be imperfect (as they are analog) and the theory could still turn out to be wishful thinking.

Re:So much for "unbreakable"

[token0]

ElGamal's proof assumes the Diffie–Hellman assumptions, which are quite strong. Actually every modern asymmetric key encryption algorithm's security would imply the existence of one-way functions, which in turn would imply P!=NP - as far as my outdated information goes, we don't have a proof of that yet. But even if I'd trust P!=NP, there's a lot of other ways the strongers assumptions could fail, e.g. maybe your particular key is one of those 10% that's easy to revert.

I'm not sure why you say "there's no crypto" and call it quantum signaling - BB84 is obviously an encryption protocol. Maybe you were thinking about entangled states communication, which also is provably secure (assuming basic quantum information principles and some things about the physical detectors), but as a protocol is simple and relies almost solely on sending entangled pairs.

A 1024 qbit quantum computer _will_ give you an exponential advantage in RSA-breaking (compared to classical algorithms we know) even if the key is longer - the algorithm might get more complicated, but there obviously are things a QC can do (in a reasonable time) while a classical can't. Regardless of that - if your encryption protocol assumes nobody will have 5000 qbit quantum computer in fifty years, then it has a weakness. When Enigmas were being used, do you think anyone thought the Bombes - massive electromechanical devices capable of doing a massive analytical job - were possible? One more thing - a 5000 qbit computer is most probably easy to do, once you know how to do a 1024 one - it's not exponential in difficulty, the only problem is to find a solution to decoherence that will scale, that doesn't have an inherent limitation.

The BB84 quantum encryption protocol (invented in 1984) is already provably secure, assuming basic quantum information principles and some detector reliability (we don't assume they're perfect, BB84 takes into account all kinds of noises on detectors and emitters; noises are always assumed to be caused by a breaking attempt, we take into account the possibility of the enemy having parts more perfect than anything we could produce). The "basic QI principles" is basically the non-cloning principle (a bit more precisely - the principle that all observations are describable by unitary positive matrices) - which is something I'd trust a lot more than even P!=NP. Saying it could be wishful thinking is like saying Newton's motion is wishful thinking. A mechanical lock still works just as advertised, quantum mechanics or general relativity won't help you break it. Maybe particles do clone when you go outside QM, e.g. the universe's growth may create particles, but making that an exploit would require you to control the universe's growth :)
Those quantum exploits you see are caused by attempts at making the protocols more practical - of course there's a ton of problems with the theory going into practice. But saying "quantum information theory is shaky" is more crazy than saying "P=NP", and way more crazy than saying "there might be a fast algo for the discrete logarithm for certain primes we don't know of yet".

Re:So much for "unbreakable"

[gweihir]

P!=NP is convenient, but not needed for one-way functions. It is enough that you have a scalable higher effort in one direction, p!=NP merely gives you a set of easy ways to get that.

Saying "quantum information theory is shaky" is not crazy at all. History shows that any physical theory was disproven, except the at that time current one. There is absolutely no reason (except arrogance) to assume we not have it right.

As to why this is not encryption: From Wikipedia: "encryption is the process of transforming information (referred to as plaintext) using an algorithm (called cipher) to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key". But this is not what Quantum Signaling does at all. What it does is make eavesdropping obvious. In that sense it may be a tamper-resistant seal on steroids, but it is not encryption at all.

Re:So much for "unbreakable"

[gweihir]

Wups, should be: "... we now have it right."

Re:So much for "unbreakable"

[token0]

Which part of "The existence of one-way functions would imply P!=NP." don't you understand? On the other hand P!=NP doesn't imply the existence of one-way functions (one-way is a _stronger_ assumption), so no, even P!=NP doesn't give you easy encryption (as far as our knowledge goes today). And ElGamal's security is based on an _even stronger_ assumption that the discrete logarithm is a one-way function - there's no simple reason to believe that it's true.

What physical theory was disproven? The principles of Quantum Information Theory never changed. There are extensions taking into account relativity, but they're irrelevant, just like Newton's laws of motion are still valid for all intents and purposes of a mechanical lock. Even Quantum Mechanics, of which QI is a very simple subset, are settled and still agree with modern theories under low gravity and such. The fact that new theories are invented with "Quantum" in their name doesn't mean that QM changed. You could just as well say that ElGamal is shaky, because maybe there's a law of physics that makes all ciphertexts magically appear plain on my screen.

From Wikipedia: "BB84 is the first quantum cryptography protocol." It may not be encryption, because you don't get a classical ciphertext, but it definitely serves the purpose of exchanging information while assuring it's unreadability to third parties. Exchanging secrets. Cryptography. Please.

Re:Oh well.

[FrootLoops]

You're exaggerating your point (eg. by talking about dragons and warp drive). One of the articles suggests you might mitigate this attack with a relatively simple extra verification step. This attack depends explicitly upon "blinding" a detector with light "above the intensity threshold" (certainly this is oversimplified). That's an attack on implementation details. Certainly I didn't mean to say that building a QC system is all "implementation details"; that would just be stupid. This one point that was attacked is an implementation detail.

Re:Dammit, more quantum stuff... Should I understa

[Intrepid imaginaut]

should I be alarmed for not being up to date here?

You both should and shouldn't be alarmed.

Re:Oh well.

[Anonymous Coward]

I think I made the point well.... since neither perfect emitters/detectors, dragons or warp drives exist.
Since these items don't exist, then the problem needs be be examined in the light of what actually does exist.

The fact that the detector has an intensity threshold isn't an implementation detail, it a part of the underlying physics. Point me to a detector that doesn't have one.
You can't just replace the detector with a different one that doesn't have this problem, you have to make the QC system more complicated.

They talk about switching in a different source to verify the correct function of the receiver, but how do you do this on the fly and not miss messages?
You need to synchronize the two systems. How do you do this?
Via an unhackable secure channel... wait isn't that what the QC link was supposed to be in the first place?

I'm not saying that there isn't a solution to this problem. but it needs to be pointed out that fixing these "implementation details" appears to mean changing the design of the protocol. Something that forces a protocol redesign is a key part of the system.

People are used to regular crypto, where the task of computing the result of a basic mathematic function can be safely left to hand-waving. You can do RSA with a computer, or longhand on a piece of paper. The properties of the computer aren't an assumed part of the way the system works. With QC, it is assumed that pieces of hardware behave in very specific ideal ways. You can't buy parts that work like that, you have to use real parts. Therefore the system design, and explanations of how a real system works need to account for that.

Re:Oh well.

[FrootLoops]

I wish I could mod this paragraph up:

People are used to regular crypto, where the task of computing the result of a basic mathematic function can be safely left to hand-waving. You can do RSA with a computer, or longhand on a piece of paper. The properties of the computer aren't an assumed part of the way the system works. With QC, it is assumed that pieces of hardware behave in very specific ideal ways. You can't buy parts that work like that, you have to use real parts. Therefore the system design, and explanations of how a real system works need to account for that.

I still think (from my fuzzy understanding of this attack) that it uses a specific implementation detail that depends upon the system used, and might be relatively easy to patch. Maybe they can use different wavelengths of photons, one for a test and one not--I don't have the expertise to say how much of a redesign is necessary. The article makes it sound like it's not a huge deal, and the Toshiba guys say in one of the other articles that their system isn't susceptible to these attacks when properly operated.

Re:Oh well.

[Vadim Makarov]

I still think (from my fuzzy understanding of this attack) that it uses a specific implementation detail that depends upon the system used, and might be relatively easy to patch. Maybe they can use different wavelengths of photons, one for a test and one not--I don't have the expertise to say how much of a redesign is necessary. The article makes it sound like it's not a huge deal, and the Toshiba guys say in one of the other articles that their system isn't susceptible to these attacks when properly operated.

Currently the problem is quite general, because most quantum cryptosystems today use detectors of the vulnerable type. We think it is patchable, just not by the approach the Toshiba group practices, but patchable. (We dislike Toshiba's approach for not being general and thorough, but more of a quick band-aid.) During the past 20 years there were a couple problems of similar magnitude in quantum crypto, and they were solved. Note that similar problems periodically show in implementations of classical crypto.

The future of quantum crypto will now be decided, from one side, by the market, and from another side, by publicly disclosed mathematical developments on various classical ciphers (which can be cracked overnight, but can also be proven more secure... I'm not a mathematician so I won't venture a guess for the odds of either). In quantum cryptography there is at least one well-engineered commercial system, several advanced commercial prototypes (Toshiba has one), and the hacking efforts are going to eliminate all easy loopholes in a reasonable time. It is also important how well quantum cryptography can be meshed into networks with many nodes and links. There have been several demonstrations of quantum crypto networks, the latest in Japan last year.

The current commercial systems (like ID Quantique's Cerberis) use quantum cryptography as an extra security layer on top of classical crypto. To get to the master key used to encrypt the data, one needs to crack both quantum key distribution and classical key distribution at the same tme. We temporarily compromised the quantum layer in this work, but in a commercial installation the data security would hang on the classical crypto, until the quantum layer is patched. Of course the security of the symmetric ciphers (normally AES with frequent key changes) used for high-speed data encryption is another question, but I think there is also an option to establish a low-bandwidth highly-secure channel encrypted by one-time-pad. The whole reason AES is offered with quantum crypto is that the performance of the classical crypto has spoiled everybody, and the users do not want to separate communication into high-security and low-security categories. They just want to encrypt the whole 10 Gbps link, so this is the default option.

Spinning

[glorybe]

Is Heisenberg spinning in his grave? I do have serious doubts that governments will ever allow fool proof encryption to be in the hands of the public.

Re: Spinning

[maxume]

Nothing is fool proof, fools are too persistent and too clever.

On the other hand the idea that Truecrypt is compromised is quite a claim.

Re:Oh well.

[FrootLoops]

Thank you for the informative reply!

Eavesdroppers-Only Channels

[Doc Ruby]

When the eavesdropping is "in channel", doesn't require material access to the transmitting medium, the eavesdropping could be the fastest, preferred, mode of signaling on the link. Spinning the quantum wheel of "how associated" is the linked topology is going to precede what state info gets distributed most widely, therefore presenting the highest possibility of sync to another signal in the system - dominating it. So modulating the the wheel's state is going to get ahead, leaving everyone on the signal angling to write to it, not just read it. Picking up the traces in the reverb that come from the eavesdropper will make the eave less secret.

Indeed, if I'm tuning into some quantum state to exchange with it, the leading edge that makes its modulation of the remote state the first is the one I'm most aiming to use.

Can the benefits of quantum crypto be proved?

[WaffleMonster]

Lets assume for a second the quantum hardware itself works perfectly as advertised and cannot be compromised.

You still need classic (Such as a symmetric key) information to prove alice and bob are talking to each other rather than to malices quantum MITM proxy server.

Has anyone proved a perfect quantum OTP source improves actual security vs use of a zero knowledge algorithm to establish the same? Even if such an algorithm does not yet exist... Is it possible to construct one? Has it been shown this is not possible?

Re:Can the benefits of quantum crypto be proved?

[Vadim Makarov]

Zero-knowledge authentication is impossible by definition. If you know nothing secret about someone, you can never verify his identity.

A small pre-shared key is used for initial authentication, in all classical and quantum crypto alike, to preclude a man-in-the-middle (MITM) attack. In the classical public-key infrastructure (PKI), this authentication key comes from the certicficate authority with, e.g., your copy of the web browser. If it is spoofed at the distribution step, MITM attack becomes possible.

In quantum crypto, the initial key is small, because once the quantum-generated key begins to grow, its small fraction is used for further authentication keys.

Re:Can the benefits of quantum crypto be proved?

[WaffleMonster]

Zero-knowledge authentication is impossible by definition. If you know nothing secret about someone, you can never verify his identity

See http://en.wikipedia.org/wiki/Zero-knowledge_proof

In quantum crypto, the initial key is small, because once the quantum-generated key begins to grow, its small fraction is used for further authentication keys

Can it be proven a perfectly random, private yet untrusted OTP source would necessarily be better than any possible encryption algorithm given the same initial trust?

Understand it for fun, but not for use just yet.

[Richard Kirk]

The original patent on quantum cryptography was for a banknote with trapped photons. These could only be read once, so you had to know the polarization axis of the of the photons to read their state. This was a wonderfully batty idea, and a useful explanation of what is known and what isn't known about a quantum state.

However, when you go into actual implementations of quantum communications, you find the hacking techniques are much the same. Here, they are trying to send out a single photon. If a real line is lossy, the system must have some sort of handshaking to resend bad bits. If you hack into their cable, and carefully mess up a few photons, you can tease this system into resending some parts of the signal, or sending a stronger signal with more than one photon; and then the system is no longer secure because more than one person can get a copy of it. It's the quantum physics equivalent of attaching your crocodile clips to the telephone wires without the user hearing the clicks.

My guess is you can get the same level of security from ordinary non-quantum techniques. If you are going to avoid a 'man in the middle' attack, you should meet the person at the other end. Suppose, when you meet, you exchange thumb drives with random data. You can then 'OR' your message with this data, using each bit once only to reduce it to random-looking bits; and the person at the other end can 'OR' it again to get it back again. An extra precaution would be to pad each message to a fixed length, so you don't give away the number of bits in your message. One time pad cryptography makes the communication link secure, but either end is potentially unsafe; which is pretty much what you would have with a perfect quantum encryption scheme.

Re:Oh well.

[owlstead]

Of course the security of the symmetric ciphers (normally AES with frequent key changes) used for high-speed data encryption is another question

Especially since AES can be quite vulnerable to side channel attacks, maybe even more so if implemented in hardware. AES should be used for less blocks than triple DES. Then again, it might be hard to come by another hardware accellerated cipher that has been researched as extensively - I suppose triple DES is out of the question. Maybe one of the other AES candidates or even Threefish could be used instead (or on top of AES, we're talking highly secure systems here).

Re:Trust is not an easy thing.

[BitZtream]

I've worked on anonymous trusted networks.

No you haven't. Anonymous and trusted are mutually exclusive, and thats why you keep failing.

Seems fairly clear you don't even understand how humans naturally build trust in the real world. Your failure to understand that pretty much precludes you from augmenting it in any working way.

Re:Oh well.

[CrypticKev]

If the line sounds a bit scratchy, it's just the cat wanting to be let out.