Encryption is less secure than we thought

August 14th, 2013 by Larry Hardesty in Other Sciences / Mathematics
Muriel Médard is a professor in the MIT Department of Electrical Engineering. Credit: BRYCE VICKMARK





Traditionally, information-theoretic analyses of secure schemes have assumed that the source files are perfectly uniform. In practice, they rarely are, but they're close enough that it appeared that the standard still held.

"We thought we'd establish that the basic premise that everyone was using was fair and reasonable," says Ken Duffy, one of the researchers at NUI. "And it turns out that it's not." On both papers, Duffy is joined by his student Mark Christiansen; Muriel Médard, a professor of electrical engineering at MIT; and her student Flávio du Pin Calmon.

The problem, Médard explains, is that information-theoretic analyses of secure systems have generally used the wrong notion of entropy. They relied on so-called Shannon entropy, named after the founder of , Claude Shannon, who taught at MIT from 1956 to 1978.

Shannon entropy is based on the average probability that a given string of bits will occur in a particular type of digital file. In a general-purpose communications system, that's the right type of entropy to use, because the characteristics of the data traffic will quickly converge to the statistical averages. Although Shannon's seminal 1948 paper dealt with cryptography, it was primarily concerned with communication, and it used the same measure of entropy in both discussions.

But in cryptography, the real concern isn't with the average case but with the worst case. A codebreaker needs only one reliable correlation between the encrypted and unencrypted versions of a file in order to begin to deduce further correlations. In the years since Shannon's paper, information theorists have developed other notions of entropy, so¬me of which give greater weight to improbable outcomes. Those, it turns out, offer a more accurate picture of the problem of codebreaking.


"It's still exponentially hard, but it's exponentially easier than we thought," Duffy says. One implication is that an attacker who simply relied on the frequencies with which letters occur in English words could probably guess a user-selected password much more quickly than was previously thought. "Attackers often use graphics processors to distribute the problem," Duffy says. "You'd be surprised at how quickly you can guess stuff."

In their Asilomar paper, the researchers apply the same type of mathematical analysis in a slightly different way. They consider the case in which an attacker is, from a distance, able to make a "noisy" measurement of the password stored on a credit card with an embedded chip or a key card used in a keyless-entry system.



"Some of the approximations that we're used to making, they make perfect sense in the context of traditional communication," says Matthieu Bloch, an assistant professor of electrical and computer engineering at the Georgia Institute of Technology. "You design your system in a framework, and then you test it. But for crypto, you're actually trying to prove that it's robust to things you cannot test. So you have to be sure that your assumptions make sense from the beginning. And I think that going back to the assumptions is something people don't do often enough."

Bloch doubts that the failure of the uniformity assumption means that cryptographic systems in wide use today are fundamentally insecure. "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 says. The MIT and NUI researchers' work, he says, "is very constructive, because it's essentially saying, 'Hey, we have to be careful.' But it also provides a methodology to go back and reanalyze all these things."

The paper is titled "Brute force searching, the typical set, and guesswork."

More information: arxiv.org/pdf/1301.6356.pdf

Provided by Massachusetts Institute of Technology


"Encryption is less secure than we thought." August 14th, 2013. http://phys.org/news/2013-08-encryption-thought.html