Schneier on Security
A blog covering security and security technology.
« Gladwell on Profiling |
| Check Washing »
February 7, 2006
More on Kish's Classical Security Scheme
Here's an interesting rebuttal of Laszlo Kish's theoretically secure classical communications scheme.
EDITED TO ADD (2/18): Kish's response.
Posted on February 7, 2006 at 4:18 PM
• 50 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
I agree that fundamentally the classical approach cannot match the quantum entanglement. However, it may be as good as is needed for practical security, and then the question is moot.
I liked the original Bruce's comment that exsercising in better crypto schemes is like building a taller pole instead of a fence. The classical appoach has a definite advantage of being here, now, and virtually zero cost. So while the statement "this is fundamentally not as good as quantum crypto" is true, Kish did find a darn good communication method.
Kish did find a darn good communication method.
Or not. There's very little indication that his system could actually be built or would in fact provide any secrecy, let alone the theoretical secrecy claimed. I wrote some comments of my own here, and attracted a response from the man himself:
I don't know for sure that it doesn't work. I'm not really qualified to judge. But I also won't believe that it *does* work - work at all, not just work perfectly - until it's gotten some serious review. I'm aware that he's working on some research that addresses some of the points I raised. It'll be interesting to see the review of that, too.
Is “breaking into a store today, only to find out that last week the store had already shipped out a video of you doing it to every police station in the area��? really that much more likely, or plausible, than a working perpetual motion machine?
I think that the transient point you raised is only valid if taken together with the "tapping closer to either end" point. On its own, the synchrony is not that important: Bob and Alice may well keep the circuit open, change their resistors, and then close th circuit. If they ensure that the resistor change time is much shorter that the "close the loop" period, then any transients will always be on the total resistance.
The spatial assymetry does seem to be an issue though.
However, if both this and quantum crypto "solve the wrong problem" then none of this is important :-) At least Kish's scheme is free :-)
I think that the transient point you raised is only valid if taken together with the "tapping closer to either end" point. On its own, the synchrony is not that important: Bob and Alice may well keep the circuit open, change their resistors, and then close the circuit. If they ensure that the resistor change time is much shorter that the "close the loop" period, then any transients will always be on the total resistance.
The spatial assymetry does seem to be an issue though.
However, if both this and quantum crypto "solve the wrong problem" then none of this is important. At least Kish's scheme is free :-)
Nothing wrong with what Terry has written (although trying to explain Quantum effects using real world examples is never going to work ;)
He has kind of missed the point though Kish is claiming non quantum security, to knock the claim down you will have to prove it is not secure in the non quantum world.
Personally I think it is not secure in either world but there is currently insufficient information to say beyond doubt. Kish's original paper was very very light on theory....
As they say Time will tell (on us all in the non quantum world ;)
He's completely missed the point. Kish never claimed to have an equivalent system to QC, *except in the sense that no information is available on the wire*. he's proposed a damn good substitute for it, though.
It's broken, though, and I think I can prove it. This margin's a bit tight, though.
Oops... I spoke too soon. I just went and re-read the paper, and in the conclusion, Kish writes:
"...quantum computers are unable to break this code moreover it is more
secure than quantum communication."
That's got to be dodgy.
Alex Young: Good catch on the "more secure than QC" quote That was exactly the line I went back and looked for myself to make sure Kish really was claiming "more" or "better" than quantum.
I loved Oldman's comment, because yes indeed, perpetual motion machines do exist in the physical world, but only in the very narrow category of macroscale quantum Bose condensates: mechanically in circulating superfluids (liquid helium-4 II and some deeper-cold He-3 paired atom fluids), and electrically in superconductor loops, which can maintain currents for at least thousands of years--and with really deep cold, for potentially much, much longer. Of course, all such systems require the high energy cost of refrigeration to near absolute zero, which is why for all practical purposes you still cannot get perpetual motion on a warm place like earth. (Now on Pluto, Sedna, Xena, or Buffy, it might be a different story...)
Quantum is... odd, to say the least.
"Quantum is... odd, to say the least."
QM is odd, and at the same time not odd.
It all depends on your point of view.
I'd like to modify Godwin's Law:
1. Any cryptosystem based on time travel loses.
2. Criticising a cryptosystem because it doesn't use time travel also loses.
Kish's scheme is broken, yes, but you can easily think up an equivalent scheme using optics, and avoid transmission line effects that way...
A theoretical time-based attack on Kish’s classical security scheme.
Kish’s classical security scheme is designed to defend against a single eavesdropper on a line. The fundamental failure of this scheme appears to be that there is no analysis of how the propagation of these classical physical laws can be used to the attacker’s advantage.
The classical physical electrical laws describe how large numbers of electrons react in conductive media. The problem is that unlike collapsing a single quantum mechanical wave, these electrons take time to move a specified distance. Specifically, the upper limit of their motion is the speed of light, which is roughly 3.0 *10^8 m/sec. This means that for any electrical change (ex: use of a different resistor) to propagate through an entire wire, it will take time. This fact can be used to an attacker’s advantage.
Part 1: The simple attack.
One assumption made in this paper is that there is only one tap on the wire. Let us assume that there are two taps. Each tap records the resistance values as described in the paper, using very small time-frames. Given enough samples, one can get a good value for resistance at any point in time at either tap. Now compare the two taps. Assuming that they are a significant distance apart, there will be some time delay in the changes of resistance at either tap. The time delay and its direction inform you as to which resistor is at the sender and which one is at the receiver.
Part 2: Down to one tap.
Actually, the complexity of two taps does not appear to be needed, at least in theory. For Kish’s scheme to work, both sides need to change their resistance at the same time as far as the observer is concerned. For example, if both sides changed their resistance at exactly the same time, only a tap in the middle of the wire would note each resistance change at the same time. In other words, if one checks for the resistance sufficiently frequently, and one is not unlucky enough to have tapped the single point in the wire where both resistance changes occur simultaneously, one could merely log the resistance changes at your present point. Since the waveforms propagate to your point at different times, you should be able to record each change individually, which means that you note each individual resistance change (not just the two together as a unit).
Defense against these attacks:
The primary defense against these attacks is to reduce the time it takes for an electrical signal to go down the wire to the absolute minimum amount of time to get a reliable determination of resistance; basically, if the attacker cannot distinguish the time that the resistances change, this attack is useless. This basically means using a short wire.
"This basically means using a short wire.
One thing you forgot the punch line
"To be practical"
Your reasoning is exactly the same as mine which I posted (about two taps) on Bruces original post.
I keep looking to see if I have missed something but there is nothing in Kish's paper to go and look at that might be hiding something.
I ran the logic through with someone who has a masters in EE. A resistance change does, in fact, propogate through the system at less than the speed of light :-) . I don't think that we (or Terry) are missing anything; I think that Kish was limiting his thinking to one single type of attack.
I think a hell of a lot of people are missing a hell of a lot of points. I'll limit myself to one that bothered my about the original scheme and the analysis thereof talked about most here: the multiple taps issue.
If you tap into some communications medium you've changed the signal characteristics of that system. Your presence has been announced. End of Story.
To understand the original idea and why it doesn't mean jack for a truly useful communications method you also need to understand the concepts of SNR, Signal Spreading, Processing Gain, Impedance, etc. Needless to say, lots of psuedo-random spread-sprectrum and pulse communications systems are out there and working just fine--without depending on "quantum properties."
Frankly, I think that this guy has probably never in his life actually built a real communications system--because if he had (instead of just modeling it mathematically, or building a set model in a test environment--may it be real or virtual) he'd know that this just isn't going to work. On top of the fact that it is "too good to be true," then comes in the whole SNR thing: It doesn't matter if it is quantum encrypted if nobody could ever decode it--it becomes mere noise.
"If you tap into some communications medium you've changed the signal characteristics of that system. " - I agree. However, one or more of the attacks described in the paper requires a tap on the communications medium. Therefore, I assumed that the given communications medium was subject to interference that may exceed the effect of a tap, and that a tap might be mistaken for such interference. These may be unrealistic assumptions, but they appear to be the same ones as those in the paper.
"On top of the fact that it is "too good to be true," then comes in the whole SNR thing: It doesn't matter if it is quantum encrypted if nobody could ever decode it--it becomes mere noise." Maybe I'm missing something, but this looks like a 1:1 SNR (which is what I assume you're objecting to). However, both sides (at least in theory) can determine what is noise, and what is signal, since that's dependant on the resistance of the entire line, as well as their chosen resistor.
"Frankly, I think that this guy has probably never in his life actually built a real communications system" - Nor have I.
Laszlo Kish contacted me with a couple of links to preprints that attempt to address criticisms of the system. He said he'd found it difficult to respond in this thread due to being rejected by the spam filter.
I think the second link there is most significant to the points I raised; it argues that the system can maintain "practical" absolute security even when the wire is tapped in multiple places. The "transient" and "wire resistance" issues he discusses are substantially the same issues I thought were most significant.
The argument seems to be that by making the change between resistances slowly and keeping the resistances large in comparison to the resistance of the wire, it's possible to make the differences among measurements (across time for the transient attack, across different taps for the wire resistence attack) small enough to be undetectable, and so it offers practical absolute security that comes arbitrarily close to absolute security.
There's also a claim that quantum cryptography also offers only practical absolute security instead of being guaranteed by a hard physical law, so that this system is just as good for a lower dollar price.
Due to the common belief that QC is totally secure (it is not, see below), many people have doubted the claim that the Kirchhoff-loop-Johnson-like-noise (KLJN) cipher can be more secure than quantum crypto. I would like to show you why it is so. First of all, let us see what are the main sources of limitations of quantum security. I paste here a good text from www.cs.dartmouth.edu/~jford/crypto.html:
"Quantum Privacy Attacks
Quantum cryptographic techniques provide no protection against the classic bucket brigade attack (also known as the "man-in-the-middle attack"). In this scheme, an eavesdropper, E ("Eve") is assumed to have the capacity to monitor the communications channel and insert and remove messages without inaccuracy or delay. When Alice attempts to establish a secret key with Bob, Eve intercepts and responds to messages in both directions, fooling both Alice and Bob into believing she is the other. Once the keys are established, Eve receives, copies, and resends messages so as to allow Alice and Bob to communicate. Assuming that processing time and accuracy are not difficulties, Eve will be able to retrieve the entire secret key -- and thus the entire plaintext of every message sent between Alice and Bob -- without any detectable signs of eavesdropping.
If we assume that Eve is restricted from interference of this kind, there are similar methods she can still attempt to use. Because of the difficulty of using single photons for transmissions, most systems use small bursts of coherent light instead. In theory, Eve might be able to split single photons out of the burst, reducing its intensity but not affecting its content. By observing these photons (if necessary holding them somehow until the correct base for observation is announced) she might gain information about the information transmitted from Alice to Bob.
A confounding factor in detecting attacks is the presence of noise on the quantum communication channel. Eavesdropping and noise are indistinguishable to the communicating parties, and so either can cause a secure quantum exchange to fail. This leads to two potential problems: a malicious eavesdropper could prevent communication from occurring, and attempts to operate in the expectation of noise might make eavesdropping attempts more feasible. The first problem is not limited to quantum communication, and is generally ignored. The second has a solution in a recent paper by Deutsch et al. ."
Now let us compare the security of QC with that of KLJN.
1. You can extra about every 100ths raw bits without being discovered by the error statistics radar of QC. This kind of eavesdropping is not detected and it can virtually extract an infinite amount of information. This information leak is about a million times bigger than the level of leaks software security experts would like to have. What is very important: this information leak exists even in the idealized QC.
2. The idealized KLJN cipher has zero information leak.
3. The practical KLJN cipher will have some due to wire capacitance and resistance effects. It depends on how much money you are allowed to invest into the cable. However it is easy to keep that leak orders of magnitude smaller than that of QC, if needed.
4. If the eavesdropper wants to extract information quickly and efficiently, he has to use a more invasive attack by extracting, multiplying and sending back the photons. In this case, QC detects the eavesdropper by the increased error statistics. To make that statistics we need a large number of communicated bits, in the order of 1000 bits. The eavesdropper will extract a similar amount of information before getting discovered.
5. If the eavesdropper is using similarly efficient attack at the KLJN cipher then she can extract at most one bit of information before getting discovered.
6. The KLJN cipher is naturally protected against the man-in-the-middle attack. This kind of attack is a difficult matter in QC, see above.
In conclusion, the fluctuation-dissipation mechanism and the maximal entropy state of thermal equilibrium is a very good cipher. Moreover, it is very robust compared to single photons.
My response to Terry Bollinger's rebuttal can be downloaded from here:
I asked Bruce to make a note with a link at Terry's entry but that will probably take longer time. Until then, this is it.
(1) Cost comparisons approach
(2) Physics of eavesdropper detection
1) Cost comparisons approach
On Feb 12 Matthew Skala said:
"There's also a claim [by Laszlo Kish] that quantum cryptography also offers only practical absolute security instead of being guaranteed by a hard physical law, so that this system is just as good for a lower dollar price."
Wow. I thought this thread was fading and hadn't checked for a few days.
Briefly (it's late), I find such the relative-merits argument that Skala ascribes above to Kish to be much more interesting than a bald claim of superiority to quantum methods. Notably, when you start looking into construction of real-world quantum communications system, mundane issues such as signal-to-noise issues start to make them look a lot more like more conventional systems. That alone makes such an argument interesting.
So, does Kish make a persuasive argument that real systems based on his methods can always asymptotically approach a given level of security faster and at lower cost than methods based on quantum security?
Perhaps others could comment more on that. Personally, I would think that such an argument could prove quite difficult to validate, since it must necessarily make a lot of assumptions about what can and cannot be done in the future by folks working on both approaches.
More later on that.
(2) Physics of eavesdropper detection
And I nearly forgot… this snippet from an earlier Feb 9 comment by RvnPhnx was also interesting:
"If you tap into some communications medium you've changed the signal characteristics of that system. Your presence has been announced. End of Story."
Hmm. Why does the image of someone placing a small antenna off to the side of a microwave relay receiver horn come to mind?
To be precise, an eavesdropper runs the risk of altering the characteristics of a signal only if she dares to intrude on the "good" part of the signal that the original users were planning to process. If their transmission media is leaky and is designed to discard at least some part of the signal during transmission, then obviously no such guarantees of detection can be made.
There is still a chance of hiding if the eavesdroppers do intrude on the primary signal path, but it requires fully transparent replication of the signal to disguise the presence of the eavesdropper. That’s even trickier than it sounds, since any delay in the signal propagation time would could also reveal the presence of an eavesdropper. That puts an interesting physical constraint on such replicating eavesdroppers, since in general it means that transparent replication can only work if the signal travels at less than the speed of light over the remote segment of the signal path where the eavesdropper is lurking. The eavesdropper must then speed up the signal for a time sufficient to make up for the delay that it introduced -- not an easy prospect. Alternatively, the replicator could be designed to have such a tiny delay that it is well within the normal arrival-time fluctuation profile (one would expect it to be quite narrow for electromagnetic beam systems) for the system.
So, for systems such as microwaves, laser cross-connects, optical fibers, and unswitched hardwired communication systems, transparent replication can be made quite difficult due to the close approach to the speed of light limit. For instances such as fibers, you can also get very conservative on the amount of signals losses that might be detectable outside of the main path.
Alas, there is a certain creature called the Internet that is so slow, variable, and diverse in its paths that forms both of capture and of transparent replication are very plausible indeed.
All of this could be made into a nicely physical model of eavesdropper delectability, I think. I'll try to add a short white paper to my web site soon to capture the above, with a couple of diagrams added. The speed-of-light limit ties in nicely to light cones, and the signal loss to the inherently leaky nature of wave phenomena (and oh yes, as the early quantum folks pointed out nearly a century ago, everything has some wave behavior).
Concerning your point 1, please read the response to your rebuttal and refences in it. See at:
Moreover, you talk about "signal-to-noise" ratio issues as difficulties. Yes, for quantum, that is a terrible problem. This is the BIG POINT where everybody immediately agreess, that quantum is week and classical is strong: the ROBUSTNESS OF INFORMATION. You want to detect single photons. Your noise is killing you and seriously compromising security because your eavesdropper hides in noise. The more noise the better for her. However, in the classical cipher you can have 20V in the cable. You do not even have to use low-noise electronics. In my response to your rebuttal I mentioned that we are talking about billion times billion (10^18) photon energy!
Concerning your point 2, I have a question: is that about quantum or classical? If quantum, the multiplication of stolen photons is easy: you need only an optically active medium, like laser amplifier. In the classical case, the Johnson-noise cipher, any wave solutions are excluded by Eq(9) of my first paper.
Moreover, if the eavesdropper tries to emit a high-frequency probing signal into the cable, that will immediately be picked up by the current sensors at the two ends, which is the defense against the eavesdropper; see in my first paper and in the paper about the man-in-the-middle attack. But even this defense is unnecessary because the low-pass filters at the end of the line (see the figure in my response to Scheuer and Yariv) will remove that.
I wrote a post on the older thread not knowing about this one. I also put it on my blog which is linked on my username below.
Perpetual motion machine??? I updated the response to Terry Bollinger with this and some other issues.
This is my last shot, for the moment, because I am very busy, and I will try to not read blogs. If you submit something significant, please send the text to my email address, too, so that I can respond to it if it is relevant.
Teleportation of classical information: there is a very interesting preprint by Oliver Cohen on the arxiv server:
Here is the abstract:
The standard quantum teleportation scheme is deconstructed, and those aspects of it that appear remarkable and "non-classical" are identified. An alternative teleportation scheme, involving only classical states and classical information, is then formulated, and it is shown that the classical scheme reproduces all of these remarkable aspects, including those that had seemed non-classical. This leads to a re-examination of quantum teleportation, which suggests that its significance depends on the interpretation of quantum states.
Laszlo Kish asked on Feb 17:
"Concerning your point 2 [about creating a model of eavesdropper detectability], I have a question: is that about quantum or classical? If quantum, the multiplication of stolen photons is easy: you need only an optically active medium, like laser amplifier. In the classical case, the Johnson-noise cipher, any wave solutions are excluded by Eq(9) of my first paper."
My intent there was just to to state more clearly a few issues that should necessarily be involved in any case in which detection of eavesdroppers is a strong goal of the communication event. The framework I used is classical -- my passing invocation of light cones is a strong giveaway there -- but it was my intent to make any assertions general enough to include quantum.
I'll certainly look at rebuttal of my rebuttal, but please note that for multiple reasons I'm operating on a slow response scale on this thread. It's very interesting, make no mistake, but my time is limited by other priorities.
OK, I looked over Laszlo Kish's rebuttal of my rebuttal. I think I can safely say: That will take some time to reply to properly.
Figure 2 concerns me. Laszlo, you seem to be saying there that anyone -- not just me, but anyone -- who does not fully accept your complex and wide-ranging theoretical argument for your KLJN cipher is implicitly rejecting either (or both) conservertion of energy and the integrity of linear algebra. Um... ouch. I'm quite fond of both, myself. I suspect many others who do not yet fully understand your KLJN cipher would also disagree with such a characterization of their beliefs.
Perhaps you could amend that one a bit to make it an assertion aimed at me only, rather than one that appears to apply to just about anyone who does not immediately comprehend the logic behind your KLJN cipher? I think that might carry your case better with other readers.
Figure 2 is, of course, relevant for the idealized case, the Kirchhoff loop with noisy resistors (the figures in the original paper show that). Then the conclusion is straightforward. Not two but three laws are relevant: Energy conservation law (because Kirchhoff's loop-law is based on that); Second law of thermodynamics (because the thermal noise's zero-net-power rule is based on that); and theory of linear algebraic equations (because the "two unknown variables from two equations" result is based on that).
Maybe, you are right, I should write more details about the physics, especially about the second law versus the thermal noise because that is not widely known. (My students will write the exam about that later today). I briefly described that in the first paper. The net energy flow between the resistors is zero. As a conclusion, the current-voltage crosscorrelation will be zero. There is no more new information to learn than themselves the two spectra (current and voltage). And that makes only two independent equations for the eavesdropper. //
Concerning Laszlo B. Kish’s Classical Security Scheme and the Feasibility of Man-in-the-middle attacks.
In [1,2], Dr. Kish argues that man-in-the-middle attacks on the communications medium may be mitigated by transmitting state information—instantaneous current and voltage amplitudes—across a public channel, whereby the sender and receiver compare such information to ensure congruence. If discrepancies in such measurements should arise then it is probable that an attacker has installed equipment to impersonate the opposite side, or has injected a ‘current spike’ in order to ascertain the values and relative locations of the resistors.
This solution relies upon the implicit assumption that the information transmitted via the public channel is secure; i.e., the state information received by either side has not been falsified. This assumption cannot be sustained as the channel is neither authenticated nor tamper-proof, and is thus subject to a man-in-the-middle attack.
In the idealized case, we must assume an infinitely resourceful attacker; furthermore, this attacker must be given complete control over the various communication mediums of the system. A man-in-the-middle attack could be mounted by any of the methods detailed in [1,2]; e.g., by injecting currents, or making use of noise current and voltage generators. An attacker would simply need to modify or replace the state information transmitted via the public channel to match the properties of his or her generation equipment or current spike to defeat the countermeasures detailed at the beginning of this letter.
To counter such attacks, Dr. Kish stipulates the use of a communications medium impervious to jamming via ‘non-jamable radio transmission’ . In practice, a non-jamable radio transmission would be difficult, if not impossible, to attain. In addition, using a wired transmission medium would render these attacks trivial.
 L. B. Kish, "Totally secure classical communication utilizing Johnson (-like) noise and Kirchoff's law", Physics Letters A, in press; preprint at http://dx.doi.org with code doi:10.1016/j.physletb.2003.10.071; also at http://arxiv.org/physics/0509136.
 L.B. Kish, "Protection against the man-in-the-middle attack for the Kirchhoff-loop-Johnson(-like)-noise cipher and expansion by voltage-based security", Fluctuation and Noise Letters 6 (2006) L57-L63.
To Ryan M. Gerdes, about the public channel issue.
These are good questions and valid for the classical channel of quantum communication, too. This is the field of classical software security, so those experts can answer this. It is important to note that the KLJN and quantum crypto need the very same kind of classical channels. I supposed that the problem of public channel was already solved/clarified for quantum so I simply imported the concept to the KLJN cipher.
Actually, the very same matter (but with quantum) was already mentioned on Bruce Schneier's older blog site http://www.schneier.com/blog/archives/2005/12/... by "Ouah" at December 16, 2005 03:46 AM. He/she wrote:
"About authentication and quantum crypto. Yes, you need an authenticated channel, and? With classical communications you also need an authenticated channel and we know how to build one. But with quantum crypto we need a perfect authentication? Yes and we also know how to do that, take Wegman-Carter authentication codes which are unconditionally secure."
Thus, I guess, this is the answer. I am sure the software/network security experts can say much more.
Thank you for your response.
I am admittedly not an expert; being merely a humble electrical engineering graduate student performing security research of the physical network layer. ;]
The ultimate security of the KLJN rests upon ones ability to secure the public channel, as information pertinent to and necessary for the security of the system are being transmitted across it. All of the methods described in your works to mitigate man-in-the-middle attacks assume that the information transmitted across the public channel is trusted—that the sending party has been authenticated, as it were.
I agree that an authenticated channel is necessary for, and could be implemented to produce, a secure public channel; however, the security of the KLJN system can never be greater than that of the public channel. If the public channel is to be authenticated using classical methods—SSL certificates for instance—then it cannot be made absolutely secure, foregoing the use of one-time pads, even in the idealized setting described in your papers. Thank you for your time.
Ryan M. Gerdes,
First of all, may I repeat it: quantum communication has the very same problem, so you should say "KLJN and quantum". However, the quantum-related network experts say that the situation is fine. Network security people should answer this. I think the key is the "publicity" of the information. But my 2 cents are here again, same as before, but with different words.
The information in those public channels does not have to be "secure" but "accurate". I think the "non-jammable radio station" term, which I imported from the quantum field, is a good illustration of the need.
Though it may be difficult to use radio stations, I am pretty sure that it is possible to do similar solutions in the network. The simplest solutions would be to connect the sender and receiver via a number of independent internet routes. That would be very difficult to jam, I guess.
Your conclusion is misleading. Your say that the "security" of KLJN (and therefore that of quantum) cannot be better than the "security" of the public channel. We are talking about different kinds of "securities". What we need from the public channel, is information assurance, not secret information transfer. I think, the non-jammable radio station and its network analogies are very good illustrations of the need. If you can jam the "radio station" then the KJLN and quantum are still "secure" because the data stay secret, though you would impede their use.
Thank you for your response, these exchanges have been especially fruitful for me, and I hope that they have been useful to you as well. I am sorry that my response has taken so long, but you have given me much to think about and research.
I agree that the problem of public channel authentication has been solved for quantum key distribution (QKD) through the use of Wegman-Carter (type) authentication (WCA); however, it has not been shown that the KLJN can make use of unconditionally secure Wegman-Carter authentication, or any other type of unconditionally secure authentication for that matter. We cannot say that the two systems are equivalent, as concerns the public channel, until we have more information about the procedure—i.e., protocol—used to mitigate man-in-the-middle attacks. The distinction between the two systems is necessary because the KLJN uses the public channel in fundamentally different ways than does QKD. My primary concern is that the method used to detect and prevent man-in-the-middle attacks—measurement of instantaneous voltage and current amplitudes—generates more overhead than can be authenticated without completely exhausting the key stream. I shall elucidate further:
To make use of WCA a randomly generated key must be used for each authentication tag that is to accompany a piece of data one wishes to authenticate. These keys are included in the previous stream of secure data. If the the number of keys necessary to authenticate data on the public channel is greater than the total secure data stream then the system is not sustainable, as it will eventually run out keys to authenticate public channel data with.
In so far as I can tell, the KLJN system, in order to mitigate man-in-the-middle attacks, is sending instantaneous current and amplitude data in real time. Let us calculate the number of bits that must be authenticated per one bit transmitted. Assuming 50% of the bits transmitted are secure, let us denote the total number of bits transmitted on the secure channel as B, where the number of secure bits is B/2. If we assume that the instantaneous voltage and current measurements are done with a sample frequency FS, with bit resolution R, for the duration D of a bit transmission on secure channel, we arrive at the total number of bits, TB, to be authenticated as (here we have ignored all other overhead in the channel, and assumed that no bits have been lost in transit.):
TB = 4*FS*R*D+B; the 4 comes from the fact that each side must authenticate two measurement streams.
If we set D = B/V, where V is the transmission rate of the secure channel. Assuming the Nyquist signaling rate, we have V = 2*FC, where FC is the channel bandwidth set out in the original paper:
TB = B*(2*FS*R/FC + 1)
I believe in the paper describing MITM attacks, you set R=7 and FS=10*FC, please correct me if I am wrong, which leads to:
TB = 141*B
or 282 bits per secure bit transmitted that must be authenticated. Certainly, more than one bit is necessary to authenticate these bits, and thus the system ends up consuming more keys per stream than it can generate.
As the system stands now, in the way that I have described it, unconditionally secure authentication is not possible—it is with QKD. Perhaps the system can be modified, and the overhead connected with each bit transmission will be of little consequence (maybe not comparing current and voltage data in real time, but at the end of a secure transmission session will solve the problem?), but it has not been shown that the system can make use of unconditionally secure authentication, WCA or otherwise. Until this can be shown, we cannot accept the system as any more secure than our present classical methods.
As far as my statement concerning the ultimate security of the KLJN: the system can never be more secure than its weakest link. To ensure the overall security of the system the public channel must be secure, by which I mean authenticated. This goes for all systems, including QKD.
I look forward to seeing your future work on an authentication framework for the KLJN. Thank you for your time Dr. Kish.
I am rather worried about the idea of putting low pass filters beside the resistors. A low pass filter is a shunt to ground for high frequencies, i.e. a capacitor in the simplest form. Now, I suppose actually the noise source is a resistor across the input to a linear amplifier, so to filter out high frequencies, we would place a capacitor parallel to the resistor on the input side and the linear amplifier output could be applied directly to the wire. (There has to be some small resistance between the amplifier output and the wire since the amplifier is a voltage source that would try to oppose any additional voltages applied there).
Now, for this scheme to work, the RMS noise observed on the wire (from two amplifiers at opposite ends) is supposed to be equal to the RMS noise which would arise from one amplifier with the resistors in parallel at its input. This can happen only if the electric fields are allowed to interfere _before_ being squared and averaged (and rooted).
(The situation very much reminds me of the two-slit which-way experiment, where interference disappears when it is possible to know which slit a particle passed through. I suspect the similarity is not a coincidence, but this remark is completely beside the point of my question, and I can't exhibit exactly how the situations are parallel, except that when interference is observed, the probability amplitudes are added before being squared, while when interference is not observed, the amplitudes are squared first -- so we can know which way the particle went -- and then added.)
The RMS voltage measured on the output of a single linear amplifier with the two resistors (and a capacitor) in parallel across its input will not equal the RMS voltage measured on the wire with amplifiers at each end, unless the voltage fluctuations output by the two amplifiers are allowed to interfere before being averaged. But for this to happen, the wire must be acting like a transmission line. If the complete waveform is observed at many points along the wire, it will be different at each point. The RMS voltage will be about the same at each point, but the detailed waveform will be different. Given enough of these waveforms, it should be easy to calculate the waveforms being output by the two amplifiers, and the RMS voltage at the output of each amplifier (before the series resistor), and hence to deduce the values of the resistors on the inputs of each amplifier
(as pointed out earlier on this blog by at least one other person).
Any proposed countermeasures which prevent the appearance of any voltage fluctuations on the wire also prevent the interference of the voltages before squaring. Actually, I guess they prevent the appearance of any voltage at all since the net current has to be zero. You can't get net current zero with nonzero voltage unless the voltage fluctuates.
Using amplified noise sources, detecting high-input-impedence A/D converters connected at intervals along the transmission line, between the wire and ground would be difficult. Using unamplified passive resistors makes the scheme difficult to realize in practice.
Or have I missed something?
Ryan M. Gerdes,
Thanks a lot; very interesting considerations. These kinds of considerations are very important for the practical realization whenever it will come.
You say, the problem is the large overhead, 282 authenticated bit for each secure bit. Yes, indeed, it seems, the one-bit security and the natural defense against the man-in-the-middle attack certainly has a price, if the "authenticated bit" fashion is to follow.
Using the same example, the required authenticated but number could be reduced however, one has to give up then the zero-bit security. For example, comparing only the currents would be factor of 2 and that would result in one bit security. Tricks may be developed with less time resolution, using the time-integral of the current, which would be an analog version of the digital parity checks, etc. That would shrink teh need by a factor of 10, so we would be at 14 bits. Is that overhead still too much?
You are right, the data can be sent later and then the unsecure bits can be filtered out, however that would still slow down the system.
Have you studied how much overhead does the protection against the man-in-the-middle attack in quantum?
I do not understand your problem. Using LC low-pass line filters is easy. They do not change anything within the allowed frequency band of working. However, they remove all the higher frequency components (transients, eavesdropping probe signals, etc.)
If still in doubt, please send me a drawing about your problems via email, or publish them on a public website where we can discuss it.
I'm not concerned about LC low-pass filters. I'm concerned that it seems to be necessary to filter out all but DC in order to defeat Eve, if Eve uses high impedence voltage sensors attached at several points along the wire. But if you filter all but DC, the scheme doesn't work. However, now that I write it out in detail, I think it does work -- you don't need to filter out all but DC -- and the others concerned about transmission line effects should look at this analysis.
You seem to be assuming that Eve will use a spectrum analyzer, but so far as I can see, measuring the voltage at a high sampling frequency is a stronger attack. I don't see any need to measure current at all. If Alice and Bob use many different resistances, I guess Eve would need to measure current. With just two resistances, Eve only needs to know voltages at several different points along the wire.
Alice and Bob probably need to measure current in order to detect various active evesdropping attacks, but I'm looking at the strictly passive high impedence tap method (which I think you would agree does work if the low-pass filters are left out).
If need be I will create a drawing from the following description, but perhaps a description will be adequate:
f(t) is the random noise from R1 (volts), after being filtered with lowpass filter.
g(t) is the random noise from R2 (volts) after lowpass filter.
w(t,d) is the voltage measured at time t and distance d from left end of wire (where f(t) is applied).
At left end of wire, a voltage source matching f(t) is connected to the wire through a small resistor (with negligible additional noise). The voltage is f(t) before the resistor, but is f(t)+g(t-d) after the resistor (see below).
At right end of wire, voltage source matching g(t) is connected through a small resistor. Again the voltage is g(t) before the resistor, but is f(t-d)+g(t) after the resistor.
Both voltage sources are connected to common ground (a second wire or the coax shield).
The signal f(t) appears (as an unmeasurable part of the superposition) at the right end of the wire delayed by time d. The length of the wire is L, and the speed of light in the wire is L/d.
At the center of the wire, the signal is
w(t,L/2) = f(t-d/2)+g(t-d/2).
At left end, the signal is
w(t,0) = f(t)+g(t-d).
At right end, the signal is
w(t,L) = f(t-d)+g(t).
Importantly, nowhere on the wire is the signal simply f(t) or g(t). Eve cannot obtain these signals because they exist only inside the securely sealed boxes operated by Alice and Bob.
Alice measures <w(t,0)>, the RMS voltage at the left end. Bob measures <w(t,L)>, the RMS voltage at the right end. (These would be nearly equal and can be published). Together with knowledge of their own resistor settings, Alice and Bob can calculate the opposite setting.
The RMS voltage is directly proportional to the sum of the two resistances, so the one measurement plus the known resistance gives the other resistance. (Right? With only two resistance values, I don't see the need to measure current except to detect active attacks. I could be wrong.)
Ok, now maybe I begin to see how this might work. There is only a finite time (the clock period) before the resistances are changed and Eve doesn't get any more data regarding that bit of the message. I think Eve's problem is that d is small enough that there is never a very big difference between the two ends of the wire.
The electric fields do get to interfere (superimpose): we never see f(t) and g(t) on the wire, only f(t)+g(t-d), etc, and f(t) and g(t) change slowly compared to d. The clock period has to be much longer than d so that the RMS voltage is averaged over a long enough time to make it directly proportional to the total resistance. And it has to be short enough that Eve cannot get enough data to figure out f(t) and g(t).
So I see that indeed there is no "wave in the wire". f(t) and g(t) will frequently have different signs, and will switch signs during a clock period, but they change slowly enough that f(t)+g(t-d) is always very close to f(t-d)+g(t), and the difference between the two ends of the wire will not attain statistical significance during a clock period.
My mistake was thinking that the low pass filter (which ensures that f(t) and g(t) do not change much in time d) would somehow cause Alice to measure <f(t)> + <g(t-d)> instead of <f(t)+g(t-d)>. Clearly it doesn't.
Yes. It is essential that the Kirchhoff loop does not contain any wave components and that is guaranteed by Eq (9) in the first paper. As soon as Eq (9) is violated, the applied Kirchhoff loop model is invalid and there is an information leak. Eq. (9) is the ultimate bandwidth limitation. The ultimate bandwidth scales with the reciprocal of the distance. However, in practical applications, due to the finite amount of money available for the cable, the cable resistance and cable capacitance may pose stronger constraints, for longer distances. Note: with sufficiently thick cables they would not pose any limitation; this is why their limit is not "ultimate", only "practical". My calculations with wires available on the market show that the cable capacitance is the more crucial bandwidth limitation issue. These parasite effects cause the bandwidth to scale with the square of the reciprocal of the distance for ranges over 100km, or shorter, depending on the cable. This is still much better than the exponential bandwidth cut-off of quantum, however it is an indication of the need of repeaters for very long distances.
How can you detect an attack in which Eve increases the cable capacitance by attaching capacitors at several places along the cable? Or if Eve introduces delay lines into the cable? I don't doubt each attack can be countered, but how can you be sure you have thought of all of them?
Fortunately, each of these would make the current alarms go on because the instantaneous balance would be violated. In the case of delay line, not only the current but also the voltage alarm would go on.
But generally, you are right: for any secure communication system, one has to be prepared that the enemy may find out some new trick. Nothing has worked against the KLJN cipher yet, however, some ideas may emerge. Then it is up to the people to find out the defense.
If you check the arxiv.org site for such aspects of quantum communication, you will see that there is a large number of papers/manuscripts dealing with breaking into different quantum ciphers. There is a wide range of clever ideas. A practical system should be defended against all those. I doubt that practical and laboratory quantum communicators are defended against all those attacks because real eavesdroppers against quantum communication do not exist yet.
Finally read your paper fully and carefully. Interesting. One question:
On p.8 sec 5 you recognize the need for a settling time proportional to L to allow the impacts of sender and receiver resistor switchovers to propagate fully.
On p.5 assertion (ii), however, your supporting analysis seemed to me -- and I could well be misreading this -- to focus on the operating state that emerges after the impacts of the sender and receiver resistor switchovers have fully propagated across the line.
If that is wrong, please steer me the right way. If that is correct -- that is, that p.5 (ii) assumes a settled operating state -- then my question is this: Where in your paper do you address the security of the dynamic phase between switching resistors and the final unbreakable state? For example, is that part of your analysis somehow implied in the particulars of how your senders and receivers use thermal noise as part of your 3-way encryption?
This question is good and was asked also by some statistical physicists in different ways and they were worried about transitions between different equilibrium states. First of all: the states are the same equilibrium states but the realization is different. The (equivalent) temperatures of the old and new resistors are the same. There is no macroscopic transient or net energy flow. There are many answers and all conclude that this transient does not provide information. The simplest but killing answer is that the single transient is equivalent to a single sample from a random noise, even if it is from the change between two noises. Because the evaluation of the loop needs to make a statistics on the noise, you have zero information. To get even the smallest amount of information (and I think even that would not be enough), you should repeat the very same switching cycle by a large number of times and make a statistics on the switching transient. A single sample does not provide information because the noises are random and their sign and amplitude is not only arbitrary but the two sides determine it. But if the transients would ever make any problems, the line filters take care of that. Moreover, it is possible to use such noise generator arrangement and timing that there is no transient. That would be a bit more complex solution however it is not needed.
It is with some distress that I have, as of yesterday, switched from being someone about to post a blistering critique of Kish's proposal to someone who had a not-entirely-pleasant "aha!" moment about it.
It is now my public statement, speaking only for myself, that as best I can tell Kish's proposal works at least as well in the engineering limit as quantum proposals to accomplish very similar goals.
My intent until yesterday had been to post a white paper on my personal web site that would detail a set of unavoidable requirements for creating an effective classical analog to quantum cryptography systems. I was then going to go on and show why Kish's methods would necessarily fail. My specific point of assumed failure was in how Kish created his classical analog of a superposed state, which, as Bruce Schneier described in his first article on Kish's methods, is pivotal to how it works.
The reason why it is very difficult to create a secure classical analog of a quantum superposed state is that you cannot easily combine the two (or more) contributing states without giving away critically important information in the process. In quantum cryptography that is not a problem, since there you can use either minimal numbers of quanta or entanglement to guarantee in the engineering limit that any attempt to probe the contributing states will be detected. In classical analogs of this, the issue of hiding the contributing states becomes much harder because data transmission by definition is not quantized and therefore highly redundant. That means that in a classical system there is almost always some way to skim off enough redundant information to eavesdrop without giving away your presence.
It seemed airtight. Kish's contributions to his pivotally important classical analog of a superposed state had to travel over ordinary wires, and so should have been visible to a sufficiently sophisticated eavesdropper. In particular, taps on multiple points of the line should have been able to pick up ramp-up or ramp-down transients that would have pointed to whether Alice or Bob was initiating a particular contribution. That not only would have blown apart Kish's method, it would have done so in a way that would have made it less than useless by increasing the time available to eavesdrop on each bit.
What finally clicked for me was a thought experiment designed to stress Kish's method in a controlled fashion. I postulated a very, very long wire, roughly one light-minute (at 3/4 c) in length, or about 300 wraps around the globe. I also added an unusually sophisticated switch for the resistor pairs of Kish's method, mostly to help make certain parameters and issues more explicit. This hypothetical switch guarantees very smooth switchovers, but more importantly it allows the time needed to ramp from one resistor value to another to be set explicitly to any desired length of time.
I then plugged Eve in with taps at the start, middle, and end of the very long line, and looked at what would happen. I was honestly shocked when I finally realized that even with this long of a line, the combination of the modified white noise spectrum provided by the Johnson-noise amplifiers plus the use of a sufficiently long ramp-time setting should be enough to make it arbitrarily difficult for Eve to detect the critical giveaway differences in the voltage/amperage profiles she sees, even on the taps that are a full light-minute apart! I sent an inquiry directly to Dr Kish about this thought experiment, and he indicated (in keeping with my own ballpark suspicion) that setting the ramp-time per bit to about 10 minutes should do the trick. While a data rate of 6 bits per hour is not exactly what you want for downloading from the Internet, it is actually pretty impressive for transferring secure bits over such hypothetically astronomical wire length.
I will capture this an more in a white paper I've been working on. I’m modifying it now to include my own attempt to explain Kish's methods in ways that avoid any mention of thermodynamics. I'll try to post the paper on my personal web site, hopefully by next week, and will put up a notice on this thread when I do so.
And my final comment is: wow.
--speaking only for myself--
The Johnson-like-noise based (KLJN) crypto system is network-ready, see the manuscript in its (almost) final form at: http://arxiv.org/abs/physics/0603041
In the case of a chain-like network with N units, an N-bit long secret key is generated and securely distributed over the whole network promptly, in two KLJN-clock periods, provided the helper regular network is fast enough. It is done by the whole-network telecloning (teleportation without terminating the source bit) of the classical bit. The noise-based method can do this with 100% fidelity.
Why the wire resistance is a minor problem. Protection by the time-inaccuracy uncertainty principle of stochastic statistics. See Figure 2 and the text in this new manuscript:
In the attached manuscript
a different optical (and microwave) scheme is shown which is unconditionally secure in the idealised and steady-state case, dislike the Giant Fiber Laser communicator. However, because at practical applications no scheme is totally secure, the laser system may become more important. In the last section of the manuscript, some critical comments about the Giant Fiber Laser method are presented. So far, the wire based communicator, which is based on Kirchhoff loop and Johnson-like noise, is superior to any of these optical methods. However that does need a wire. On the other hand, currently used wires can also be used, such as power lines, phone lines, etc., see this manuscript:
P.S.: See all these and more at:
The Johnson-line noise based secure communicator has been built and it has been tested up to the range of 200 km which is well beyond the direct quantum communication range. Its raw-bit security level is set so that it is beyond the theoretical security of practical quantum communicators. Here are the pictures of the first communicator and network element and the first draft:
More data will follow in the paper.
I still do not see how this can be secure. Why shouldn't it be possible to discern the noise which is injected from one side from the noise which is injected from the other side by measuring at two points along the wire?
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.