Key Management Is the Problem...

In any system for transmitting messages using encryption, the security of the system boils down to the security of the encryption key.  This key security often isn't electronic at all – you need a secure way to distribute keys to authorized message senders and receivers.  If that key is stolen or misplaced, your key distribution process and ensure that no real messages are sent with that key – as the bad guys might have it.  This process is called “key management”, and it's hard.  Almost always there's a flaw in key management – anything from a minor and unlikely vulnerability to a gaping security hole you could drive an aircraft carrier through.  All of this is well understood by anyone designing a security messaging system.

So...how do you make a secure key management system?

Well, Roarke Horstmeyer at the California Institute of Technology and some others think they have an answer.  For their “key” they use a slab of special glass whose microscopic structure is random, unpredictable, and readable.  To set up a secure system, they make two slabs of glass – one for each side of the messaging system.  They then read the random data in each key and combine them to make a public key.  This public key can be safely published to the world, as it's contents can't be used for anything by itself – you have to possess one of the two glass slabs to make it useful.

Let's say we have two parties: the traditional Alice and Bob, each of whom have one of these special glass slabs.  The combination has been published.  Now Alice wants to send Bob an encrypted message.  She figures out how long her message is (“n” bits) and then takes the next “n” bits of her key (read from her glass slab) and uses them to encrypt her message.  She sends the message to Bob.  Bob takes the next “n” bits of his key (read from his glass slab) and subtracts it from the published combined key, yielding Alice's key – which he then uses to decrypt her message.  Straightforward and as secure as a one-time pad.

Really the glass slabs are just a memory – a very reliable, physical and tangible memory that (today at least) could not easily be copied.  Even just reading it would take a considerable amount of time, which means that security protocols (processes) could detect the fact that someone was reading it.  There's nothing special about the glass per se; it's this combination of characteristics that make it attractive.  A thumb drive could store data for a key, and be used the same way as the glass – but copying the thumb drive takes only a few seconds, and it's easy.  A thumb drive (or any other electronic store) would be vulnerable to any such attack.

The trouble with the glass, though, is that almost certainly there's a technical attack – some way that a bad guy could quickly read it.  Any conceivable storage mechanism for a key has this problem...

“Fiendish” Cipher from WWII...

Via Bruce Schneier, this fascinating story of a POW sending coded messages in his letters to his family...

Quantum-Resistant Encryption (UPDATED)...

If you posit the existence of a quantum computer (either now, tucked away in a government agency, or in the future when scientists figure out how to do it), then the cryptosystems in general use today can be trivially broken.  In plain English: anybody with a quantum computer can read all of your encrypted messages, including any secure web sessions (HTTPS via SSL).

I just stumbled across a cryptosystem that doesn't have any known attack via quantum computer, and is available today.  It's called NTRU, and it's an asymmetric key system with fairly high performance (especially compared with conventional asymmetric cryptosystems).  It's available in a Java library from the creators, and it's now part of Bouncy Castle.

I just barely understand the math behind conventional cryptosystems.  I haven't (yet) tried to understand this one, but I'm very curious to see how its mathematical properties make it immune to the quantum attacks that would work against conventional cryptosystems.  Perhaps one of my readers understands and can illuminate the topic for us?

Update 2/5:  Reader and friend Doug W. writes to say:

Color me very skeptical. I have no problem with quantum computing as an interesting basic research topic, but many folks, both in the field and in the press, seem to believe that we’re just a few years away from something practical. My suspicion is that it’s more like nuclear fusion power, which has been a constant 10-20 years away from practicality for over sixty years. In fact, I’m far more optimistic about fusion power than quantum computers, which isn’t saying much.

