Turning the Key on Data

Quantum cryptography advances threaten to shake up traditional approaches to computer security.

Math is hard.

Those three words sum up the premise upon which the security of the trillions of bits of encrypted data crisscrossing the Internet daily depends. The encryption algorithms used in everything from Web browsers to virtual private networks to the servers holding the nations top-secret data at the National Security Agency are all built on mind-numbingly difficult, one-way equations.

And the keys used to encrypt and decrypt the data are no bargain, either. Each key is an incredibly long prime number and all you need to do to recover the key is factor that prime number. To put the difficulty of that problem in perspective, consider this: A mathematician at the University of Notre Dame, in South Bend, Ind., recently solved a 109-bit key challenge from Certicom Corp. by using 10,000 computers running around the clock for 549 days.

The keys used in most commercial cryptosystems are more than twice that long.

This system has been adequate for more than 20 years, but some recent advances in the field of quantum cryptography are threatening to turn the security industry on its ear.

MagiQ Technologies Inc., a New York-based startup, recently announced that it has developed a system capable of using quantum cryptography to encode and distribute encryption keys. The solution, code-named Navajo, consists of an appliance at either end of a dedicated communications link. The keys are encoded one photon at a time and sent down the wire to the receiver.

Quantum cryptography relies on the properties of photons, or single particles of light. Each photons polarization can be expressed in one of three quantum bases: circular, rectilinear or diagonal. Prior to a transmission, the sender and receiver agree upon which basis they will use. The sender then encodes the photons in quantum states and sends them to the receiver.

The receiver observes the states and then compares what he or she has received with what the sender has sent.

Such transmissions are essentially entirely secure, thanks to Heisenbergs uncertainty principle, which dictates that anyone who intercepts the data would alter it simply by observing it.

This would introduce whats known as quantum noise and alert the receiver to the fact that the transmission had been intercepted.

MagiQs solution uses quantum cryptography to encode and distribute the keys. While this is a major leap forward from the current method of key distribution, experts say that the security of the crypto keys is hardly the biggest problem facing existing cryptosystems.

Given the relative difficulty of factoring even a small key, they say, there is little need in the everyday enterprise market for quantum key distribution.

"Think back to all the computer-security vulnerabilities and break-ins and hacks and disasters. Can you think of any that can be traced to a key- generation problem? This device doesnt solve a problem that people have," said Bruce Schneier, chief technology officer of Counterpane Internet Security Inc., in Cupertino, Calif., and a noted cryptographer.

"Its like weve put a stake in the ground to block an oncoming army, and were arguing whether the stake should be a mile tall or a mile-and-a-half tall, Schneier said. "Honestly, the army will just go around the stake."

Others believe that quantum key distribution does hold some promise and shows that scientists are getting closer to creating a fully functioning quantum cryptosystem usable in the real world. "The main advantage is that the security relies only on physics and not on hard math problems," said Burt Kaliski, director of RSA Labs, part of RSA Security Inc., in Bedford, Mass. "Its the kind of research the industry needs to do. But, right now, its not convenient because its only for two people [on a dedicated communications link]. If there are routers in the middle, you somehow have to be able to trust those routers."

Two professors at Northwestern University, in Evanston, Ill., think theyve solved that problem. Prem Kumar and Horace Yuen have developed what they say is the first quantum cryptosystem to work over long distances at high speed on existing fiber-optic lines.

The system can be used on networks that have routers and amplifiers in-line and can operate as fast as 100KB per second.

The main innovation of the Northwestern system is that it uses the phenomenon of quantum noise to make transmissions more secure. Because anyone trying to eavesdrop on the transmission would alter the message, it would thereby become unreadable to the eavesdropper.

The receiver, however, can use the shared secret key that he or she has exchanged with the sender to remove the lions share of the noise and decipher the message.