More on Kish's Encryption Scheme

Back in 2005, I wrote about Laszlo Kish’s encryption scheme, which promises the security of quantum encryption using thermal noise. I found, and continue to find, the research fascinating—although I don’t have the electrical engineering expertise to know whether or not it’s secure.

There have been developments. Kish has a new paper that not only describes a physical demonstration of the scheme, but also addresses many of the criticisms of his earlier work. And Feng Hao has a new paper that claims the scheme is totally insecure.

Again, I don’t have the EE background to know who’s right. But this is exactly the sort of back-and-forth I want to see.

Tags: , ,

Posted on June 11, 2007 at 6:49 AM • 29 Comments

Comments

Clive Robinson • June 11, 2007 7:31 AM

Oopps forgot to say about the link,

However it does not mention a new paper by Feng.

Greg • June 11, 2007 8:19 AM

This is interesting.

However I think we need more effort put into how to desgin good protocols etc.

Crypto is the easy part I think. Hashes need work, but modern cyphers are rarely the weak link nowdays and neither is the public key systems (With the exption of timing attacks or other side channel attacks esp for smart cards).

The bits i find really hard are the details of the protocol incuding key revocation and distrabution (public key distrabution is not a simple matter in pratice). The next hardest thing is dam patents.

In fact I would say that ECC would be widespread by now if it wasn’t for the patent issue.

Woo • June 11, 2007 8:32 AM

I’ve read through your summary and the paper a few times now, and I can’t see the groundbreaking principle.
The main concept is a transmission of no(identical)/yes(different) states without anyone being able to eavesdrop reliably.
There still needs to be some data transmitted – or generated at both ends. Fact with thermal noise in resistors is: You can’t manufacture two resistors with exactly the same noise pattern. So, generating the data on both ends simultaneously is impossible. Using thermal noise to generate data on one end would require this data to be transmitted to the other end, to be kept or discarded depending on the high/low resistor game, or quantum states, or whatever method desired.
So, the only usable method would be to supply both sides with an identical bitstream, and then use this resistor “handshake” to determine which bits to use and which not.
The key derived/transmitted over such methods would still have to be used with traditional encryption concepts, with all their flaws. Not to mention that you still need the infrastructure for this key-transmission concept.

X the Unknown • June 11, 2007 9:26 AM

@Woo: “Fact with thermal noise in resistors is: You can’t manufacture two resistors with exactly the same noise pattern.”

At least in Bruce’s first summary, it doesn’t use thermal noise at all (except maybe off-line, as a random-number generator to help choose which resistor to use for a given bit). It’s simply a binary-choice of two different-valued resistors, throwing away matches.

However, a related problem exists: The actual resistance of the resistors owned by Alice have to be very close matches to those owned by Bob (well within the temperature-based variance), or an attacker can discern the difference:

10.1 ohms + 99.8 oms
is not equal to
101 ohms + 10.2 ohms

Anonymous • June 11, 2007 10:24 AM

Kish states that he has already explained why the system he proposes withstands attacks such as resistor value mismatch. However, he has done a poor job of doing it in a manner that gives him credibility before security people. His vitriolic attacks on Feng Hao did not help his credibility either.

RC • June 11, 2007 12:07 PM

It is possible that scientists will discover a way to tell who has the 10-ohm resistor and who has the 1000-ohm resistor. Perhaps tapping the wire at each of two places, at different distances from each of the resistors, will yield data that can be used to break the system.

Clive Robinson • June 11, 2007 12:18 PM

@Anonymous

It is not just Feng Hao who has been on the recieving end of a fairly heated debate.

However cryptography is one of the few areas of research where heated debate is accepted as part of the process of moving the body of knowledge forward (provided the attacks are not personal and on topic). I suspect that this came as a bit of a schock to Laszlo Kish where his field of endever is a lot more sedate in comparison.

@All

That aside there are still many unknowns within the system that have not been yet adequately explained (atleast to me and by the sounds of it several others 8)

However if the system works it will have a great number of advantages over the current generation of quantum cryptographic systems (and not just from the cost point of view, think ease of switching for instance).

I am still unconvinced for a number of reasons one of which is the fact that transfering information requires a force. Which involves not just energy but direction and propagation.

Kish says,

“the net energy flow between Alice and Bob is zero over infinite time”

and,

“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).”

However saying that the net transfer of energy is zero does not mean that it is zero at any given point in time or as Kish puts it,

