June 2007
The Court of Appeals and Email Privacy (19 June 2007)
Quantum Cryptography (29 June 2007)

Quantum Cryptography

29 June 2007

I’m unhappy with a lot of the complaints about quantum cryptography. They’ve gone far beyond critiquing current products and is instead attacking the very concept.

Today’s cryptography is largely based on certain assumptions. You can’t even call them axioms; they’re far too weak. Let’s consider RSA. We know that no one has proven it equivalent to factoring; even if that had been done, there is as far as I know no theoretically and useful computational complexity bound for factoring, especially for the average case. Similarly, we have no proofs that discrete log is inherently hard. But cryptographic proofs frequently work by showing that breaking some new construct is equivalent to solving one of these "believed to be hard" problems. We have a theoretically unbreakable system — one-time pads — but as most cryptographers know, they’re rarely usable.

Protocols are even worse. We can prove certain things about the message exchanges, and we have tools to help analyze protocols. But I have yet to see any such mechanism that can cope with attacks that mix protocol weaknesses with, say, number theory — think of Bleichenbacher’s Million Message Attack (which also involved how the protocol worked over the wire) or Simmons’ Common Modulus Attack.

It’s not wrong to want something better. Sure, we think our ciphers are secure. The Germans thought that of Enigma and the Geheimschreiber; the Japanese thought that of Purple. Is AES secure? NSA has said so publicly, but there have been technical papers challenging that. Consider, for example, Warren D. Smith’s new paper.

To me, QKD (Quantum Key Distribution) is indeed a very valid area for research. It’s a very different approach; ultimately, it may prove to be useful, at least in some circumstances.

Now — I’m not saying that anyone should buy today’s products. As has been pointed out ad infinitum, they rely on conventional cryptographic techniques for authentication. More seriously, they have been subject to serious friendly attacks. It’s only recently been mentioned prominently that the most devices don’t send a single photon per bit, and the proof of security relies on that. There is the limitation, possibly inherent, to a single link. (I wonder, though, what can be done in the future with switched optical networks.)

All that said, perhaps QKD will be useful some day. Unauthenticated? Diffie-Hellman is unauthenticated. Expensive? RSA is computationally expensive, and in fact wasn’t used very much for 10 years after its invention. Single link? We still use — and need — link-layer cryptography today. Provable security? Despite their limitations, one-time pads are and have been used in the real world. Sometimes, the operational and threat environments are right. It has been noted that cryptography is a matter of economics — and in some situations, perhaps the economics of QKD are right.

It’s very valid to criticize today’s products, and it’s almost obligatory to criticize over-hyped marketing. As I said, I don’t think today’s products are useful anywhere, and the comparisons vendors draw to conventional cryptography are at best misleading. But let’s not throw the baby out with the bathwater.