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
Any correlation between plain and cipher. For instance if you can deduce that a particular string will occur at a particular point in the plaintext, then you can isolate the cipher equivelant and use that as a lever to break the rest of the ciphertext. You dont have to deduce it with certainty for this to be important, even if you have to try and discard a number of possible correlations before you find one that holds up.
This is a pretty basic old-school cryptographic method, kind of fun to think that fancy-pants mathematicians have been missing it all these years.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Friends don't let friends enable ecmascript.
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!
As usual, the paper makes more sense than the press release, but is less grandiose in its claims.
It's a fairly technical result that finds some appeals to the asymptotic equipartition property lead to too-strong claims, compared to a more precise analysis.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
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.
Nah, once you guess one bit, the only bit left is zero.
Give me Classic Slashdot or give me death!
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.