Useful Links

Recent Posts

Archive

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.

The Court of Appeals and Email Privacy

19 June 2007

The 6th Circuit Court of Appeals has issued an interesting opinion on email privacy. In doing so, it rules that a portion of the Stored Communications Act (SCA) violates the Fourth Amendment.

I'll let the lawyers on the net provide a detailed explanation. As I understand the opinion, though, the question is what process, and hence what standard of proof, is necessary for the government to obtain access to stored email. The SCA sets out three mechanisms: a search warrant, a subpoena, or a court order. Search warrants, which do not require notice to the subject, require a high standard: "probable cause". The other two mechanisms have a lower threshold — relevance to an ongoing criminal investigation — but in general subjects can challenge such orders. In this case, the government relied on a provision in the SCA that allowed the government to delay notice, and hence forestall challenges. The Court struck that down. It said that the government can't have it both ways: it can use the no-notice/ no-challenge search warrant, but with probable cause; or it can use the easier mechanisms, but only if the request can be challenged.

There are two other important points. First, the Court asserted that in general, users of commercial ISPs do have a legitimate expectation of privacy for their email. However, that expectation is dependent on the terms of service, which suggests that users really need to read those boring licenses carefully. Second, the Court distinguished between "technologies" that do some sorts of email scanning — anti-virus, anti-spam, etc. — and human examination of content. I suspect that that distinction will become increasingly fragile as technology improves.

The Court opinion is here.