Move Over, Quantum Cryptography: Classical Physics Can Be Unbreakable Too

MrSeb writes "Researchers from Texas A&M University claim to have pioneered unbreakable cryptography based on the laws of thermodynamics; classical physics, rather than quantum. In theory, quantum crypto (based on the laws of quantum mechanics) can guarantee the complete secrecy of transmitted messages: To spy upon a quantum-encrypted message would irrevocably change the content of the message, thus making the messages unbreakable. In practice, though, while the communication of the quantum-encrypted messages is secure, the machines on either end of the link can never be guaranteed to be flawless. According to Laszlo Kish and his team from Texas A&M, however, there is a way to build a completely secure end-to-end system — but instead of using quantum mechanics, you have to use classical physics: the second law of thermodynamics, to be exact. Kish's system is made up of a wire (the communication channel), and two resistors on each end (one representing binary 0, the other binary 1). Attached to the wire is a power source that has been treated with Johnson-Nyquist noise (thermal noise). Johnson noise is often the basis for creating random numbers with computer hardware."

Kish again?

[Dwonis]

I remember when this was posted on Slashdot 7 years ago [slashdot.org].

unbreakable been around for a while

[Anonymous Coward]

Claude Shannon proved in the 1940's that the Vernam cipher with a key the same size as the message, aka one time pad, has perfect security. The USA built the world first digital audio system [wikipedia.org] during WWII in order to give such perfect security to voice communications between Roosevelt and Churchill, among others.

The fundamental idea

[JoshuaZ]

The basic idea of the key exchange is a variant of an older key exchange idea. The very basic idea involves Alice and Bob having a wire that goes between them. Each of the two has two resistors one with very low resistance and one with high resistance. To gain a series of random bits, Alice and Bob both randomly choose a resistor and connect it to the wire and then measure the resistance through the whole system. If they both used the high or both used the low resistance resistors they throw out those exchanges. Whenever they have one medium and one high, they will both know which one had a low and which one had a high because they'll know their own. But Eve the evil eavesdropper even if she has a connection into the line won't be able to get this just from knowing the total resistance. In some weak respects this resembles a physical analog of the Diffie-Hellman http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange [wikipedia.org]. The process being proposed here though, a Kish key exchange http://en.wikipedia.org/wiki/Kish_cypher [wikipedia.org] does some clever stuff with the thermodynamics end to deal with man-in-the-middle and other related attacks.

Re:Still breakable

[PatDev]

Tampering detection is all that is required for perfect security. The trick is that you do not transmit the message itself over this channel, you instead transmit a random stream of bits. Once both sides share a random stream of bits that they know has not been overheard, they can use that random stream as the key to a one-time-pad that can be transmitted over any traditional eavesdrop-able channel. You could just email the ciphertext over the public internet, since you know that you have an (unknown to any attacker) shared secret key, you have perfect secrecy.

Re:Still breakable

[PatDev]

The resistor stuff solves an orthogonal problem to OTP. OTP gives you perfect secrecy when you share an unknown secret key with the other party you are communicating with. This "resistor stuff" is how you get an unknown shared secret key with the other party. OTP still requires key distribution, which is what this does. The two are complementary, neither replaces the other.

Re:Still breakable

[Baloroth]

No, you can't. There is nothing to "brute force": the current and voltage is essentially random. You can't brute-force that for the same reason you can't brute-force a one-time pad: there is nothing to brute-force. Also, while I'm not sure, I don't think Alice needs to know the current and voltage: it looks to me like only Bob does (Alice attaches a resistor with the resistance she wants, Bob does so randomly, Bob compares the current he sees with what it was originally minus the resistor he attached: only Bob needs to know the original current). The only way to decrypt the data stream is if you know what resistor either side attached, and you can't do that without adding energy to the system, which Bob will notice (Alice too if she knows what the current was originally, but that would mean Alice and Bob already have a shared randomness, which means they don't need any tricks to encode a message: they can just use that randomness as a one-time pad).

Re:Still breakable

[sjames]

Knowing V and I don't help you because you don't know how much of the R that resulted in I given V was from Alice's end and how much from Bob's. Only they know that.

Re:unbreakable been around for a while

[bh_doc]

Funnily enough, "quantum key distribution" is what it's actually generally referred to in the field.

Re:Still breakable

[swillden]

If you can decrypt something that means there is a method to do so. You pass the message and one-time pad into this "function" and receive output.

Yes, but how do you know when the output is correct?

This is why an OTP provides perfect secrecy, if the key is secret. For a given ciphertext, there is some key that transforms it into every possible plaintext of the right length. This means that the result of brute force searching the keyspace for an n-bit ciphertext is every possible n-bit message. Thus, the only information you can get out of an OTP-encrypted message is the message length -- assuming it wasn't padded. With padding, the only information you can get is the maximum length.

The same problem actually occurs with "normal" ciphers and short messages. If I use AES to encrypt a one-bit message (perhaps padding the rest of the block with random bits), every possible AES key will result in an apparently-valid decryption -- the first bit will be either 0 or 1. But I have no way to tell which is right, even though I know that 2^128-1 of them are wrong. Claude Shannon defined the concept of the "unicity distance" to describe this, "unicity distance" being, basically, the length of the smallest amount of ciphertext which an attacker with infinite resources needs in order to determine the correct key, by examining resulting plaintexts. With an OTP, the unicity distance is infinite because as the message grows so dos the key, without bound.

Assuming the key is secret... which is the hard part with one-time pad protocols.

Re:Still breakable

[harlows_monkeys]

IMHO, the fallacy in the claim of unbreakable one-time pad encryption is the reliance that all computed plain-texts for the key space are equally possible to be the correct plain-text for the cipher text.

Imagine you are being that exists beyond time and space and can experience all possibilities at the same time. I would think that all possible computed plain-texts would mostly look a huge pile of crap, but an exceedingly few amount are going to look like something you recognize, and then one of them will look like an Apple.

Once again, that does not mean one-time pads are not very secure. They are very secure, just not truly unbreakable.

No, a one time pad with a true random key is truly unbreakable.

What you've overlooked is that when your hypothetical Godlike being sees all possible computed plain texts, that consists of every possible message of the length of the cipher text.

Note that what the Godlike being sees when he tries all possible decryptions does not depend on what the message is (other than the length). Thus, he gets absolutely no information from the cipher text (other than the length).

Try thinking about it with a small example and that should help you see it. For instance, do a 3 bit message. We've got 8 possible messages: 000, 001, 010, 011, 100, 101, 110, and 111. Let's say you know that only 001, 010, and 100 make any sense. Alice sends to Bob the encrypted message 110.

When your Godlike being considers all possible decryptions, he gets 000, 001, 010, 011, 100, 101, 110, and 111, depending on whether the key was 110, 111, 100, 101, 010, 011, 000, or 001.

So he looks at these, and picks out 001, 010, and 100 as the only meaningful messages. Now what? He has no idea which is the right message.

Now perhaps he knows that some of the meaningful messages are more likely than others. Maybe he knows that 99% of the time, Alice sends 010. So he will probably be right if he guesses that this message was 010.

However, he'd have had exactly the same chance of being right if he had guessed 010 without even looking at Alice's message!