Modern Codebreaking

Interesting piece from the BBC about modern codebreaking in an era of essentially unbreakable codes, hooked to the Chalabi scandal regarding U.S. breaking of Iranian codes. Some excerpts:

Simon Singh, author of "The Code Book", a history of codes, said: "Modern codes are effectively unbreakable, very cheap and widely available. I could send an email today and all the world's secret services using all the computers in the world would not be able to break it. The code maker definitely has a huge advantage over the codebreaker."
…….
Ross Anderson of the Computer Laboratory at Cambridge University [says]: "As the former chief scientist of the NSA once remarked at one of our security workshops, almost all breaks of cipher systems are due to implementation errors, operational failures, burglary, blackmail and bribery. As for cryptanalysis, it happens, but very much less often than most people think."
……
The three "Bs" - burglary, blackmail and bribery - might have to be employed if there is no other way of getting at the key. We are back to the world of spies.
…..
Simon Singh says that sometimes there is a backdoor way in through deliberately corrupted software: "There is always the chance of human error. Encryption requires a key, and if I get hold of your key then I can read your messages. Or if I plant some software in I get to see the message before you encrypt it." Whether something similar happened in this case involving Iran is simply not known.

Lots of neat details on the distinctions between private-private and public-private keys, the difficulty of factoring the product of multiplied prime numbers, and other such codemaking fun, and worth reading in full if the topic interests you at all.

Comments

[arthur]

Actually, factoring prime numbers is very easy, since the only factors are 1 and the number.

[linked article gerts the point correctly]

[Mr. Nice Guy]

kpr od s fomh-fpmh

[Brian Doherty]

Math boner corrected, thanks Arthur.

[Jason Ligon]

I read somewhere last week that we have built the first quantum encrypted network. Nifty stuff.

David Friedman talked a bit about a world where cameras are so small you don't have privacy anywhere outside, but encryption schemes are so good you have near perfect privacy online. A draft of his new book "Future Imperfect" is webbed here, and there is a section outlining his points on privacy (see Privacy X3 in the intro for an overview).

http://patrifriedman.com/prose-others/fi/commented/Future_Imperfect.html

[CodeMonkeySteve]

I scoff -- *all* ciphers are crackable, if by no other method than brute force (i.e. trying every possible key). The idea is to use a large enough key that the time required to break it would be prohibitive (i.e. hundreds of years). But with faster computers (and the NSA has *acres* of them), the time can be reduced to weeks, perhaps days.

Quantum cryptography doesn't really help anything: it's just a secure method of key exchange. The actual data is still encrypted using a standard cipher and passed over an unsecure network. Quantum computing will be far more useful in breaking ciphers then quantum cryptography can be in securing them.

Pretty much the only way to improve privacy and security of communication is to use hard crypto for *everything* (even -- especially! -- spam), hiding the sensitive communication amongs billions of mundane communications, and requiring the NSA to crack all of it.

[JDM]

"Quantum computing will be far more useful in breaking ciphers then quantum cryptography can be in securing them."

Except that Quantum computing is an absurd pipe dream, whereas Quantum cryptography can ensure the exchange of a secure key.

[thoreau]

Quantum computing will never happen on a practical scale as long as the "killer app" is the Shor algorithm. The Shor algorithm is great for breaking classical codes, since it can factor very large numbers in polynomial time. But it's useless against quantum cryptography. And quantum cryptography is easier to implement than the Shor algorithm.

[R C Dean]

Its like you people are talking in code, or something.

[CodeMonkeySteve]

"Quantum cryptography can ensure the exchange of a secure key."

Key distribution is not the issue -- asymetric crypto (i.e. public-private) pretty much solved that problem. Quantum key exchange improves things slightly by making it hard (perhaps impossible) to snoop the key, but it does nothing to make the underlaying cipher any more secure. You're still using 3DES, AES, Blowfish, or whatever to encrypt your data -- well known ciphers with well known methods of attack.

I only mention quantum computing because it seems to be the only route to faster procesing power, once Moore's Law breaks down. Perhaps spintronics is a more likely candidate. But the point is that faster computing power will further reduce the time it takes to crack the cipher (any cipher), and you end up in an arms race between larger key sizes and faster machines.

[CodeMonkeySteve]

"Its like you people are talking in code, or something."

V qba'g xabj jung lbh'er gnyxvat nobhg, vg nyy znxrf cresrpg frafr gb zr.

[Mo]

I believe Kevin said that a lot of hacking involves "human hacking". Calling secretaries for passwords, posing as tech support, etc.

[Warren]

scoff -- *all* ciphers are crackable, if by no other method than brute force (i.e. trying every possible key).

That?s a silly thing to say for several reasons. First of all, a one-time pad is absolutely uncrackable (there are an infinite number of keys). Second of all, It?s perfectly feasible to employ keys so large it would take eons to test them all, even a billion fold increase in computing speed would reduce the time required to mere millennia. Another thing, you run into an infinite monkey quandary. That is, encrypted data appears randomized, applying a key to it essentially re-randomizes it. Applying every possible key will produce many intelligible results, only one of which is the original data.

[JDM]

"Quantum computing will never happen on a practical scale as long as the "killer app" is the Shor algorithm."

