Tuesday, September 28, 2004
qDoS
Quantum Cryptography (QC) is all the rage in technical journals. It seems mankind has finally arrived at a point in our understanding of the fabric of the universe that we can take advantage of those immutable laws, and bend that fabric to our will. Glorious stuff indeed.
Among the claims that QC promotes is "perfect encryption": the ability to share information in a way that guarantees its security against an attacker of unbounded capacity. This claim, in and of itself, is valid. Following the protocols established for the execution of QC, such a channel can be established. The problem arises when we attempt to use the data in a real-world situation.
Current bandwidths of the quantum channel are very low-- somewhere on the order of Kbits/second. Further, the nature of the protocols requires that a significant number of these bits be discarded-- on the order of 60% in a highly optimized environment. Therefore, from a practical perspective, the use of the quantum channel as a means of securing the entire communication is unlikely for the foreseeable future. Instead, it is often used for Quantum Key Distribution (QKD).
The security concern at this point should be obvious: per the principle of the weakest link, our total communication channel is now only as strong as the algorithm used to encrypt the public channel. Therefore, our evaluation of the value of QKD as a distribution mechanism must be based solely on the value of a "perfectly secure" key exchange-- and not on the security of the entire communication. That, unfortunately, is a topic of discussion for a future article.
Before we even get to that point, we must consider other inherent vulnerabilities of the protocols in question. Specifically, I want to consider Denial of Service (DoS) attacks. In extant networking environments, DoS is achieved by the process of saturating various aspects of the network in such a way that normal traffic cannot be processed effectively; the network becomes unusable.
In the world of QC, significant emphasis is put on the fact that any attempt to eavesdrop on the conversation is detectable-- which is indeed the case. Unfortunately, it is the nature of that detection that represents a significant vulnerability that I have labeled qDoS. I will now examine the protocols and vulnerabilities presented, using the common cryptographic protocol descriptive notation in which Alice and Bob are communicants, and Mallet is the malicious party (having superseded Eve's traditional role as eavesdropper, as we shall see).
The first step in a QC/QKD protocol is sifting: the selection of bits at random from the quantum stream. We will leave out, for now, how the random determination of bits on both ends is achieved-- though it is another critical aspect of our weakest link analysis that should be considered, there are ways of dealing with this issue that in effect provide the sought after level of confidence. The bottom line is that in this process, the volume of the stream is significantly reduced, on average. However, we are left, in the end, with a collection of candidate key bits that move forward to the next stage.
Next, error correction is initiated. In this process, parity bits are used to verify the validity of the candidate key stream. These parity bits, considered to be "revealed information", further reduce the quantum channel bandwidth. However, an even worse problem lingers: the source of error. Error can occur for any of a number of reasons, most of which are related to various forms of noise. One, however, is the heart of this blog's topic: eavesdropping.
You see, the guarantee that eavesdropping will be detected is based on the fact that any attempt to do so will disrupt the measurements that occur in sifting, thereby revealing the attempt in the form of error bits. However, indicating that such an intrusion is underway does nothing to alleviate the fact that by simply having attempted to eavesdrop, our attacker has now become a disruptive force on the quantum channel: error bits, by definition, cannot be used by QKD. In effect, the principle at play here is if you seek, you shall not find-- you shall only destroy. The rather high bar previously established by DoS attacks (network saturation) has been replaced by the act of merely "observing".
This problem is exacerbated by potential solutions to traffic analysis. The concern, simply stated, is that the presence of communication on the quantum channel is sufficient evidence of the presence of encrypted communication on the public channel. One resolution is the establishment of a quantum channel backbone across which multiple QKD requests can be executed. While resolving the traffic analysis problem, this expands the scope of a qDoS attack to include all participants on the affected backbone.
In closing, naysaying is the easiest of tasks. I prefer to offer not just problems, but solutions. In this case, however, the solution is not very clear. When manipulating the principles of physics to achieve such a lofty goal, you inherit the risk that such manipulation brings with it an unacceptable consequence. If the issues outlined in this post are indeed real, alternatives are hard to come by: selecting a more amenable set of "laws of physics" is not an option.
This is an interesting field with a lot of positive potential. It is my hope that the negative potential I have outlined can somehow be rectified in a way that makes it a practical solution to a significant problem. In the meantime, there are hints, scattered throughout this post, that other issues are afoot. Interesting fodder, to be sure. Stay tuned!
