Cracking Crypto Just Got a Little Easier

Researchers from MIT and the Northern University of Ireland stand by their theory that information theory is the wrong foundation for cryptography and security.

It’s been a brutal month for crypto.

Starting with the Black Hat conference, researchers, engineers and hackers have been unveiling new weaknesses and attacks in different cryptographic implementations that threaten the security of communication and commerce on the Web.

Not only have holes been shot in SSL over and over for years, but recently experts tried to put a prognosis on the lifespan of the RSA algorithm, which was met with some skepticism.

The topper, however, could be a paper released by a team of scientists from MIT and the National University of Ireland at Maynooth who may just have flipped the study of crypto on its head with their findings. They conclude that the mathematical fundamentals on which cryptography is measured may be, well, misapplied.

The discipline of information theory is what’s at question here, in particular, the notion that most work done analyzing secure cryptographic schemes have depended on a common assumption—which is the incorrect approach according to the scientists.

In an article released by MIT, the scientists said that in information theory, information is tied to entropy, which is a measure of uncertainty in a random variable and usually refers to Shannon entropy, developed by MIT professor Claude Shannon. Shannon entropy, as it turns out, is flawed for secure implementations because it is based on the average probability that a string of bits will occur, according to the MIT article.

But since an attacker needs to make only one reliable correlation in order to continue guessing a password or private key, for example, the need to know the average probability is unnecessary. Giving more weight to an improbable outcome is a more accurate assessment of how to break the security of a given target. The article said that a computer cut loose to guess correlations between encrypted and unencrypted versions of a file would learn the answer much quicker than expected.

“It’s still exponentially hard, but it’s exponentially easier than we thought,” said Ken Duffy, a NUI researcher. “Attackers often use graphics processors to distribute the problem. You’d be surprised at how quickly you can guess stuff.”

Muriel Medard of the research laboratory of electronics at MIT told Threatpost that Shannon entropy works just fine to measure the efficiency of communication. Until now, the randomness of data at the basis of that theory was thought to be enough to protect it, but she said their work proves that data isn’t so random, especially if an attacker knows enough about a target when they’re able to enter passwords, for example.

“When doing a guess of some kind whether it’s a password or verifying  a hash, that makes a huge difference in the amount of time it takes to arrive at the guess,” she said. “There are small variations which are small enough not to worry about them for network performance, but have a significant impact on the security of the network when looking at guessing attacks.”

When compression, or any kind of outside noise, is introduced, this alters how an attacker would go about guessing a secret because it’s changing the randomness of the data.

“It’s like when you play 20 Questions with someone you know, you’re likely to guess quickly versus someone you don’t know at all,” Medard said. “Theoretically, people could choose anything in the universe, but you may have knowledge about their preferences that now allow you to guess more quickly.

“That means that small variations from the uniform, whether as a result of compression or noise that are not completely uniformly distributed, you can use these small differences to hear very stark differentials of what happened under an idealized assumption and what might happen under slight non-uniformity.”

Medard said she’s not sure yet about the ultimate impact the team’s work would have on cryptography or security in general.

“We’re still trying to figure that out ourselves,” she said. “Probably in some domains where you’re just trying to hide information and are not so worried about guessing, there would be a limited impact.”

Suggested articles

Newsmaker Interview: Scott Helme on Securing the Web

Threatpost sat down with Helme to discuss the state of web security, including certificate transparency, HTTPS deployment, Let’s Encrypt, content security policy and HTTP strict transport security.


  • BEE on

    This is total B.S. Guessing at something by knowing a lot of things about a person to figure out their password etc. and running a program is apples and oranges and B.S. The truth is that MIT and the school in Ireland are working on security for the money =Governments. they are never going to tell us the truth: point , the British Gov. and the American both have much very secret work about WWII that they will never divulge, period. Do not believe the story that was just told. There is NO information in the statements that the two schools just released to the public.
  • TG on

    Well,guessing worked in the movie Wargames, so it must be true! Looking at the paper it doesn't seem to have much practical impact aside from confirming that guessing can be preferential to brute force.
07/18/18 5:55
LabCorp investigates a potential #databreach that could affect millions:

Subscribe to our newsletter, Threatpost Today!

Get the latest breaking news delivered daily to your inbox.