More importantly, has anyone ever implemented the Shor algorithm or any other quantum algorithm? I'll believe it when I see it. I have a hard time figuring out how you get the results out of quantum algorithms unless you know the answer already.

[Abiola Lapite]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

"I scoff -- *all* ciphers are crackable, if by no other method than brute force (i.e. trying every possible key). The idea is to use a large enough key that the time required to break it would be prohibitive (i.e. hundreds of years). But with faster computers (and the NSA has *acres* of them), the time can be reduced to weeks, perhaps days."

Oh yeah? Why don't you try cracking my public key, then? As someone else has already pointed out, one-time pads are unbreakable even *in theory*, while even a computer the size of our solar system wouldn't crack a 2048-bit RSA key in our lifetimes.

Readers interested in actually learning something substantive about modern cryptographic techniques could do far worse than take a look at the Handbook of Applied Cryptography, freely available to read online.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (MingW32) - GPGshell v3.10
Comment: My Public Key is at the following URL:
Comment: http://www.alapite.net/pgp/AbiolaLapite.txt

iD8DBQFA0hD7OgWD1ZKzuwkRAh6AAJsE51OvaDZpnSu/dDkDD9yXlLb8jQCaA8ep
OZsCR4HANen6VJEx+HAwFgc=
=7Xhf
-----END PGP SIGNATURE-----

[mojo jojo]

Actually I think that quantum key exchange merely tells you whether or not someone has intercepted your message.

[Rus]

Warren,

Good comments. Also a thought: If quantum crypto allows for a provable secure exchange of key material, then quantum crypto used to distrubute a good one time pad ( i.e. one that is truly random ) might be the best possible solution, since the limiting factor with one time pads is key distribution.

And as to speaking in code,

Vs lbh pna ernq guvf, lbh'ir ivbyngrq gur QPZN

[Ray]

I might take a teaching gig at a private school this coming academic year; high schoolers.

The first time someone asks " Why do I have to take math?" (algebra, calc etc) perhaps I'll bring this up. It will completely bore most but the geeks will be off and running.

[thoreau]

Matt's skepticism is not as absurd as you might think. I spent my first year of grad school in a group working on quantum computing before changing fields (for a lot of reasons, skepticism about quantum computing being the least important one), and I was even a co-author on a paper proposing a quantum computing algorithm.

Undoubtedly, with enough time and effort and money somebody will get it to work. The question is, so what?

By the time quantum computing on a large scale is achieved, good old binary computing will be even further along than it is right now. The processor speed for a classical computer will be much greater than the processor speed for any upcoming quantum computer.

In some sense processor speed is not the most important variable, since quantum algorithms can do certain tasks in far fewer steps than any classical algorithm. Still, that just means that the quantum computer will only be able to beat a classical computer for certain exceedingly difficult tasks, which already limits the size of the potential market. And that speed premium will come at a huge cost. For some tasks it could still be cheaper (and almost as fast) to buy a bunch of cheaper classical computers and do parallel processing, instead of buying a really expensive quantum computer.

Sure, there will still be a market. But it will be small. And without a sizable market there will be no money for innovation.

Even worse is if the "killer app" remains the Shor algorithm for factoring large numbers. Factoring large numbers is crucial to cryptography, but it won't be so useful against quantum cryptography. And quantum cryptography is easier to implement than the Shor algorithm. So by the time some huge machine is available to do the Shor algorithm, the Shor algorithm may be obsolete.

Of course, all this would change with either a stunning technical breakthrough on the hardware side, or some new algorithms on the software side. And the history of computing is replete with surprising advances. The people who built ENIAC had no idea that in 50 years ENIAC's progeny would be used as consumer products.

So, my verdict is that quantum computing will never go anywhere in its current manifestation, but if somebody finds a new and better application, well, all bets are off.

[thoreau]

CORRECTION

I mean to say that JDM's skepticism is valid, not Matt's. Matt was criticizing the skepticism.

Sorry.

[JDM]

"I love it, for every great idea there is some halfwit out there ready to tell anyone who will listen it can't be done. Rest assured, someone smarter than you will make it work."

Yes well, there are people smarted than either of us who are still skeptical as well. I'm a big beleiver in techonology, but quantum computing is all theoretical at this point, though I haven't read anything about it in almost a year.

I'll bet people could build a supercollider that rings the entire moon, but never will.

[JD]

A quibble: one-time pads are in one sense perfectly crackable through brute force - it's just that a) you'll never know if you really got it right or not, since there are far more "false positives" than correct answers, and b) cracking one part of a message doesn't help you with the rest, or with future messages. All this assuming proper one-time pad use, of course. I recall that some Soviet one-time pads were broken by US intelligence because the pads were generated by KGB secretaries pounding on typewriter keys: the problem is that humans have a strong tendency to pound left-right-left-right, making the pads far less random.

But Singh is right. Most cyphers have been broken through weakness of usage, not weakness of design. Re-used scrambler settings, known plaintext attacks, faulty implementations, etc.

[matt]

"Quantum computing is an absurd pipe dream"
I love it, for every great idea there is some halfwit out there ready to tell anyone who will listen it can't be done. Rest assured, someone smarter than you will make it work.