Kish’s “totally secure” system is insecure

October 8th, 2006 at 20:10 UTC by Feng Hao

Recently, Kish proposed a “totally secure communication system” that uses only resistors, wires and Johnson noise. His paper—“Totally Secure Classical Communication Utilizing Johnson (-like) Noise and Kirchoff’s Law”—was published on Physics Letters (March 2006).

The above paper had been featured in Science magazine (Vol. 309), reported in News articles (Wired news, Physorg.com) and discussed in several weblogs (Schneier on security, Slashdot). The initial sensation created was that Quantum communication could now be replaced by a much cheaper means. But not quite so …

This paper—to appear in IEE Information Security—shows that the design of Kish’s system is fundamentally flawed. The theoretical model, which underpins Kish’s system, implicitly assumes thermal equilibrium throughout the communication channel. This assumption, however, is invalid in real communication systems.

Kish used a single symbol ‘T’ to denote the channel temperature throughout his analysis. This, however, disregards the fact that any real communication system has to span a distance and endure different conditions. A slight temperature difference between the two communicating ends will lead to security failure—allowing an eavesdropper to uncover the secret bits easily (more details are in the paper).

As a countermeasure, it might be possible to adjust the temperature difference at two ends to be as small as possible—for example, by using external thermal noise generators. However, this gives no security guarantee. Instead of requiring a fast computer, an eavesdropper now merely needs a voltage meter that is more accurate than the equipments used by Alice and Bob.

In addition, the transmission line must maintain the same temperature (and noise bandwidth) as the two ends to ensure “thermal equilibrium”, which is clearly impossible. Kish avoids this problem by assuming zero resistance on the transmission line in his paper. Since the problem with the finite resistance on the transmission line had been reported before, I will not discuss it further here.

To sum up, the mistake in Kish’s paper is that the author wrongly grafted assumptions from one subject into another. In circuit analysis, it is common practice to assume the same room temperate and ignore wire resistance in order to simplify the calculation; the resultant discrepancy is usually well within the tolerable range. However, the design of a secure communication is very different, as a tiny discrepancy could severely compromise the system security. Basing security upon invalid assumptions is a fundamental flaw in the design of Kish’s system.

Entry filed under: Hardware & signals