It’s possible – in some very strange theoretical sense – for a quantum computer to factor large numbers used in RSA crypto, assuming you could even convince the quantum device to do big integer math, though that alone seems unlikely to me. However, my gut says that the thermal noise in any system, even near absolute zero, dwarfs the energy difference between that many superimposed quantum states by many orders of magnitude (dozens? hundreds?). Thus, I find it difficult to believe that such a system would be stable long enough to be useful. I could certainly be wrong, but I’m not holding my breath. Right now, quantum computers can factor the number 15, and they’ve been stuck there for a good while -- it’s a long way from 2**4 to 2**1024. Just saying…

And don’t get me started about quantum cryptography. As Paul Kocher (a very well known and respected crypto researcher) said in 2003:

To me, quantum cryptography is useless. It purports to solve a problem that’s already solved. It is an interesting research problem, though. But, you’re not going to see quantum computers showing up to do useful things probably in my lifetime and possibly never. But it is the most interesting problem in computing in the last 30 years. It’s absolutely fascinating. But, of all the things that keep us awake at night, that’s way down there with alien invasions.

I’ve heard lots of talks on quantum crypto at cryptography conferences over the past 15 years, and most of the cryptographers I know just roll their eyes. It is, however, a great research area if you are looking to get research grant money.

Also, fwiw, NTRU has been around quite a while and is at best a niche technology. Lattice cryptography has a bit of a funky reputation (not all due to NTRU), due to lots of claims which have been repeatedly broken. The NTRU folks are nice guys and very bright, but I don’t see it getting wide deployment anytime soon.

[Full disclosure: I have an applied physics degree from Caltech, and I do cryptography for a living]

New English Letter Frequency Tables...

Many older ciphers (and some less sophisticated current ciphers) are based on letter substitution (instead of “a”, write “m”, instead of “b”, write “j”, and so on).  A basic tool for cryptanalysts trying to break such a cipher is tables of “letter frequencies”.  These tables show how often each letter appears in ordinary writing for any particular language.  Even more importantly, the tables will include how often each “digram” (pair of letters) and “trigram” (triplets of letters) appears.  With these tables and a little additional cleverness for polyalphabetic substitution ciphers, all you need is enough encrypted messages and you can break the code.

Letter frequency tables have been readily available for a long time.  I remember first seeing them in the 1970s (when I was studying cryptography in the U.S. Navy), and the tables I saw then were quite old – WWII-era.  The English letter frequency tables most often used today were generated by a fellow named Mark Mayzner in the early 1960s.  He analyzed (the hard way!) some 20,000 English words to generate his tables.  

It turns out that Mr. Mayzner is still alive, and just last month he wrote Peter Norvig to ask if he might update those tables using today's much easier methods and vastly larger accessible texts.  Peter did exactly that, and the results are here – and freely downloadable!

Can You Decrypt This Message?

If so, the folks in the British intelligence agency GCHQ would like to hear from you – because so far, this recently found WWII pigeon-carried message has completely stumped them.

Even as recently as WWII it was common for secret messages to be sent via trained pigeons.  The message was rolled up tightly and put inside a small covered vial attached to the pigeon's leg...

Crypto vs. Rubber Hose...

Hristo Bojinov of Stanford has come up with a way to thwart a “rubber hose” attack that tries to force an individual to give up a password.  No, it's not training in pain tolerance – it's a different way to authenticate.

The basic idea is that you can learn subconciously (in fact, this is the way we learn most things), without even realizing that you've learned something.  Passwords are not like this; those we very conciously learn (memorize). 

The new technique involves learning how to play a special game.  In the process of doing this, you learn – subconciously – a 30 character password made up of just six characters.  This is a very secure password.  If someone asked you to recite it, you wouldn't be able to do it – not even if they gave you the rubber hose treatment, and not even if you wanted to give them the password.  You are not concious of it at all.  To actually authenticate yourself to a computer, you have to play a round of their game.  In doing so, you demonstrate to the computer that subconciously you really do know the password.

