Original URL: http://www.theregister.co.uk/2013/08/14/research_shakes_crypto_foundations/

Your encrypted files are 'exponentially easier' to crack, warn MIT boffins

Maths gurus tug rug from under modern crypto: 'You’d be surprised how quickly it takes'

By John Leyden

Posted in Security, 14th August 2013 19:03 GMT

Encryption systems may be a lot less secure than we thought, according to new research into the maths underpinning today's cryptography.

Boffins in the US and Ireland have managed to poke holes in modern information theory, an area of mathematics used to prove the strength of cryptographic systems before they are trusted and widely deployed.

As a result, the scientists claim it's easier to take encrypted files and deduce their original unencrypted contents than one would expect.

In other words, computers can find correlations between encrypted data and its unencrypted form far faster than previously thought, and eventually crack the lot. Code-breaking software needs to find just one reliable correlation before it can hit the jackpot.

Cracking an encrypted file will still be a hard slog, we're reassured, but just not quite as tough: an attacker could unlock a file far sooner than the many months or years of processing time previously estimated.

That's because information theory, built on work by Claude Shannon in 1948, assumes certain things about the entropy of digital information - simply put, how disordered the data is in a message. Analyses of modern cryptographic algorithms assume perfectly uniform sources of information, in which the mix of binary 1s and 0s is perfectly random and hopelessly unpredictable.

In reality, data is never that perfect: parts of files can be guessed and those bytes used as a foothold in cracking open the data by brute force.

“It’s still exponentially hard, but it’s exponentially easier than we thought,” said Ken Duffy, of the National University of Ireland (NUI), who co-wrote this latest research.

"Attackers often use graphics processors to distribute the problem. You’d be surprised at how quickly you can guess stuff.”

Duffy and three other scientists from the Massachusetts Institute of Technology (MIT) and the NUI presented their work, Brute force searching, the typical set and guesswork, at the International Symposium on Information Theory [PDF]. A follow-up paper, due to be unveiled this autumn at the Asilomar Conference on Signals and Systems, will take the research one step further: it will demonstrate that keyless door locks that work with wireless keycards may not be as secure as previously thought.

Matthieu Bloch, an assistant professor of electrical and computer engineering at the Georgia Institute of Technology, said the above research does not mean cryptographic systems in wide use today are fundamentally insecure, rather that they are less secure than we've all been led to believe.

"My guess is that it will show that some of them are slightly less secure than we had hoped, but usually in the process, we’ll also figure out a way of patching them," he said. "It’s essentially saying, ‘Hey, we have to be careful.’ But it also provides a methodology to go back and reanalyse all these things." ®