[Infowarrior] - Quantum cryptography may not be as secure as we thought

[Richard Forno]

Quantum cryptography may not be as secure as we thought

By Chris Lee | Published: May 15, 2008 - 05:05AM CT

http://arstechnica.com/news.ars/post/20080515-quantum-cryptography-not-as-secure-as-we-thought.html

Quantum cryptography is often touted as the ultimate in information  
security, but that doesn't make it immune to successful attack. A  
recent publication in IEEE Transactions on Information Theory details  
how the very process of ensuring security can be used by evildoers to  
send fake messages on a network. As with all good cryptography  
researchers, the publication also includes a method for defeating the  
attack.

The security provided by a quantum system relies on the fundamental  
laws of nature rather than the inability of computers to factor large  
numbers efficiently. The sender, traditionally called Alice, encodes  
information in the quantum states of, for instance, light. The  
recipient, imaginatively referred to as Bob, measures the quantum  
state. That measurement depends on what is called the basis and, if  
Bob and Alice don't have the same basis, Bob will not receive the same  
information that Alice sent. This feature is used to generate a secret  
key that can then be used to send information over more public channels.
Generating a key

The key generation process looks like this. Alice takes a random  
string of ones and zeros and encodes them in the quantum states of  
light. In doing so, she doesn't use the same basis, but rather flips  
randomly between two different basis sets. Bob also flips his basis  
sets and records the bit values that he receives. He then transmits  
his basis flips to Alice and she sends her basis flips to Bob. Those  
cases where, at random, the two agree on the value received, the bit  
values encoded by Alice are used as the key. An eavesdropper (who,  
amazingly enough, is always called Eve) can obtain all the publicly  
sent information and still not obtain the secret key. If she attempts  
to measure the quantum bits, they will be modified, meaning that Alice  
and Bob will see errors in the bits where their bases were not the same.

One vulnerability of this system is the man-in-the-middle attack,  
where Eve plays the role of Alice for Bob and Bob for Alice. Every  
security system fails at this point because sometimes you have to  
trust that Alice really is Alice. One way to try and ensure the  
security of the exchange is to begin communications using a small,  
shared key. This key is then expanded using the quantum cryptographic  
system. Part of the expanded key is set aside so it can act as the  
shared key that initiates the next session. The remainder is used to  
encode messages sent in the current session. Assuming Eve has no  
knowledge of the starting key, the system is secure.

But what if Eve knows some of the key already? Well, then problems can  
arise. Eve can grab the full key provided certain conditions are met:  
first, she has to be able to capture the quantum and classical  
information sent by Alice before Bob sees it. Second, she has to be  
able to modify the information in the quantum channel—a modification  
that may not necessarily be detectable, since it does not require  
measuring the quantum state—though I am not certain that this is truly  
practical. If these conditions are met, then Eve may be able to obtain  
the key for this session and, by extension, all future sessions.
Probabilities and coincidences

The explanation for how this works is a little technical but it  
involves probabilities. The key is generated from coincidences in two  
sets of random numbers, meaning that any number within a bit range is  
equally probable. However, if Eve has part of the key, it can be used  
to break up the distribution of possible numbers, making some of them  
much more probable while completely eliminating others.

Eve can then modify the information in the quantum channel to make  
just a few numbers within the distribution much more probable. Since  
Eve has not measured the information in the quantum channel, and the  
information in the classical channel is public, Alice and Bob remain  
unaware of Eve. At this point, Eve can simply try out the few  
remaining possible keys on various messages until she achieves  
success. Since sessions using the same key will last for a long time,  
Eve can be sure to get some of the good sauce from Alice and Bob.

So, what can Alice and Bob do about this? There are several solutions,  
which mainly involve making sure that Eve cannot delay transmissions  
in the quantum channel long enough to be able to modify it after  
receiving the classical information. What the authors propose is  
similar, but offers a guarantee that the message was not delayed. In  
their scheme, Alice sends a random string of ones and zeros on the  
quantum channel. Bob selects a bunch of bits from the message at  
random and sends them back to Alice using the quantum channel. Alice  
evaluates the bits and adds them to the bit string generated by the  
basis flips. This is then sent to Bob, who replies by sending his  
basis flips, and the key is generated. Now Eve cannot modify Alice's  
message before sending it on to Bob because she does not have the  
basis state string required to modify the message.

So what does this all mean? It means that a security protocol that is  
designed to counter a threat that does not yet exist (quantum  
computing) is slightly more secure than it was yesterday.

IEEE Transactions on Information Theory, 2008, DOI: 10.1109/TIT. 
2008.917697