Quantum Cryptography

[Steven M. Bellovin]

I'm unhappy with the tone of the discussion thus far.  It's 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 of us on this list 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.  I've seen no technical commentary on this list on
the Warren D. Smith paper that was cited here about a week ago.

To me, QKD 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.  Gilmore has 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.


		--Steve Bellovin, http://www.cs.columbia.edu/~smb

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com