24 comments Add your own

  • 1. Clive Robinson  |  October 10th, 2006 at 10:35 UTC

    When I first read about Kirsh’s system I fairly instantly had my doubts due to the way a signal (takes time) to propergate down a transmission line (see my post on Schneier on security). I also assumed at the time (being a comms engineer) that either Kirsh had forgoton that all transmission lines have antenuation and therefore you could turn the transmission line into one arm of a measuring bridge. Or more importantly he had found some way to address it that he had not yet published (as it would have fairly major repucusions for the comms industry and physics).

    At the time I said “I’m going to put my neck out and say it’s Snake oil and not very pure at that.”

    Thankfully the Scheuer and Yariv “How Secure” paper came along with,

    “When the analysis is carried out taking into account
    the, inevitable, time delay and the resulting transients,
    or the impedance of the wire, we find that the system
    becomes vulnerable to eavesdropping, thus invalidating
    the basic premise of “[Kish]

    and it’s attendent clasical analysyis, saved not just my neck but my education as well ;)

    The whole Kish debate reminded me of the ones raised around Ivor Catt’s views in the 1980′S, shortly after I had entered industry (Heaviside Signal and Catt’s Anomaly). Which took over ten years to settle down. So likewise I have been waiting patiently for the dust to settle on the Kish debate ;)

    I look forward to reading your paper later today (the PDF does not open on the Linux boxes around here so time to find a Windoze box).

  • 2. Clive Robinson  |  October 10th, 2006 at 10:39 UTC

    Sorry I appear to have made a formatting error, never trust your own eyes with small type :(

    The two links above should have been,

    Heaviside Signal = http://forum.physorg.com/index.php?showtopic=4554
    Catt’s Anomaly = http://www.ivorcatt.co.uk/6_6.htm

  • 3. Laszlo Kish  |  October 28th, 2006 at 22:29 UTC

    Feng Hao, thanks for the information about the comment paper however it is flawed. It indicates that the commenter simply has not read my paper. It was pointed out that “thermal like” noise has to be used not thermal noise (unless for stealth communication which is irrelevant here) an that means that hardware noise generators with much greater (1 million times or more) noise voltage as thermal noise can be used. Thus the temperature of the system is simply irrelevant; therefore the comment paper is flawed.

    Note: even the title of teh very first paper says “Johnson like” noise.

    There is more development: optical realization, implementation over power lines, and secure network implementations here:
    http://www.ece.tamu.edu/%7Enoise/research_files/research_secure.htm

    If you want me to see your response, please send a copy to my email address because I infrequently read blogs.

    Good luck,
    Laszlo Kish

  • 4. Feng Hao  |  October 29th, 2006 at 22:33 UTC

    Hello Laszlo,

    The problem with the proposed system is that the underlying assumptions are invalid, hence it gives no security guarantee. If you believe by adding the word “-(like)”, those assumptions become valid now and can stand up to any theoretical or practical challenge, it’s better to make that explicit in your threat model.

  • 5. Laszlo Kish  |  October 30th, 2006 at 00:40 UTC

    Feng Hao,

    You should execute a thorough analytic study before saying general comments. The proposed system is absolutely secure in the mathematical/idealized limit. The problem with your comment article and Scheuer/Yariv’s one is that you change the original system. The changed system is of course not unconditionally secure. You are right that practical systems are never equal with that idealized mathematical system which shows the total security. However, the original idealized/mathematical system is unconditionally secure and it is very difficult to find such idealized systems. I do not any other suich system at the moment. For example, no one of the quantum schemes is unconditionally secure because the inherent noise coming form the detection scheme makes a few % bit leak possible without discovering the eavesdropper.

    On the other hand, if an idealized system is absolutely secure, such as this, the engineering design is able to approach that infinitely depending on resources and requirements. It is very easy to go beyond quantum security.

    See more about all these aspects in my response to Scheuer-Yariv. The paper can be downloaded from Physics Letters A, and it comes out in the early December issue. Here is the preprint:

    http://arxiv.org/abs/physics/0605013

    Therefore the proper argumentation at your side would have been to say that in the practice parasite/nonideal elements compromise security. Some of them is significant some of the not. But your one is insignificant. I am writing a large paper about the design/running aspects of the cipher and I will deal with your comments there.

    Finally, if you want to argue from a practical point of view, which is your only valid condition because the ideal system is absolutely secure, using thermal noise is completely unpractical, as it was said already in the very first paper. In practical system you must use enhanced noise therefore your comments are irrelevant even for the practical case.

    So far, there is no real challenge against the cipher. But I hope somebody will come up with some serious/significant idea eventually so there will finally be some excitation:-)

    We will soon demonstrate all these aspects with a real system via a communication range of 1000 km.

    Good luck,
    Laszlo Kish

  • 6. Feng Hao  |  October 30th, 2006 at 10:09 UTC

    If one wishes to assume absolutely no friction in this world, he may come up with a sensational design, and hence claim a breakthrough. I’ve no doubt of that.

    If you think the comment paper challenges the practicality of the proposed system, you haven’t got the point of the paper. The comments you have made so far are not unexpected.

  • 7. Laszlo Kish  |  October 30th, 2006 at 13:40 UTC

    Feng Hao,

    I am very glad that finally you at least admit that the mathematical/idealized scheme is totally secure.

    Concerning practical security, the problem of inaccuracies and other type of non-idealities, see the issue of statistics. The eavesdropper has not enough time to build a sufficient statistics. If we suppose 1% inaccuracy (such as inaccuracy of voltage noise strength, which you call temperature, inaccuracy of resistor values, inaccuracy due to voltage drop in the wire, etc), which can be a practical goal, then the eavesdropper would need 10,000 times longer measurement to reach the same good statistics as Alice and Bob. But the eavesdropper has the same short time (clock time) as Alice and Bob.

    This issue was briefly mentioned already in the very first paper and a relevant aspect was later analyzed in the paper about the protection against the man-in-the-middle-attack:

    http://arxiv.org/abs/physics/0512177

    Finally in the response to Scheuer-Yariv, an explicit analysis was given for 1% inaccuracy, see the last figures. That figure is exactly relevant for your inaccuracy claim supposing that the inaccuracy is 1% :

    http://arxiv.org/abs/physics/0605013

    The eavesdropper is in a hopeless situation and the upper limit of bit leak due to this 1% inaccuracy is better then that of idealized quantum schemes.

    As you see, real world aspects are also analyzed but you simply missed to read the papers carefully enough. I recommend that we continue this discussion after you have carefully studied these aspects.

    Good luck,
    Laszlo Kish

  • 8. Feng Hao  |  October 30th, 2006 at 14:49 UTC

    >> Feng Hao,
    >> I am very glad that finally you at least admit that the
    >> mathematical/idealized scheme is totally secure.

    That’s not what I meant.

  • 9. Gabriel Chime  |  October 30th, 2006 at 17:31 UTC

    Dr.Hao,
    If I understand your paper correctly, the main point is that if one uses Johnson noise then an eavesdropper can exploit temperature differences.

    On the other hand, Dr. Kish’ point is that one would never use Johnson noise in a practical design.

    I THINK YOU’RE BOTH RIGHT.

    Dr. Kish’ idealized scheme appears to be as good as the corresponding one based on quantum communication.

    Any practical implementation of either idea will differ from the simplified theory.

    A practical system doesn’t have to be 100% secure, just secure enough so that the probability of breaking the code is very small.

    Time will tell which system is easier to implement. I am not a gambling man, but at this point I would bet on Dr. Kish’s scheme.

    In the meantime, Dr. Hao and Dr. Kish, please tone down the language a bit, there is no reason to be rude:)

    Sincerely,
    Gabe Chime

  • 10. Clive Robinson  |  November 3rd, 2006 at 14:42 UTC

    @Laszlo

    I am still a little confused about the system. In a lot of your comments you say there is no transfer of energy between the two endpoints, and that it is a clasical system.

    As far as I was aware back in the 1960’s it was established by a researcher (I cannot recall his name at the moment) at IBM, that all information processing required a minimal but calculable use of energy for each bit of information.

    Likewise a LC lowpass filter does nothing unless energy is transfered from one energy storage component to another withinit, therefore information cannot pass through it unless energy is transfered.

    You also talk about a signal voltage without explaining if you are refering to a PD across an infinate resistance (open circuit) or an EMF across a finite resistance or energy storage component.

    If the later then it is acting as a force and is constrained by the speed of light then the information cannot be transfered instantly. Likewise it involves the transfer of charge which involves the movment of electrons.

    Can you clarify things a bit?

  • 11. Laszlo Kish  |  November 3rd, 2006 at 15:45 UTC

    Clive,

    If I understand it correctly, there are three separate issues in your note:

    1. Energy transfer between Alice and Bob. This has to be made more accurate by saying *net* energy transfer.

    2. Energy requirement of communicating a bit.

    3. Propagation velocity of information in the wire.

    Please let me know if I miss something. The answers are below. The conditions are supposed ideal.

    1. The net energy transfer, the net power flow, between Alice and Bob must be zero (or if it is not, it must be the same net power flow at all situations). Therefore the choice of the strength of voltage noise generators versus resistance must follow the same type of scaling as with thermal noise except the voltage should be much stronger (million times and beyond) at practical application. That means, the effective voltage must be proportional with the square-root of the resistance at a given bandwidth and the factor of proportionality must be the same at Alice and Bob. This factor of proportionality and the two resistor values are public information.

    In this case, the net power flow between Alice and Bob is zero in any situation. The instantaneous power flow is not zero however the net (average) power flow is zero. It is important to note that that there is no information in the instantaneous values. The information is in the average.

    2. The minimal energy requirement, which is the energy dissipation, during the communicating of a bit is controversial; Landauer said it is approaching zero, Porod says it is at least kT*ln(2) or more; and I believe in the last claim. In a specific system, “thermal noise driven computing” (a computer, its clock and its logics driven by thermal noise) it comes out 1.1 kT/bit, see more at http://arxiv.org/abs/physics/0607007

    In any case, the limit is in the order of kT/bit (or less according Landauer’s claim) and that is an extremely small value. Imagine a practical Johnson-like noise communicator with resistors in the order of 1000 Ohm and noise voltage of 10 Volts. In the case of a line of 1 km length, we would have a few kBit/sec speed. That means that the energy dissipation for a transferred bit is somewhere in the 10-100 microJoule range. Let us take the lower value. That is 2.5*10^15 kT energy. That is, in this communication, the energy dissipated to exchange a single bit is more then 15 orders of magnitude (million*billion times) greater than the lower limit posed by statistical physics.

    In conclusion: the cipher does dissipate a huge energy. However, the net energy flow between Alice and Bob is zero over infinite time. They are heating the resistor of the other however this cross-heating is the same in both direction. For real thermal noise, the fluctuation-dissipation theorem of statistical physics guarantees this and it excludes the possibility of building a perpetual motion machine driven by thermal noise in thermal equilibrium.

    3. Propagation speed of information. That is not faster than the light velocity but it is very much slower. (Note: in the practical case, the finite velocity of voltage propagation is the reason why the bandwidth must be limited to avoid wave effects in the wire and this is the reason why low-pass line filters must be used in a practical arrangement to maintain security, see http://arxiv.org/pdf/physics/0605013 ).

    The propagation speed of the instantaneous voltage in the line is already less than the velocity of light. However there is no real information in the instantaneous voltage amplitude. The information will be in its statistics, in the average of its square. To make that statistics with sufficient accuracy the required sampling time will slow down the “propagation” of that information by about a factor of 10. Thus we do not have any problem with Einstein’s speed limit.

    It seems there is a lot of misunderstanding about this information provided by the noise voltage. This information is by no means secret! Eve will also extract it thus it is a public information. The real secret bit will be extracted from the combination of this public information and from the local bit (resistor) value of Alice and Bob.

    Regards,
    Laszlo

  • 12. Clive Robinson  |  November 4th, 2006 at 21:38 UTC

    Laszlo,

    Thanks for the info I shall have a contemplative chew on it over the rest of the weekend and try to biuld a visual model in my head (yup I’m a graphical not a formula thinker :(

    Regards,

    Clive

  • 13. Laszlo Kish  |  December 6th, 2006 at 05:20 UTC

    The response to Feng Hao’s comments is accepted for publication in Fluctuation and Noise Letters and it is coming out in the December/2006 issue (hard copy and web edition). The preprint can be seen here:

    http://www.ece.tamu.edu/%7Enoise/C29_Kish_preprint.pdf

    Laszlo Kish

  • 14. Feng Hao  |  December 6th, 2006 at 16:32 UTC

    Laszlo,

    After reading your response, I really don’t want to explain further on this, but can only (strongly) suggest you to submit your paper to a recognized SECURITY journal or conference.

    Good luck
    Feng

  • 15. Laszlo Kish  |  December 9th, 2006 at 10:51 UTC

    Feng,

    I am on a trip, so briefly. It is better to keep the discussion at the scientific level. However, because you say that, here is the situation.

    The IEE journal where your comment paper comes out does not even have an impact factor! Thus, using your terms, it is not yet a “recognized journal”. Therefore, because the editor did not allow me to publish a response following directly your comment, I decided to publish at FNL which has an impact factor and is abstracted in SCI.

    Good luck,
    Laszlo Kish

  • 16. Feng Hao  |  December 9th, 2006 at 13:26 UTC

    You misunderstood me. I suggested you to submit your paper to a journal specializing in Security/Cryptography, so that you will get feedbacks on whether security experts in the field agree with you. And I am sure Fluctuation and Noise Letters is not a journal on security .

    The reviewing process in IEE Information Security is rigorous. If your paper was rejected, there must be a reason for that. If you still insist your design is indeed “totally secure” and my critiques are irrelevant, I have nothing more to say.

    With that, I hope our argument ends here. Let readers decide.

  • 17. Laszlo Kish  |  December 12th, 2006 at 15:29 UTC

    Feng,

    You misunderstood me, too.

    1. I have never submitted any paper to IEE Information Security; I only asked for the opportunity to write up a response directly following your paper. But IEE Information Security refused this initiative by saying that such practice is not a common practice in the field. Note: Physical Review Letters, Applied Physics Letters, Physics Letters, and other leading journals I know always allow and even arrange a response directly following a comment.

    2. Because the debate is about noise, random fluctuations and information in physical systems, the journal Fluctuation and Noise Letters (FNL) is actually a much more relevant forum to discuss this communicator than IEE Information Security. On top of that, the non-existent impact factor of IEE Information Security and the existing impact factor of FNL is another very important fact. However, I still offered them the possibility that I write up my answer for them provided it can directly follow your paper, just like well established journals arrange that. But IEE Information Security refused this offer thus I wrote up my response for FNL. It comes out in the December hard copy issue of FNL and it will also be published in the web edition of the December issue.

    But I agree with your final statement: Let the Reader decide!

    Laszlo Kish

  • 18. Laszlo Kish  |  January 6th, 2007 at 05:08 UTC

    RELEVANT NEWS:

    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 range of direct quantum communication. Its raw-bit security level is set so that it is beyond the theoretical security level of practical quantum communicators. Here are the pictures and the first draft of a paper: http://www.ece.tamu.edu/~noise/research_files/research_secure.htm

    More data will follow in the manuscript later. Arbitrary breaking attempts can eventually be tested and characterized. The device is designed to have a security level well beyond the theoretical security of quantum communicators.

    Laszlo Kish

  • 19. David Honig  |  May 30th, 2007 at 19:44 UTC

    Won’t an adversary be able to do time-domain reflectometry
    to see the differering impedences at the ends of the
    conductor?

    This resistor scheme is, in a sense, linear; quantum schemes
    exploit the nonlinear nature (of quantum collapse) to detect
    adversaries.

    This resistor scheme is clever in that there’s no “first order” difference for the adversary to monitor, but there are
    more “higher order” analog tricks to play, to distinguish
    bigR-wire-smallR from its mirror image.

  • 20. Morlock Elloi  |  June 2nd, 2007 at 21:38 UTC

    The system essentially functions by modifying an observable via undetectable modification channel, and the observable itself is ‘linear’ to the point where multiple modifications give cumulative effect on the observable without the ability to distingush the components.

    It’s like two households feeding an alley cat. It gets skinny, just right, or fat.

    Most objections question either the supposed undetectability of the modification channel or undistinguishability of “sum’s”components.

    But the really interesting question is, are other systems that satisfy the above possible without using messy electrons in the wire? Something faster than the alley cat, of course.

  • 21. Peter Glaskowsky  |  June 15th, 2007 at 06:51 UTC

    Oh, I see David Honig already said what I wanted to say, but I’ll say it myself anyway– time-domain reflectometry breaks this system. It requires what Dr. Hao said to begin with– the attacker must have more sensitive measuring equipment than the users of the system– but that is always a given in security analysis.

    This is a clever idea, but it only works in an ideal world. In the real world, it is insecure, more difficult to implement than traditional digital cryptography, and it’s less capable as well because it won’t work over the hundreds of billions of dollars of existing switched digital network infrastructure.

    . png

  • 22. Andrew Raybould  |  June 16th, 2007 at 15:38 UTC

    Do the low-pass filters at both ends of the line (mentioned above) defeat time-domain reflectometry?

  • 23. Laszlo Kish  |  October 25th, 2007 at 14:45 UTC

    Dear All,

    Sorry for the late response but I have not followed the development of the discussions on the web (must focus on other projects). For the moment, the KJLN secure communicator project is in idle mode because the experimental realization and testing were completed (with success) last April. Two review papers are awaiting completion with theoretical and design issues. The test results are reported in a Physics Letters article which is in press (maybe came out already in print). You can read the manuscript in press, as item number 7, at:

    http://www.ece.tamu.edu/%7Enoise/research_files/research_secure.htm

    The experimental network unit prototype was tested with parameters in the range 2km – 2000km. All the existing breaking ideas were tested. The Fen Hao breaking method was also tested using the fact that the effective temperature (much beyond 1 billion Kelvin) of the noise generators could be set with only 12 bit effective accuracy (even though the DA converters had 14 bit accuracy). But even this 12 bit accuracy was enough to secure that during the test runs of 75000 bit, zero effective bits could be eavesdropped with the Hao method. The theoretical info leak with the Hao method at this accuracy is less than 6 bits in 1 billion communicated bit. However, there is no theoretical limit of increasing the noise accuracy, only practical (financial) and the present one looks secure enough if we consider quantum communicator parameters as standard. With the given practical parameters, Feng Hao’s attack was the weakest “information leak” type attack among the tested ones. If the communicator would have utilized the thermal noise of resistors (stealth communication), then Hao’s attack would be of practical significance and it would yield further constraints on temperature stabilization and further limits of the wire resistance. However, stealth communication is probably rarely needed therefore the current system rund with enhanced “thermal-like” noise with noise-temperature much beyond 1 billon Kelvin. The strongest proposed attack was the Bergou-Scheuer-Yariv (BSchY) type attack based on wire resistance at economically selected wire diameters and it resulted 0.19% information leak. This is still about 5-10 times better than typical quantum communicator information leak of raw bits. Moreover, this value inversely scales with the 6-th power of the wire diameter thus doubling the wire diameter yields 64 times less leak.

    There is one more difference between the information leak of the KLJN and quantum communicators. At quantum information leak, we know the location of the extracted bit with a high accuracy. Up to know, the attacks posed on the KLJN communicator either ignite the alarm within the clock period of the bit in question, thus no secure information is extracted, or if there is a leak without alarm, the exact location of the correctly guessed bits (beyond the noise) is largely unknown. This is a further gain in practical security compared quantum communicators.

    It is important to emphasize that all these successful attack types, including Hao’s attack, are practical issues due to the non-ideality of the practical system. The system is theoretically totally secure at the math model level. However, in reality, neither this system nor quantum communicators are totally secure because real systems can only approach the clean conditions math models assume but never exactly reach them. Therefore, ideas, like Hao’s attack and the BSchY attack are very important because before widespread installation of such communicators they must pass all the existing attack types. That means, the information leak must stay below certain commonly accepted limits.

    Reflectometry and any other breaking idea based on propagation times, they have been considered and excluded by the appropriate selection of low bandwidths (no-wave-limit), already in the very first paper. Andrew Raybould rightly points out the role of line filters. This is the only reason why the communicator must be so slow and this is why its speed is inversely proportional to the range.

    Because I rarely have time to search for web discussions, if you have a question or idea which you published in a web blog, please ask me also directly, then I can surely respond: Laszlokish@tamu.edu

    Thanks,
    Laszlo Kish

  • 24. Persuasive Instigator  |  October 29th, 2012 at 04:22 UTC

    Hey Feng Hao,

    Laszlo Kish proved your assumptions wrong. He said that the temperature doesn’t matter because you can scale it to a million times higher than the actual real temperature and still have the noise fluctuations.

    What’s your response to this? Come on, don’t give up, fight back.

    PI

Leave a Comment

Required

Required, hidden

Some HTML allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Subscribe to the comments via RSS Feed


Calendar

October 2006
M T W T F S S
« Sep   Nov »
 1
2345678
9101112131415
16171819202122
23242526272829
3031