Hold the Photons!

  • Bruce Schneier
  • Wired
  • December 15, 2005

How would you feel if you invested millions of dollars in quantum cryptography, and then learned that you could do the same thing with a few 25-cent Radio Shack components?

I’m exaggerating a little here, but if a new idea out of Texas A&M University turns out to be secure, we’ve come close.

Earlier this month, Laszlo Kish proposed securing a communications link, like a phone or computer line, with a pair of resistors. By adding electronic noise, or using the natural thermal noise of the resistors—called “Johnson noise”—Kish can prevent eavesdroppers from listening in.

In the blue-sky field of quantum cryptography, the strange physics of the subatomic world are harnessed to create a secure, unbreakable communications channel between two points. Kish’s research is intriguing, in part, because it uses the simpler properties of classic physics—the stuff you learned in high school—to achieve the same results.

At least, that’s the theory. Here’s how the scheme (.pdf) works:

Alice and Bob have a two-wire cable between them, and two resistors each—we’ll say they each have a 10-ohm and a 1,000-ohm resistor. Alice connects a stochastic voltage generator and a resistor in series to each of the two wires. That’s the setup.

Here’s how they communicate. At each clock tick, both Alice and Bob randomly choose one of their two resistors and put it in the circuit. Then, Alice and Bob both measure the current flowing through the circuit. Basically, it’s inversely proportional to the sum of their two chosen resistors: 20 ohms, 1,010 ohms or 2,000 ohms. Of course, the eavesdropper can measure the same thing.

If Alice and Bob choose the same size resistor, then the eavesdropper knows what they have chosen, so that clock tick is useless for security. But if they choose a different size resistor, the eavesdropper cannot tell whether it is Alice choosing 10 ohms and Bob 1,000 ohms, or the reverse. Of course, Alice and Bob know, because they know which resistor they’re choosing. This happens 50 percent of the time.

Alice and Bob keep only the data from the clock ticks where they choose a different size resistor. From each such clock tick, they can derive one secret key bit, according to who chooses the 10-ohm resistor and who the 1,000-ohm. That’s because they know who’s choosing which and the eavesdropper doesn’t. Do it enough times and you’ve got key material for a one-time pad (or anything else) to encrypt the communications link.

I’ve simplified it a bit, but that’s the gist of it.

Interestingly enough, this key-generation mechanism is actually very similar to one described by Bennett and Brassard in the early 1980s using quantum properties (see Applied Cryptography, second edition, pages 554 to 557), but this one is all classical. That’s what makes it neat.

It’s also reminiscent of a 1940s scheme from Bell Labs. Details of that system are either classified or lost, but James Ellis described (.pdf) it in 1987 as inspiring his invention of public-key cryptography back in the early 1970s:

The event which changed this view was the discovery of a wartime, Bell-Telephone report by an unknown author describing an ingenious idea for secure telephone speech (reference 2). It proposed that the recipient should mask the sender’s speech by adding noise to the line. He could subtract the noise afterwards since he had added it and therefore knew what it was.

That “reference 2” is something published by Bell Labs called Final Report on Project C43. No one I know has seen a copy. Bell Labs cryptographers have searched the archives for it, and they came up empty-handed.

Did Kish rediscover a secure communications system from the 1940s? Or is this a retro-discovery: an idea that by all rights should have emerged in the 1940s, but somehow evaded human epiphany until now?

And most importantly, is it secure?

Short answer: There hasn’t been enough analysis. I certainly don’t know enough electrical engineering to know whether there is any clever way to eavesdrop on Kish’s scheme. And I’m sure Kish doesn’t know enough security to know that, either. The physics and stochastic mathematics look good, but all sorts of security problems crop up when you try to actually build and operate something like this.

It’s definitely an idea worth exploring, and it’ll take people with expertise in both security and electrical engineering to fully vet the system.

There are practical problems with the system, though. The bandwidth the system can handle appears very limited. The paper gives the bandwidth-distance product as 2 x 106 meter-Hz. This means that over a 1-kilometer link, you can only send at 2,000 bps. A dialup modem from 1985 is faster. Even with a fat 500-pair cable you’re still limited to 1 million bps over 1 kilometer.

And multi-wire cables have their own problems; there are all sorts of cable-capacitance and cross-talk issues with that sort of link. Phone companies really hate those high-density cables, because of how long it takes to terminate or splice them.

Even more basic: It’s vulnerable to man-in-the-middle attacks. Someone who can intercept and modify messages in transit can break the security. This means you need an authenticated channel to make it work—a link that guarantees you’re talking to the person you think you’re talking to. How often in the real world do we have a wire that is authenticated but not confidential? Not very often.

Generally, if you can eavesdrop you can also mount active attacks. But this scheme only defends against passive eavesdropping.

For those keeping score, that’s four practical problems: It’s only link encryption and not end-to-end, it’s bandwidth-limited (but may be enough for key exchange), it works best for short ranges and it requires authentication to make it work. I can envision some specialized circumstances where this might be useful, but they’re few and far between.

But quantum key distributions have the same problems. Basically, if Kish’s scheme is secure, it’s superior to quantum communications in every respect: price, maintenance, speed, vibration, thermal resistance and so on.

Both this and the quantum solution share another problem, however; they’re solutions looking for a problem. In the realm of security, encryption is the one thing we already do pretty well. Focusing on encryption is like sticking a tall stake in the ground and hoping the enemy runs right into it, instead of building a wide wall.

Arguing about whether this kind of thing is more secure than AES—the United States’ national encryption standard—is like arguing about whether the stake should be a mile tall or a mile and a half tall. However tall it is, the enemy is going to go around the stake.

Software security, network security, operating system security, user interface—these are the hard security problems. Replacing AES with this kind of thing won’t make anything more secure, because all the other parts of the security system are so much worse.

This is not to belittle the research. I think information-theoretic security is important, regardless of practicality. And I’m thrilled that an easy-to-build classical system can work as well as a sexy, media-hyped quantum cryptosystem. But don’t throw away your crypto software yet.

Categories: Computer and Information Security

Sidebar photo of Bruce Schneier by Joe MacInnis.