“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. ”

The fact that this also involves a wave propagating down the transmission line at considerably less than the speed of light just makes me nervous.

It’s the fact that there are just to many potential hooks for an attacker to hang their hat on that gets to me, nothing definate (this may in part be due to the fact that I have not been able to build a model in my mind that I find acceptable).

One analogy to the system I have heard from sombody trying to understand it is,

“that it is like the inverse of a direct sequence spread spectrum system.”

That is the spreading code which is normaly kept secret is the Kish generated thermal like noise and is public.

Or in Kish’s words,

“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 secret data is transfered simply because this “thermal like” signal randomly passes backwards and forwards between the two endpoints.

It is encoded in the statistics or in Kish’s words,

“It is important to note that that there is no information in the instantaneous values. The information is in the average.”

Which is kind of like saying I will pass a ten million gallons of water back and forwards between Alice and Bob’s swiming pools. However on average 1 pint of difference will be seen by Bob…

It is the next bit where all the hand waving starts,

As Bob and Alice know the state of their switches they effectivly perform a comparison between the statistics of the expected thermal equilibrium (switches in same state) and the actual equilibrium. The difference indicates that the switch at the other end is not in the same state (hence a bit of data is transfered). Now Eve not knowing the state of either of the switches has no reference to work against so can not tell…

Hmm this is the bit that we all want to understand 8)

junky • June 11, 2007 3:44 PM

“this is exactly the sort of back-and-forth I want to see….”

how about “ooh..aah..yes..yess… oh-yes baby…” 😉

Filias Cupio • June 11, 2007 5:03 PM

I’m also worried about propagation times. There might be a way around this: if the measurement of the bit is statistical in nature (i.e. as time goes on, we get more information about the setting of the bit until eventually we deterimine it with high confidence) and if the propagation delay is very short compared to the length of time we need to determine the bit, then there is very little information to be had by comparing evesdropped measurements from each end of the cable.

You might be able to go from having zero information (50% chance the bit is 1) to (say) 50.02% chance the bit is a 1. I don’t think this would significantly damage a well designed cryptographic system. At best, you could brute-force it a little bit faster: e.g. breaking a 1024 bit key in the time it would normally take to break a 1020 bit key.

Sparky • June 12, 2007 2:46 AM

I was thinking the same thing as Clive Robinson (and several others); I think eavesdropping would be possible (i would dare to say, it wouldn’t be very difficult for an decent electrical engineer), when the attacker has access to two or more points on the transmission line.

This would allow a wave-propagation analysis, which can determine the direction of flow of the different waves, to figure out which originated for Alice and which from Bob. It would be possible to just record high speed pulse code modulated signals (much like a .wav audio file), and do the actual analysis off line.

Just another thought: there is a rather large difference in the values of the resistors used. This means that at least half the time, there is a huge impedance mismatch at the ends of the wire, which causes a reflection of the signal. In this case, the attacker would only need a single eavesdropping point, because any signal send would bounce back and forth between Alice and Bob, gradually deceasing in strength because of the line resistance. The attacker could analyze the initial direction of propagation, and thus the origin of the signal, but the amplitude of the reflection would depend on the impedance mismatch, and therefore on the resistor chosen at that end of the line.

Finally, I have some serious doubts about the routability of the signal. It would require a really old POTS (Plain Old Telephone System) like router, which uses relay contacts to physically connect the two subscribers lines. The problem is that this system will have to allow for resistance, impedance and resulting noise from aging and dirty relay contacts. Relay contacts (especially dry ones, not mercury wetted) tend to act as low-pass filters; they seriously attenuate high frequency signals, and have a rather nasty non-linear frequency response.

(this comment has grown a bit longer than i expected. I am technically not an electrical engineer, I studied computers sciences)

Sparky • June 12, 2007 3:10 AM

Maybe I wasn’t quite clear. What I meant to say about the reflection because of the impedance mismatch, is that there are at least 2 different ways to use this physical phenomenon to attack the channel.

The first is to determine the direction of propagation of a given wave by doing a timing analysis. When the signal is first transmitted on the line, the attacker would record it, but not know where it originated from. A short time later, the attacker would see the reflection of this signal, and could, at this point, calculate the time delay between the signal and it’s reflection. Assuming the attacker is not at or very near the middle of the wire, he could tell the difference between the two participants.

