The Reality-Based Community

 Fun and games with codes

Simon Singh says at the end of his entertaining history of codebreaking
that the battle between codemakers and codebreakers is over and the codemakers have won (Sorry, I've lost my copy and you can't search inside the book on Amazon, but I'm pretty sure). In 1949 Claude Shannon, the founder of information theory, proved that the one-time pad developed between 1917 and 1923 was unbreakable by cryptanalysis.
Since then, the problem has been key distribution. It was the re-use of one-time pads by the KGB that allowed the laborious Venona decrypts of some of their contact reports.

In 1984 a theoretically perfect solution for key distribution arrived in the black magic of quantum cryptography.

In this scheme, Alice transmits to Bob, over an insecure channel, a stream of photons with some randomly set property like polarisation in a quantum superposition that collapses on detection. Using additional information transmitted openly, Bob can reconstruct Alice's settings, and so they can both use this knowledge to make an unbreakable one-time key. If the eavesdropper Charlie intercepts the stream, his detection itself causes the collapse, which Bob can identify using the additional information. You (assuming you are a rich, paranoid corporation) can already buy devices that use this scheme. QED.

Laszlo Kish of Texas A&M University, with Hungarian colleagues back in Szeged, has invented an elegant variant (see here and here) that uses comprehensible classical physics and components anyone can buy at Radio Shack. Alice and Bob now each just have two resistors, high and low, connected to a copper phone line whose noise varies with the total resistance. They switch their resistors randomly but simultaneously between high and low, and note the settings plus the noise level in the wire. They discard the settings when they chose the same value and the noise was high or low, and keep only the settings when the noise was medium, and the settings therefore different. Bob can infer Alice's settings, so they can simultaneously build a one-time key out of them, but Charlie cannot - there's no current and he can't identify which end of the line had which resistor.

Bruce Schneier points to a rebuttal claiming the Kish code can't be quite as beautifully secure as an ideal quantum scheme. I'll take Bollinger's word for it, but it's an unfair comparison. A real quantum device has its own weaknesses. For example, in the ideal device Alice only sends one photon with one setting. If she sends more, the eavesdropper Charlie can peek at one and leave the others undisturbed.

Anyway Schneier, a real expert, says: so what?

..they're solutions looking for a problem. In the realm of security, encryption is the one thing we already do pretty well. Focusing on encryption is like sticking a tall stake in the ground and hoping the enemy runs right into it, instead of building a wide wall.

I'm not so sure. Solving the encryption problem has effects. Cryptographic security for the citizen has a downside, as Big Brother shifts to other means. Phil Zimmermann. the creator of the freeware public-key encryption package Pretty Good Privacy, wrote already in 1994 in the documentation for an early version:

A physical security breach may allow someone to physically acquire your plaintext files or printed messages. A determined opponent might accomplish this through burglary, trash-picking, unreasonable search and seizure, or bribery, blackmail or infiltration of your staff... Don't be lulled into a false sense of security just because you have a cryptographic tool. ....This kind of attack is cheaper than cryptanalytic attacks on PGP.

If Ahmed sends Boujama (time to vary the name conventions a little) a cryptographically secure message, Charlie, or his successor Porter, and their bosses Dick and George, don't have to give up. They can and do go much further than Zimmermann's Nixon-era fears: they can kidnap Ahmed, fly him to a secret prison, and waterboard him until he reveals the message.

Al-Qaeda, from the fragmentary information in the public domain, doesn't in fact seem to rely on advanced cryptography; this training manual, if authentic, suggests that they are using ciphers that were obsolete in the time of Louis XIV. (The Bolsheviks too used poor ciphers that the Okhrana read with ease, for all the good that did.) But aware of their technical inferiority, and vulnerability to surveillance and traffic analysis, they do seem to protect their secrets another way, by relying on face-to-face briefings for important operational orders.

The price of signals security may include a contribution to the rise of torture.