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."
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.
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.
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!
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.
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.
Which god? Zeus? Odin? Quetzacoatl? Given the differences between some people's definitions of what 'god' is, I am unconvinced of the 'all aspects of the one divinity' argument, so before we start playing 'what if' let's establish what you mean when you say 'God' and why we should accord that definition primacy over another.
The thought exercise you pose is little different to any one of the form that posits a state of being where your senses are fooled so that you cannot perceive the true reality - brain-in-a-jar, plugged-into-the-Matrix, figment-of-a-dreaming-god. The answer is the same in all cases - if the environment I perceive is consistent, if the illusion is complete, then the difference that makes no difference is no difference. The 'glitches in the Matrix', the 'glimpses of the divine' are less likely to be cracks in the slightly-less-than-perfect-illusion and more likely a figment of our imperfect perception and/or cognition.
If we are figments of a gods imagination, then it is either indifferent or malicious. The mental gymnastics required to claim that a beinn who keeps us in ignorance whilst imbuing us with reason and curiosity is benign are ridiculous.