The attacker could also measure the amplitude (strength, in volts) of the reflection, which is determined by the impedance mismatch.

In layman’s terms, an impedance mismatch is a difference in resistance between the wire itself and the end of the wire. If the wire is open at the end, the end resistance is infinite. To properly terminate a wire in a communication system (for example, a RS485 bus), a resistor of the correct value needs to be place across the wires. If this is not done properly, a part of the signal is reflected. It’s a bit like a wave in water encountering a blockage with a small opening; some of the wave gets through the opening, and some of it is reflected.

I hope this clarified my thoughts a little, especially for those who are not familiar with the theories of data communication.
I’m surprised that no-one has brought this up (as far as I know).

bob • June 12, 2007 7:08 AM

Couldnt you increase the data transfer rate by having larger sets of resistor pairs? 5, 10, 50, 100, (…pattern…) 50M, 100M would give you 4 times as much data per element, reduce the occurence of “null” elements (when both sides picked scissors) and make decoding more difficult for the eavesdropper. Granted it still requires pairs of matched resistor pairs and a much more discriminating detector at each end.

CJ • June 12, 2007 7:47 AM

Re: Sparky at 2:46 and 3:10

He restricts operation to very low frequencies—so wave propagation doesn’t really occur. He inserts a low-pass filter before the resistors, so you can’t probe the impedances with higher frequencies.

I think measuring at widely separated points and later comparing the measurements has a lot of promise.

Generally,
this system seems impractical, at least for longer distances. I seem to recall (i looked at the paper a few days ago) that it suggested use of a 22 mm diameter wire for transmission of a key over a distance of 2,000 km.

My ROM estimate is that the copper in such a cable would cost hundreds of thousands of dollars.

Clive Robinson • June 12, 2007 10:36 AM

@CJ

“My ROM estimate is that the copper in such a cable would cost hundreds of thousands of dollars.”

Not one hundred % sure on this, Kish does not give a reason why he has the values he does only that it varies by XXX.

At one time he talkes about coax cables is he refering to the inner or outer conductor, has he taken the skin effect into account (which should be negligable at low frequencies) it is difficult to tell as there is not enough detail in the paper on many things…

Anonymous • June 12, 2007 10:46 AM

Interesting:

‘”The way the eavesdropper gets discovered is that both the sender and the receiver are continuously measuring the current and voltage and comparing the data,” Kish said. “If the current and/or voltage values are different at the two sides, at any moment, that means that the eavesdropper has possibly broken the code of a single bit. Thus the communication has to be terminated immediately.’

So this scheme is vulnerable to the same type of MITM attack as quantum cryptography. I can’t see it catching on…

Giga • June 12, 2007 11:46 AM

I have the EE background, and a lot of things bother me about Kish’s scheme, including some of the points already raised here. (Some of the other points are invalid, and show the poster hasn’t read the papers.)

One point is that Alice and Bob have to switch their resistors in or out of the circuit simultaneously. How do they coordinate this, except by using an untrusted channel? Even GPS (a very accurate public access time signal) has skew. Or do Alice and Bob have personal atomic clocks, thus raising the cost? Skew in switching resistors momentarily transmits what the old choice of resistor was, so logic lets Eve deduce what the new choice of resistor is

Also, it seems almost trivial to mount a DoS attack that would force Alice and Bob to use a different mechanism, or force them to not communicate at all. It could be a real DoS or it could be a gopher chewing on the cable. Or specially trained NSA gophers.

Finally, the 2 Kish papers I read both omit the computer network over which Alice and Bob exchange other information. What about side-channel attacks on that network, such as sending fake messages or inverting actual messages? That other network is a pivotal part of the overall system, because it’s how Alice and Bob exchange information about what was sent over the “encrypted” resistor circuit. Each heterogenous choice made on the resistor circuit has a corresponding public message with voltage and current readings, and a datum that basically tells the recipient that the received bit is either the resistor value chosen, or its logical inverse. If the public network is trustworthy, or the messages on it are authenticated, then why bother with the resistor circuit at all? If the public network or its messages are untrustworthy, then Alice or Bob can’t trust what those messages say about the resistor circuit. Catch-22?

Even with such questions, I think the research is worth doing, on the whole. But I also think the system is worth attacking, at various points in the system, and not just attacking the strongest theoretical part.

Archimerged • June 12, 2007 1:12 PM

Regarding cost of the 2000 km 21mm diameter copper cable, gnu units calculates:

