Slashdot Mirror
MIT Research: Encryption Less Secure Than We Thought
A group of researchers from MIT and the University of Ireland has presented a paper (PDF) showing that one of the most important assumptions behind cryptographic security is wrong. As a result, certain encryption-breaking methods will work better than previously thought.
"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 information theory, 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. ... 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, some of which give greater weight to improbable outcomes. Those, it turns out, offer a more accurate picture of the problem of codebreaking. When Médard, Duffy and their students used these alternate measures of entropy, they found that slight deviations from perfect uniformity in source files, which seemed trivial in the light of Shannon entropy, suddenly loomed much larger. The upshot is that a computer turned loose to simply guess correlations between the encrypted and unencrypted versions of a file would make headway much faster than previously expected. 'It’s still exponentially hard, but it’s exponentially easier than we thought,' Duffy says."
I thought this was News for Nerds, but instead we are reading about Math, which is some kind of religion, and I am an Atheist.
UNITE with the Campaign for a Free Internet because today, our future begins with tomorrow!
According to the Wired article on the huge Utah data center, its purpose is to store encrypted messages from foreign embassies and eventually, some time in the future, decrypt them and gain insight into how the 'enemy' (any foreigner) thinks. That time is now exponentially closer.
Just great, Now instead of 100 Quintillion years, it's only going to take 100 Trillion years to decrypt my porn
What correlation between the plaintext and cyphertext are they talking about?
Also, I think there is a theorem about modern crypto systems that says if you can guess one bit, the rest doesn't get any easier.
Sheesh, evil *and* a jerk. -- Jade
There was also an article on Slashdot just over a week ago about a separate advance against RSA.
http://it.slashdot.org/story/13/08/06/2056239/math-advance-suggest-rsa-encryption-could-fall-within-5-years
A picture is emerging where not only are the tools available to the layman for protecting information difficult to use, their is a good chance that they also do not offer as much protection as we have long held them to provide.
This is well-known FUD that is making life difficult in government-facing Information Assurance circles. We are still talking ^n where to bruteforce N >>> heat death of universe. This is such unlikely cause of concern that effort currently spent on mitigating and testing is much better spent on ensuring proper implementation and validation of modern cryptographic algorithms. Instead all they care about is entropy assessment and don't care that it is for the implementation of ROT13.
It is (as given on the paper) the "National University of Ireland, Maynooth" and NOT simply "University of Ireland". "The constituent universities are for all essential purposes independent universities, except that the degrees and diplomas are those of the National University of Ireland with its seat in Dublin". I'm from Ireland and had no clue WTF "University of Ireland" was going to be and had it not been for the MIT connection would have assumed it was one of those places you send a few dollars to get a "fake" degree. When and if it's truncated you might see "NUI", "NUIM" or "NUI Maynooth".
I remember reading in an ecology textbook about researchers who wanted to model reforestation after a Mt. St. Helens erupted. They used the average seed dispersion as input to their model, and found that reforestation occured much, much faster.
Turns out the farthest flung seeds take root just as well as the average seed, and they grow and disperse seeds. And the farthest flung of those seeds grow and disperse seeds, compounding the disparity between average and extreme seed dispersion.
Just something to keep in mind when you're working with averages.
Give me Classic Slashdot or give me death!
Use Word! Those zippy-looking XML-ish .docx files are all messed up!
This issue is a bit more complicated than you think.
I don't have insider knowledge, this is just speculation based on societal trends. Where cryptography used to be the almost exclusive realm of governments to protect their secrets, it is now quite mainstream. Encryption protects e-commerce transactions among other things that are useful for the average person and vital to our businesses. It is now a field that university researchers pay attention to (where only cryptographers under the employ of spy agencies did previously) and companies spend their own money to pursue R&D on.
The NSA still does research, but it just doesn't seem likely they have a big edge over the academics who public in journals that everyone can read.
How is this in principle different from the known plaintext attacks (https://en.wikipedia.org/wiki/Known-plaintext_attack)?
These assume that the attacker knows both the encrypted version of the text and the original it was based on, and tries to glean information from their correlation.
Modern ciphers are made resistant even to chosen plaintext attacks, where the analyst knows the key and can tailor-make pairs of plain- and ciphertext.
So, can someone clarify for me exactly what the implications of this are? Is this a lowering of the relevant exponent in the exponentially hard problem, meaning you should multiply your key sizes by some factor that perhaps the paper somehow could provide, or is it a constant factor meaning you should extend your keys by a fixed amount?
Either way, this is important news. I expect the details depend on the nature of the data in question, so there aren't easy answers. Its things like this that are the reasons we use key sizes that are significantly larger than could be practically cracked today.
This might be news in mathematical circles, but this has been a known issue in cryptoanalysis circles for years. It's even the basis for the smart card attacks performed by a German group in the mid-90's. Shannon entropy theory is fine for its limited domain, but as soon as you start dealing with encryption-during-transit of values known to the attacker (plus timings and order of sequence), a LOT more has to be done to ensure high entropy of the metainformation too, and Shannon entropy doesn't account for that.
So in properly defined encryption systems, this isn't much of an issue. The problem arises when people shout "we use AES-256" or "we use SSL/TLS 2.0" (which have fine Shannon entropy) and yet handle that encrypted data in a way that exposes it to pattern analysis attack, whether encrypted or not.
Note that this is a separate issue from that of choosing a secure encryption key/keylength in the first place. It has more to do with how you're wrapping the unencrypted data and how random separate unencrypted data sets using the same key are.
The way I've always thought of it is: if the entropy source is truly random, then any meaningful data injected into it will impart a pattern into the randomness. This can be used to identify the data based on patterns discovered in the supposedly random data. Conversely, if the entropy source isn't truly random, it is possible to discover its pattern, extract that from the equation, and what you are left with is the data.
You still have to deal with the secret key in either case, but this makes building that key exponentially easier, given a known cleartext source and a collection of cleartext encrypted samples. The more encrypted samples of the known cleartext you've got, the simpler the decryption becomes.
Can a knowledgeable party weigh in on what this research means to whole-disk encryption, where an attacker has knowledge of what significant amounts of data, specifically the operating system files, look like un-encrypted? It would seem to me that such knowledge makes the sort of attack described by the article much easier.
Any sentences that starts with, "What if it is we..."
This is a widely held misconception. Double encryption is not significantly stronger than single encryption due to the meet-in-the-middle attack.