Quantum Crypto Broken Again
The New Scientist reports [link to http://technology.newscientist.com/channel/tech/dn14866-laser-cracks-unbreakable-quantum-communications.html?feedId=online-news_rss20 no longer works] that researchers Vadim Makarov, Andrey Anisimov, and Sebastien Sauge have broken quantum key distribution.
The attack is described in their paper, “Can Eve control PerkinElmer actively-quenched single-photon detector?”
Spoiler Warning: Yes. She can.
The attack is brilliant in its elegance. They essentially jam the receiver. A bright pulse of laser light is sent and it blinds the receiver, which allows the eavesdropper, Eve, to decode the same photons that Alice and Bob are decoding, and thus get their key. The paper is only two pages, too, which is even better.
As you might expect, the Quantum Experts have said:
I don’t think it’s a serious flaw.
I’m incredulous. This is a serious flaw. It is a serious flaw because one of the main arguments about quantum cryptography is that because it is “physics” based as opposed to “computer” based, that it is more secure than software cryptography.
That argument is not without its merit because mathematical cryptography has about the same sort of intellectual rigor as physics did in Newton and Leibniz’s time.
However, no matter what sort of implied or actual rigor physics has, the comeback that the software people have is, “only if you build it right.” And that is a huge problem for any physics-based cryptography. You cannot prove you built it right. All you can do is show that you built it to within certain tolerances.
Those tolerances have known potential problems. For example, if your single-photon emitter emits two photons, that’s a big oops. There are also tolerances with unknown potential problems. This is one of those. No one thought you could do that before.
However, the promise of the physics-based approach is the tacit assumption that breaking the crypto means breaking the laws of physics. (Some supporters are less than tacit in this belief.) The fact that someone came up with a way to break quantum crypto cuts to the philosophical core of the discipline. It rocks the rational underpinnings as much as suggesting that NP<P would. (A core unsolved question in the math is whether NP>P or NP=P.)
This is big, and it’s big because it means that the “trust me, it’s physics” approach that quantum crypto expounds is broken. We can’t trust them because it’s physics. We have to trust that it’s built right and that there isn’t a cute physics trick that someone hasn’t found yet.
We should be hearing, “back to ze old drawink board” rather than “I don’t think it’s a serious flaw.” Moreover, the fact that they think this isn’t serious is an even more serious flaw. It means they don’t understand security.
Like most successful crypto-system attacks, this one is an attack against a particular implementation. It in no way calls into question the utility of quantum cryptography, but rather highlights that it doesn’t matter how good your algorithms/techniques are, if you don’t properly implement them in a secure system.
You’re right, and this is precisely my point. Let’s say you bought some quantum crypto gear. How do you know it works?
While software relies on some similar assumptions — you assume the math works, you assume the CPU works — it’s possible to come up with a reasonable assurance that the system is working correctly. More importantly, you have some assurance it will work well next week, and if it doesn’t there’s a plan to upgrade the device so that it does.
How do you test and verify quantum gear, and if you bought one last week with the Perkin Elmer detectors, how do you patch it?
The QC people have been saying, “oh, you don’t want that math stuff, you want physics.” They’ve been caught with a big oops again.
Most importantly, they aren’t saying oops.
You are the only person I know who makes quantum crypto a math vs. physics thing. One visited physics class and it is obvious that nobody trusts math as much as the physics themselves. The big advantage of quantum crypto is that it prevents/detects the recording itself. If quantum crypto breaks today your message yesterday is safe. This is not true for an AES-encrypted message (as someone may have recorded it yesterday). (And the mathematicians didn’t prove that the algorithms used for encrypting are secure, but only mathematicians really care about this.)
The other reason quantum crypto is getting much attention is that quantum computers are likely to break all algorithms in P (See Shor’s algorithm[1]).
[1] http://en.wikipedia.org/wiki/Shor%27s_algorithm