‘(2 US$/pound) (pi/4) 21mm 21mm 2000 km 8.96 gm/cm^3’

27.4 million US$

Archimerged • June 12, 2007 1:43 PM

Cost of the copper is just an interesting calculation. Right of way would cost much more.

Re: security of public channel. Presumably, this scheme is a way of increasing the value of already shared secret keys. Suppose the public channel is authenticated using a secure digital signature system, while the private channel is used to exchange session keys. I presume that a properly designed digital signature would give extremely high resistance to key leakage, so that a shared signature key could be used to exchange millions of session keys before the most paranoid users would feel the need to change signature keys.

Re: DOS. How is this copper channel more vulnerable than any other land line? How can a wireless system ever be theoretically completely secure?

a different bob • June 12, 2007 6:44 PM

@Archimerged:
“Presumably, this scheme is a way of increasing the value of already shared secret keys.”

No, it’s a key-generation scheme. Alice and Bob cooperate to generate secret keys, which they both know, but which Eve can’t observe without being detected.

Archimerged • June 12, 2007 9:06 PM

But they need to share a secret key in order to authenticate the public communications. Otherwise Eve can alter the content of the public line. This sort of system is supposed to not depend on public key cryptography, which is presumed insecure due to quantum computation. (Quantum cryptography was supposed to be the antidote to quantum computers).

Ale • June 13, 2007 5:56 AM

@a different bob:

I completely disagree. I have never read Kish address any concerns about the actual data network over which data transfer takes place. As with Bennett/Brassard, it can be realistically used only for key exchange – thus intercept/replay attacks are possible in the data network. I am with Giga on that one.

X the Unknown • June 13, 2007 9:57 AM

@Giga : “… Alice and Bob have to switch their resistors in or out of the circuit simultaneously…”

Couldn’t they both disconnect the circuit (an on/off switch between the resistor and the communications-wire) before changing resistors? (Or does the scheme require continuous connection?)

Because with both disconnecting, there should be no “circuit” until both have reconnected (with their new resistors in place).

Archimerged • June 14, 2007 4:31 AM

@a different bob

I think the confusion comes from paper[1], in which Kish writes “For example, after a whole random sequence is sent, it is possible to announce through a public channel which secure bits forms the message and what is their proper order.”

I now have 0508135, 0509097, 0509136, 0610014, and 0612153 but I haven’t read them in great detail. Which paper describes encryption which does not require a public channel? Or is a key agreed on simply by taking the resistor value at the sender end when the two resistors are opposite? It does seem like that would work, and that Kish ought to stick to that application instead of getting more complicated.

[1] L.B. Kish, “Totally secure classical communication utilizing Johnson (-like) noise and Kirchoff’s law”, Physics Letters A 352 (2006) 178-182; also at http://arxiv.org/physics/0509136.

Archimerged • June 14, 2007 4:44 AM

In paper[2], Kish writes “However, when the eavesdropper is using noise current generators, though the cipher is protected, the eavesdropper may still be able to extract one bit of information while she is discovered. For enhanced security, we expand the KLJN cipher with the comparison of the instantaneous voltages via the public channel.”

This requires an authenticated public channel. In that case, a shared secret would be required to authenticate the public chanel, AFAIK.

[2]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; also at http://arxiv.org/physics/0512177.

Andy • June 14, 2007 11:13 PM

With regard to the questions about switching: in the ‘2K demo’ paper, Kish refers to ramping the signal up before, and down after, a measurement, to avoid transients.

I, too, have wondered about measurements taken at two or more points, exploiting the propagation delay. Is there any way, by comparing the actual waveforms, timeshifted by the delay between the points, to determine which end is contributing most to the total signal – or does it echo back and forth enough to obscure its origin?

Andy • June 16, 2007 11:46 AM

Scratch my comment on two measuring points: there are low-pass filters at both ends of the line, and all changes (resistance-switching) are made slowly, over a period much longer than the time taken for signals to propagate the length of the line. If I understand correctly, this means that, at any given time, the voltage and current are the same at all points on the line, so no propagating change is observable.

As for Alice and Bob’s comparison of measurements, this doesn’t have to be done secretly (an eavesdropper already has access to these values), but it does have to be secure from being altered by the eavesdropper. I suppose this could be done over multiple channels, making it harder for the man-in-the-middle to cover his tracks… is this good enough?

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.