Non-quantum key generation?


Here’s a paper to avoid: http://arxiv.org/abs/1206.2534 .  I saw it reported in Technology Review at http://www.technologyreview.com/view/428202/quantum-cryptography-outperformed-by-classical/ .

The paper is:

Information theoretic security by the laws of classical physics, R. Mingesz, L.B. Kish, Z. Gingl, C.G. Granqvist, H. Wen ,F. Peper, T. Eubanks , G. Schmera, presented at the 5th IEEE workshop on soft computing applications, 2012.

The context is that you have two people, Alice and Bob, who want to communicate.  You have an attacker, Eve, in between who is trying to figure out what they are sending back and forth.  (This is the standard cryptographic cast of characters.)

The idea is that you have a wire between Alice and Bob, and Alice sends her bits by switching between two resistors.   Because of the thermal agitation of the electrons in the resistors, a resistor  generates electrical noise, in addition to its more normally understood function of converting electrical energy to heat.  [One can prove that these are inseperable: anything that can potentially dissipate electrical power into heat will also generate noise.  It’s called the fluctuation-dissipation theorem.]  So, as Alice switches from one resistor to another, she puts different amounts of voltage noise on the wire.   Here’s the schematic drawing of the circuit:

 

So far, so good.  Now, the claim in the paper is that the listener in the middle (Eve) cannot tell whether Alice or just Bob switched resistors, so Eve cannot tell a real bit (Alice’s) from a fake bit (Bob’s).  However Bob can.  He knows what his switch is set to, so he can subtract off the amount of noise that his resistor generates from the total.  The remainder is, of course, the noise from Alice’s resistor.   So, Bob can read what Alice is doing, and Eve can’t.

But, don’t think of this as a communication system!  It isn’t.  It is (to the extent it is real) a way for two people to generate a random key that they both share.   Let me say that again: nobody is sending information yet: the intent is for Alice and Bob to get a random number from the thermal fluctuations of the system in such a way that Eve (in the middle) cannot get the same number.  Once they have a shared key, then A&B can set up a secure comunication system that uses normal cryptography.

Here’s why it’s not a communication system: Suppose that Alice an Bob have one High value resistor and one Low.  Obviously, if both ends are Low, then the noise voltage is very low, and Eve can tell what Alice is sending.   So, it’s only transitions between (L,H) and (H,L) that can confuse Eve.     Alice and Bob need to synchronize their switches precisely, and they would need to arrange some clever protocol where the message is encoded in the presence or absence of such transitions.  And, the protocol would have to be designed not to leak information via (H,H) or (L,L) switch settings.

According to the paper: “At each clock period, Alice and Bob randomly choose one of the resistors and connect it to the wire line. The situation LH or HL represents secure bit exchange [31], because Eve cannot distinguish between them through measurements, while LL and HH are insecure.” But, if A&B randomly, independently, choose either H or L, then half of Alice’s choices will be immediately obvious to Eve: all those insecure (L,L) and (H, H) choices.  It would be a very leaky communications channel.   While it is true that Eve cannot (in the idealized system) see a (H, L) to (L, H) transition, there’s no way for Alice to safely send an H-to-L transition because she doesn’t know what Bob is going to do.  [The only way she could know what Bob’s action was going to be would be if she had some other secure communication link with Bob…]

So, Alice and Bob each do their random switching.  They ignore all the (L, L) and (H, H) pairs, and they generate the key from only the (H, L) and (L, H) pairs.    Essentially, they key has a 1-bit for (L, H) and a 0-bit for (H, L).  They key accumulates in fits and starts, and they stop whenever they have enough bits.

So, that’s how it works.  It works nicely in an ideal system, with a very short wire and perfectly simultaneous switching by Alice and Bob.  The question though, is whether in a real system, with a longer wire and imperfect components, whether Eve could learn some of the bits of the key, and if so, how many.

The argument that one can find on the web is mostly about physics.    The protocol requires simultaneous switching, and relativity tells us that you cannot define simultaneuity between two different places.   [And if the ends aren’t in different places, it’s not much help in setting up a communication link.]  The problem is that the electrical effects sweep from one end of the wire to the other, and that depending on where Eve sits, she will see either Alice’s or Bob’s switch happen first [ 1 ].  The authors actually have a good answer to that problem:  they slowly change the resistance values.  If the resistors change slowly enough, and if A&B filter the electrical signals so they only let low-frequency waves out onto the wire, then this particular leak becomes small.

There are also issues with imperfect wires.   For instance, if the wire from Alice to Bob has some resistance, Eve can look at the two ends, measure the difference, and deduce who has H and who has L.  The authors respond by having both Alice and Bob broadcast their voltage measurements to each other so they can look for discrepancies that might be caused by Eve.  But that kind of approach can be vulnerable to a man-in-the-middle attack on the “broadcast” channel between A and B.  It’s also a recipe for a measurement arms race between Eve and A&B.  If Eve has a better voltmeter than A&B, she can suck some information out of the wire without Alice and Bob ever being quite sure that they are being tapped.  [And what do Alice and Bob do during a thunderstorm?  If lightning strikes nearby and induces just a little extra current on the wire, do Alice and Bob assume the wire is compromised?   Do they dig the wire out of the ground, inspect it, and lay a new one?]

Other authors have pointed out other problems.  If the temperature of the two ends differs, some information leaks out [ 1 ].

A lot of noise and effort seems to be wasted over squabbles about how many bits get leaked if Eve is a non-interfering listener.  That seems counterproductive.   Clearly some bits leak to Eve, but equally clearly, it seems possible to design a system where the leak rate is small. [To be useless against this kind of attack, the system would have to leak lots of bits to Eve.  As long as Alice and Bob share some information that Eve doesn’t, they should still be able to communicate securely.  For instance, if I have a 256-bit key that is completely secure, an attacker could brute-force it by trying all 2**256 keys.  It would take an astronomically large amount of time and effort but it’s possible in principle.   If 10% of the bits leaked to Eve, she would only need to try 2**230 or so brute-force attempts before she could read Alice’s messages.   While that reduces Eve’s effort by a factor of a billion or so, it would still take an astronomically large amount of work before she could read their message.]

But the bigger issue is the man-in-the-middle attack.  Cut the wire and put a black box in the middle.   On Alice’s side, the box pretends to be Bob, on Bob’s side, it pretends to be Alice.  There doesn’t seem to be any tamper-proof way to detect such an attack.   The paper suggests that you have a separate “broadcast” channel to let Alice and Bob compare notes, but that channel could be subject to a man-in-the-middle attack also.

Even without a man-in-the-middle attack on the broadcast channel, it might be possible to put a black box in the middle of the wire.  All it needs is electronics that has lower noise than Alice’s or Bob’s, and it can simulate the voltages and currents precisely enough so that the endpoints won’t notice.  [One can imagine the attacker using expensive, liquid-helium-cooled amplifiers so that their noise is much lower than room-temperature Johnson noise.]

However, from a theoretical point of view, once the paper suggested a separate “broadcast” channel as a way of avoiding a man-in-the-middle attack, it was an admission of failure.  It means the overall system can only be secure if the other channel is secure.   And that means that this system isn’t any better than normal cryptography.  It might still be interesting, because most of the cryptography we use every day is imperfect, but it’s not the quantum leap that the authors advertise.

Oh well.

Now, if Kish and collaborators want to keep pushing their ideas, it’s up to them to point out an engineering use case where their system is less vulnerable than a conventional system of equal cost.   That is, if they want to protect their wire, the conventional system gets to protect its optical fiber.