You might ask yourself (I certainly did) “But how does this help with the rubber hose attack?  The trained authenticator could still be forced to play the little game!”  The authors of the paper assert that there must be a “liveness test” – in other words, you can't use their method for remote authentication, but rather only for authentication when physically present at the system you're trying to authenticate to.  Presumably someone would then notice if you were being beaten with the rubber hose.  There are some problems with that, as there are ways to coerce people that don't require the coercer to be physically present with the coerced (for example, your spouse or child could be held hostage until you authenticate).  Worse, I think, is that if you subject a password authentication system to a liveness test, then its security is enhanced in the same way.  In other words, it seems to me that a large part of the benefit of this new system is derived from the liveness test, rather than the method itself. 

But all that carping aside, there are some genuinely interesting security ideas in here.  How practical they are is another matter altogether, but the general notion of using subconcious memory strikes me as worth exploring.

Authentication to a computer system is a really tough problem, far harder than most people realize.  It's the basis for many of the kinds of computer security that average people run into every day (like, say, access to your bank account) – and yet we are still lacking good, secure, reliable solutions.  Passwords are by far the most common approach, and they are demonstrably feeble.  Biometric authentication (fingerprints, iris patterns, etc.) are stronger, but are defeatable and less reliable than most people consider acceptable.  So I'm always interested in anything that might improve the situation...

Enigmas in the News...

Enigma machines, that is: WWII-era German cryptographic machines.  I had no idea that so many had survived the war...

Calling All Code Breakers...

Some historians want some help breaking a Civil War diary code...

Copiale Cipher Cracked...

News story here...

AES Vulnerability...

Not bad enough to get worried about – yet – but something to keep an eye on...

Tunny Machine Back in Action!

If you're a technology history junkie like me, you probably know about the Tunny machines.  They were an important part of the Bletchly Park efforts that decoded Nazi messages.

The British National Museum of Computing has recently finished building a complete, working replica of a Tunny machine.  In the course of doing so, they've now documented exactly how it was built (this documentation didn't exist before they started their work).

This is something I would really like to see.  Next time I'm over in England, I've got to make a point of seeing this museum (I've never been there)...

Code Cracking...

Where the code is on lottery tickets.  A Canadian statistician figured out how to pick winning tickets in a “scratcher” lottery – without scratching.  It's a fascinating read...

Public Key Cryptography Invented Earlier than We Thought?

Ask anyone interested in cryptography about public-key cryptography, and the names of Diffie, Hellman, Murkle, Rivest, Shamir, and Adleman will quickly arise.  They're the inventors of the concept of public-key cryptography as most of us know it.

Well, maybe not.  If this article is accurate, apparently the British government developed public-key cryptography independently and several years earlier than the six listed above.  The narrative sounds plausible to me, though of course I have no personal knowledge of any of it...

How to Safely Store a Password...

Hint: bcrypt is involved...

Russian Spies Had Secure Communications...

Though they looked like the Keystone Kops in general, one thing the Russian spies apparently did right was communications security.  They used steganography, and their communications were never detected, much less decrypted...

Chaocipher Revealed...

John Byrnes' Chaocipher has long intrigued cryptanalysts, mainly because how it worked was never revealed and nobody could be sure that it was even real.  That has now changed: the entire system is now in the public domain, and it's both real and clever...

Factoid of the Day...

Retiring Justice Stevens was a WWII cryptographer.

Cryptography in JavaScript...

Challenging objective: “build a secure, powerful, fast, small, easy-to-use, cross-browser library for cryptography in Javascript” – claimed met.

Diffie, Hellman, and Merkle Win a Prize...

The Hamming Medal was awarded to cryptographic pioneers Whitfield Diffie, Martin Hellman, and Ralph Merkle.  Their basic technique for what is today called “public key” or “asymmetric” cryptography was the first available to anyone outside three-letter agencies (NSA, CIA, etc.).  It's also the only real cipher I've actually implemented, several times over the years and most recently just a year ago.  Though it's over thirty years old, it's still perfectly viable...