Quantum Cryptography Cracked?

29 April 2008--Quantum cryptography, touted by scientists as the ultimate unbreakable code, may turn out to be susceptible to eavesdropping after all when implemented practically, according to a Swedish duo.

”Quantum codes are supposed to guarantee 100 percent security,” says Jan-Ake Larsson, associate professor of mathematics at Linkoeping University, in Sweden. ”If they don't live up to that promise, that's a problem.”

Larsson and his former graduate student Jorgen Cederlof, who now works for Google, say they have spotted a flaw in practical quantum codes. Their report on this flaw and a patch for the problem appear in the April issue of the IEEE Transactions on Information Theory.

The most secure codes currently in use rely on public-key cryptography, whose security stems from the fact that computers today cannot factor very large numbers within a useful time period. However, in theory, given sufficiently powerful computers, these codes can be cracked.

Quantum cryptography, in contrast, is supposed to be unbreakable, even in theory, because its security is based on a fundamental tenet of quantum mechanics. It turns out that the very act of measurement in quantum mechanics changes the nature of the quantum system being observed. Thus, if an eavesdropper listens in on a quantum message between two parties, he or she changes the message in a way that is detectable. Through a multistep process, quantum encryption systems--and there are at least three on the market now--use the security of quantum mechanics to generate cryptographic keys. These quantum keys are ciphers used to encode and decode messages.

The process of key generation, though based on quantum physics, also requires exchanging some information on a regular ”classical” channel. Eavesdropping on the classical channel cannot be detected. One of the final steps in setting up a quantum key is to authenticate the communicating parties--determining that Bob is really talking to Alice, not some eavesdropper.

If there is no authentication, Alice and Bob will be open to a ”man in the middle” attack, as it is termed by code breakers. The attack would work like this, Cederlof explains: ”Now Eve comes along, buys a couple of [quantum encryption] devices identical to the ones Alice and Bob have, cuts the cables between Alice and Bob, and connects her devices at both ends. Now Alice will think she is talking to Bob, but in reality she is talking to Eve. Eve just acts as Bob would have, and after a while Alice and Eve have created a shared secret key. The same thing happens between Eve and Bob. When Alice tries to send an encrypted message to Bob, she will encrypt it with a key known only to Eve (but which Alice thinks only Bob knows). Eve intercepts the message, decrypts it, reads it, encrypts it with the key she shares with Bob, and sends it to Bob. Alice and Bob never suspect anything.”

The way around this is to communicate classically and make sure Alice is really talking to Bob. But that is exactly where the vulnerability lies.

”To our surprise, the authentication was not secure,” says Larsson. He and Cederlof say that it is difficult to eavesdrop, but the possibility does exist. In their paper they suggest a patch. ”The modification we propose is basically an extra exchange of a small amount of random bits on the classical channel,” says Larsson.

According to Tassos Nakassis a computer scientist at the National Institute of Standards and Technology (NIST), in Gaithersburg, Md., the error may have originated because quantum cryptography is an emerging interdisciplinary field that combines advanced quantum physics with traditional code making. Authentication and its weaknesses may have gotten lost in the conversation between quantum physicists and classical cryptographers.

The Swedes went looking in just the right place for a vulnerability, according to Bruce Schneier, an expert in cryptography and chief technology officer at BT Counterpane, in Santa Clara, Calif. ”Authentication has always been a problem with quantum crypto,” he says.

Audrius Berzanskis, chief operating officer at the quantum cryptography systems firm MagiQ Technologies, in New York City, claims his firm's systems are immune to this kind of attack, because they are overly conservative with respect to how they treat errors in the quantum channel--whether or not the errors are caused by an eavesdropper. This conservatism comes at the cost of the rate at which quantum keys are generated. And Berzanskis adds that Larsson and Cederlof's patch might allow the key rate to increase. Experts from outside quantum cryptography companies agree that the vulnerability is real, but most think it would be impractical to exploit.

”This is an interesting issue and worthy of the awareness of the community,” says physicist Joshua Bienfang, who works on quantum cryptography at NIST. But he notes that Larsson and Cederlof correctly emphasize that the attack relies on Eve capitalizing on opportunities that occur with very low probability. In their worst-case scenario, with a computationally omnipotent Eve, they estimate it would take something on the order of nine months to break the system. And he says that the patch offered should ”firmly shut the door on this type of attack.”

Norbert Lutkenhaus, a physicist at the Institute for Quantum Computing, in Canada, summed it up. ”Practically, I don't think it is a threat of any kind,” he says. ”But it is good to know about the vulnerability.”