MIT Research: Encryption Less Secure Than We Thought 157
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."
Huh? (Score:4, Insightful)
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.
Re:good news for NSA (Score:5, Insightful)
I severely doubt this is news to the NSA.
Interesting times (Score:4, Insightful)
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 [slashdot.org]
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.
Re:good news for NSA (Score:2, Insightful)
Bad news for the NSA. Known insecurity can be fixed either through patch or brute force (bigger key). The NSA, I'm sure, prefers secret insecurity.
Re:good news for NSA (Score:4, Insightful)
And, if you let them, the NSA will be owning exponentially expensive taxpayer-funded stuff that is then used to spy on taxpayers.
Re:FUD (Score:3, Insightful)
With all due respect, "citation needed". The authors of the paper aren't FUDsters spewing soundbites for the media, they are presenting it at the International Symposium on Information Theory before their peers. I can't tell from the link whether the paper has been accepted by a peer-reviewed journal or whether it's still in review, so some skepticism might be called for before uncritically accepting the conclusions, but this is still a far cry from FUD.
I'd like to see something more than just a dismissive handwave that this is "well known" old news and not new evidence of weaknesses in cryptographic methods. Even if this has been suspected for some time and the paper merely describes rigorously the nature of such weaknesses, that's still scientific progress and undeserving of the label FUD.
Re:God says... (Score:1, Insightful)
People who judge others intelligence by the words they use are not all that intelligent.
I wont even get into the self absorption involved in using one long run-on sentence to say what could have been more simply expressed in very few words.
There is nothing at all wrong with a few short, simple obscene words if they convey exactly the meaning intended. Speech is not a Christmas tree - you dont need to decorate it.
Re:good news for NSA (Score:5, Insightful)
I'll undo my moderation in this thread just to tell you that you are wrong. One cannot determine the key from the ciphertext. If they can this is known as a "break" in the cipher.
A "break" in a cipher does not mean that it is practical to find the key, merely that it is more feasible than mere brute force. For example, a "break" could reduce the effective strength of a cipher from 256 bits to 212 bits under a known plaintext attack. This is a BAD break in the cipher given current standards, but it is the cipher is still completely uncrackable in human (or even geologic) timescales.
The "weeks or months" number, by the way, has nothing to do with cracking cryptographic keys. I would surmise that is a number more geared towards cracking passwords, which is an entirely different topic. Also, for some realistic numbers on cracking encryption keys, check out Thermodynamic limits on cryptanalysis [everything2.com]
Re:good news for NSA (Score:4, Insightful)
Actually, you're both wrong.
For certain types of encryption, you are right - a known-plaintext attack that easily reveals the key is a fatal problem for the encryption method. This is true of AES, for example. The converse is also true - currently, knowing the plaintext and encrypted values for an AES-encrypted block of data does not let an attacker determine the encryption key in a reasonable amount of time. It still requires testing every possible key to see if it produces the same encrypted block given the known plaintext.
Other types of encryption are absolutely vulnerable to known-plaintext attacks. I'm less familiar with this area, but certain common stream ciphers (like RC4) are literally just an XOR operation, and so if you know the plaintext and ciphertext, you can obtain the keystream by XORing them together.
Re:good news for NSA (Score:3, Insightful)
If the NSA was only concerned with open source cryptographic products and protocols, you would have a point. But aside from government procurement, NIST standards are in practice used to specify deliverables for corporate security products. Getting Duel_EC_DRBG into a NIST standard is the equivalent of putting a backdoor into an ISO standard for door locks.
Once in the standard, the NSA can then lean on vendors to use the broken algorithm, and the vast majority of users of that product would be none the wiser. Most corporate security products are opaque and proprietary, and the purchasing agents are unlikely to have a clue about the problem. All they want to see is "NIST-approved".
All we can do is conjecture, but I don't think the scenario is that outlandish. To my mind it seems more like standard operating procedure than unlikely conspiracy. The fact that the backdoor is clumsy reflects less on the carelessness of the NSA, and more on the exceptional skills of the civilian community. We're smarter now. The NSA has fewer tricks up its sleeve, but it's not like they can just quit and go home.