How secure is your encryption?


Papal Encryption
Papal Encryption (Photo credit: Samuraijohnny)

The answer is, “probably quite secure, but not as secure as you might think.”

This is not a story about the NSA but about the fundamental maths of encryption – and about the ability to “guess” what an encrypted message might mean through a sophisticated version of “frequency analysis” – in other words guessing what the unencoded symbols would be on the basis of how likely they are to occur.

Up to now the assumption has been that for long enough messages encryption would essentially erase the underlying pattern of a message – in other words the encoded message would have the maximum possible degree of randomness or “entropy“.

A parallel can be made with compression – in a perfect compression algorithm entropy would be maximised: there would be no underlying pattern of 1s and 0s in the binary – as if there was a pattern then this too could be compressed (replaced by a shorter symbol) and so on. In fact most compression algorithms are pretty good – which is why you cannot repeatedly zip files and hope they will keep getting smaller.

But if you are using encryption you might not regard “pretty good” and really good enough – you would want a more or less nailed-on guarantee that your encryption would have maximum entropy, as a pattern in the coded message might point to the patterns in the underlying message.

To get that guarantee we need to show that coding the same word in “clear text” would result in a truly random selection of “code words”. Now, no mathematical process can ever truly guarantee this but it was assumed, based on what seemed to be sound reasoning, that for a sufficiently long message of “clear text” the entropy of the coded message would rapidly approach the maximum.

But report Mark Christiansen and Ken Duffy from the National University of Ireland (Maynooth) and Flavio du Pin Calmon and Muriel Medard from MIT – that assumption is flawed. In fact, in the real world, the approach to maximum entropy is a good deal slower than previously believed: in fact “conditioned” (i.e. real world) sources never get there

There is a paper discussing this – here – with some heavy duty maths. Another article – which probably does a better job than me in explaining it, (but also seems to play down the Irish connection!) is here.

The bottom line seems to be that sophisticated “brute force” attacks (also known as guessing!) might just work after all – because once you guess one word well, the rest of the code might fall into place. If the decoder has some clues about what the message might contain (think of the cryptanalysts at Bletchley Park knowing that many German messages contained weather reports) then it is possible that guesses might – just might – work.

Does this mean that your encryption is broken? Probably not. But it does mean that someone might be able to break your messages well inside the known age of the universe after all.

So, we are not protected by the US after all


Image representing Google as depicted in Crunc...
Image via CrunchBase

Let me start this post – on the PRISM programme – by making a few things clear.

Firstly, I think the jihadist terrorist threat is real and dangerous and even potentially existential in nature: if these people had atomic weapons do you think they would hesitate to use them?

Secondly, I think the police and security services need to be able to do their job to deter and catch these people.

And, thirdly, I believe that all such actions need to be regulated by law and need to reflect the fundamental protections we expect.

What we now know is that a US based internet – which is what we have when we consider Google, Facebook, Twitter and the rest – does not offer those of us who are not US citizens the guarantee that our communications are protected by law. No probable cause is needed to snoop at what we say and do – don’t take my word for it, listen to what the President of the United States has said.

He’s been very clear that the communications of non-US citizens have no legal protection. And I am sure he is right.

Most of us, perhaps until today, sought to resist the efforts to “internationalise” the Internet: why would we want Putin or Assad to have a say on internet regulation? We don’t, and we still don’t.

But equally the current situation is not acceptable either. For Europeans we must now expect and demand that the European Commission intervene swiftly and make it clear to the US internet giants operating on European soil that the current situation is unacceptable and equally make it clear to the US authorities that this is a matter of trade policy: after all communications could be being intercepted to steal trade secrets as much as anything else.

The aim should not be to ban the authorities’ access to communications but to ensure that European citizens who trade with US internet companies are offered the same legal protections as US citizens (and vice versa as far as Europe is concerned).