IanG on Tap

I see from a wide variety of sources that flaws have been found in various popular hash algorithms. Someone has found a collision for SHA-0. (Remember, the whole point of a hash function is that it is supposed to be computationally unfeasible to find two messages that hash to the same value.) Moreover, there are rumours doing the rounds for a break of SHA-1.

If it turns out that SHA-1 is compromised, that's a big deal - lots of stuff uses SHA-1.

This highlights a property of most cryptography that often seems to be ignored: it's all based on conjecture.

The way we typically do cryptography today relies on various mathematical problems that are thought to be hard, such as factoring numbers with large prime factors. I'll just highlight the significant part of that.

"...problems that are thought to be hard..."

That's not "guaranteed" to be hard, "robustly mathematically proven" to be hard or "deemed by divine provenance" to be hard. Just thought to be hard. That's the conjecture upon which we all rely when we use typical cryptographic techniques.

The problem with this is that mathematicians have a pesky habit of making progress. Things that nobody knows how to do one day are doable the next. Who's to say that one day, someone won't find an efficient way of solving the mathematical problem underlying a particular cryptographic technique, thus rendering it easy to break the cryptography? After all, the various government agencies concerned with cryptography and the interception and decoding of encrypted messages seem to employ an awful lot of mathematicians, so you have to assume that some of them are probably working on these very problems.

Or possibly the NSA already knows how to crack all the popular algorithms, and is busy working out how to crack the new and exciting crypto systems they've invented but have yet to leak out into a broader world.

The problem with basing a crypto system on the conjecture that a particular calculation is computationally expensive to perform, is that if that conjecture turns out to be wrong, and an efficient way of performing the computation becomes widely known (or at least known by your enemies) then the crypto system (and any other systems based on the same conjecture) all become useless.

But what can you do?.. I suppose the main thing is just to be aware of the risks, and to make sure you have sufficient defence in depth. If the discovery of a fundamental weakness of any single algorithm means the compromise of your systems, then perhaps you need deeper security. Regardless of what you base your security on - mathematical problems, hired goons, or limited access to the relevant mattress - a single point of failure is bad.

Why Quantum Crypto Might Make Things Worse

There are those who believe quantum cryptography will be the answer - this relies on physics rather than mathematics. But there are two problems there. One is that it's still conjecture, it's just now we have to hope that the physics is right, rather than that the maths is hard. Physics has a recurring habit of turning out to be slightly more complex than we thought from time to time - Newtonian physics is pretty useful, but Einstein came up with something better. The classical view embodied in Newton's and Einstein's laws is pretty darn useful, but quantum mechanics illustrated that it's not the whole story. Who knows what's next?

But there's another issue - even though there are some early successes with quantum cryptography, it'll be a long time before it gets deployed everywhere. This means we should expect a long crossover period where both mathematical and quantum cryptography are in use. And here's the shocker: if quantum computing starts to become successful (and you could reasonably guess that quantum computing will advanced at about the same kind of rates that quantum cryptography does) it poses a problem for current public/private key cryptosystems. The big deal with quantum computing is that it effectively allows you to build a real non-deterministic computational device. It's easy enough to model a non-deterministic computer with a normal computer; it just becomes exponentially expensive to do so. But if you have a real one, then problems that can in theory be solved cheaply with a non-deterministic Turing machine all start to look approachable. And as a general rule, deriving the private key from a public/private key crypto system is one of the things that non-deterministic computational models turn out to be really good at.

By and large, the capabilities of quantum computation are, I suspect, somewhat overestimated. I think those who regard them as the next big thing that will keep Moore's law going will be disappointed - they're not in fact a way of running your existing code faster. But for certain kinds of problems they excel. And deriving a private key from a public key is, in principal, one of them. (This is true for non-deterministic computational models at least. Whether it will turn out to be true for real quantum computers if we ever manage to get them working on more than a handful of bits at a time remains to be seen.)

So if you're hoping for massive advances in quantum information systems to save us from cryptographic doom, be careful what you wish for. It might usher in technology that renders all existing public/private key systems useless at a stroke, which might not be regarded as progress.

Of course we could all just use one-time pads. They're pretty secure, so long as you have a good random number source. Just a tiny key management issue to deal with...