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.
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.
Cooty Rats Semen
(If you don't get it, you need to see: http://www.imdb.com/title/tt0105435/ )
Pics or it didnt happen
Cryptop = buying time
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!
Isn't this (one reason) why any good encryption system compresses what it is encrypting first? To maximize the data's entropy?
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.
Still not going to stop using encryption. Just because it's not as good as previously thought, it doesn't mean we should just hand everything over to the NSA in cleartext. Even if there is a 100% chance of them hacking it, make them work a little.
We'd send our drones after them if they wouldn't hack them and send them back.
they found that slight deviations from perfect uniformity in source files, which seemed trivial in the light of Shannon entropy, suddenly loomed much larger
Okay, but can't they simply apply an xor mask to the plaintext to make it perfectly uniform, and then encrypt the masked version?
For example, let's say it turns out that iterating on the SHA512 function [SHA512(key), SHA512(SHA512(key)), etc.] yields an arbitrarily long xor mask that has perfect uniformity, and is statistically indistinguishable from a random sequence. You then apply that mask to the plaintext before encrypting it to destroy its non-uniformity. Wouldn't that be the fix?
Or is the problem here that they can't find a function that can truly mask out the non-uniformities of the plaintext prior to encryption? If that's the case, I would be very surprised, and for me that failure would be far more interesting and news-worthy.
Sometimes "polite" language is not in itself sufficient to adequately convey a message. One could spend time elaborately preparing a ripost of the finer points of a religious belief which is, on it's face, ridiculous. This approach, however, would not adequately the pain, suffering and existential angst felt by the Anonymous Coward to whom you are replying or the countless other members of our community, myself included, who have been mistreated by the followers of this "imaginary friend." We are at a point in history and in society where people are using their "beliefs" to further their ends of oppressing people who are not attempting to do harm to anyone. We are at a point where we are expected to "respect" other's beliefs even when those beliefs run directly counter to what can be observed by the naked eye, even when the exercise of those beliefs would cause harm to those in the immediate vicinity. Still we cannot even read a website, purporting to relate to technology news, a completely secular subject, without finding these beliefs being forced into our eyeballs and down our throats. The level of anguish experienced at these events can not be expressed without resorting to expletives.
tl:dr: Fuck you and your wankery.
Is 1563649 a prime number?
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.
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.
Does this men that by digitally signing an email I'm weakening the PGP encryption?
Any sentences that starts with, "What if it is we..."
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.
'Itâ(TM)s still exponentially hard, but itâ(TM)s exponentially easier than we thought,' Duffy says.
So, what, rather than a computer taking until the heat death of the universe to crack my 4096 bit key it will only take until our Sun goes super nova?
brb, generating 8192 bit keys.
No sig for you!!
sekg 1408 drnh @$?" xxth bhg9 douche bag
hjmp llmo 3860 ++%# jjgj mmnm muggle
The mind conceives, the body achieves, the spirit manifests.
Where on the hard drive is the partition table? Where in the partition is the superblock? Where on the hard drive, is the root directory assuming the owner used one of the most common filesystems?
"A codebreaker needs only one reliable correlation between the encrypted and unencrypted versions of a file in order to begin to deduce further correlations."
It is necessary to encrypt twice, using 2 different encryption methods. Then it will be impossible to find one reliable correlation.
Friend, calm down. tdavis, the author of these many posts (and a rather terrible operating system), is a known schizophrenic on welfare. Please understand that his is mentally diseased and be kind to him.
RSA is the thing we should be worried about; primarily since it's used so widely. The math behind quick factorization is probably already known, add in quantum computing and you'd need like 2^1024 bit keys for RSA to make sense. So that leaves really symmetric encryption systems (don't know enough about the curve based stuff) and those are typically based on shifting, XORing with key and repeating. With respect to the article I'm not at all sure that anything can be inferred from having ciphertext and plaintext for a given key without having a quick way to do set subtraction between the set of all possible keys and the keys that could feasibly produce the ciphertext given the plaintext. Even then the key length could be increased very easily so you'd need something like a linear time method to do the set subtraction. Then, you'd just keep doing set subtraction until you had a reasonable number of keys like 1,000,000 and then go the other way and just brute force future ciphertexts to see which ones spit out coherent plaintext. But really why not just work with OTPs, steganography, multiple layers of encryption or private encryption schemes?
I suggested using 2 different un-related encryption methods. Because the 2nd method is entirely different from the first, MITM does not function. Using 2 different un-related encryption methods protects against other attacks, also.
Meet-in-the-middle applies to using the same encryption method two times, using different keys.
Note that the free TrueCrypt offers encryption using 2 or more different encryption methods, with different keys for each method. They call it cascade encryption. Unfortunately, that term is used also for encryption using 2 or more keys with the same encryption method.
woah! wait guys... lets just see what this God fella has to say, now...
This sig is not paradoxical or ironic.
His imaginary friend as you bigoted people put it, has been proven to exist more than your global warming religion.
Really? I think I have missed the evidence. Would you be kind to put some references?
Still we cannot even read a website, purporting to relate to technology news, a completely secular subject, without finding these beliefs being forced into our eyeballs and down our throats. The level of anguish experienced at these events can not be expressed without resorting to expletives.
Oh you poor poor thing and your poor poor feefees. I'll pray for the day when you're no longer hideously oppressed by slashdot comments. We shall overcome.
So...it's easier to determine the encryption key if already have the unencrypted version of a file? Yeah, that's real helpful. You don't really need the key if you already have a decrypted version. Just don't ever leave a decrypted version around and even then, don't use the same key for each file. Problem solved.
Except they figured this out just in time for quantum computers to ruin all encryption.
I'm glad to see you read comments the same way you read the bible: skimming through to find the bit you wanted to see, while ignoring the rest which would invalidate your point.
Is 1563649 a prime number?
You got it wrong. It's money, shopping and momma. If momma aint happy, nobody happy.
Mod me up/Mod me down: I wont frown as I've no crown
Schizophrenic: Calls the voice in their head "Bob the Clown". We medicate them.
Christian: Calls the voice in their head "God". We give them special rights.
You assume I'm theist; that's adorable. You're a sheltered asshole who wouldn't know oppression from a hole in the ground. There are people being tortured, killed, or otherwise being denied basic human rights over religious dogma, and you're crying over that darn anonymous coward quoting some religious shit. You are the equivalent of a tumblr SJ thug crying about being fatshamed while trying to portray it as some human rights issue. Yes, there's a problem, but it's very fucking unlikely you ever came close to even vaguely experiencing it if you're whining about a troll quoting the bible (hook, line, and sinker, by the way). Go fucking cry about it on /r/atheism while countless others are actually suffering from real mental and physical abuse.
Most comment strings are hundreds long on slashdot. Nothing like a complicated word problem to filter the commentators!
A long random encryption key is still Kryptonite to the any code breaking Superman. But what most code breakers rely on is the fact that the longer a code is... the more it needs to be predictable for human recall. Being able to narrow your work load or concentrate it in a direction that will likely bare fruit is the only way to break a long encryption key.
But most research that is "viable" is in getting clues for keys in human behavior, in mistakes in the cryptography engine, and in sneaking in backdoors.
If it takes 10 Billion years to crack proper AES 256 encryption... what does a 50% theoretical reduction in computation time even mean? Nothing.
Here is where the fun begins -----> http://en.wikipedia.org/wiki/Password_psychology
If you want an interesting take on decryption of long keys... look at the studies that predict how much energy would need to be generated to handle said computations.
Then there is the Ethical argument on the opportunities lost by sending super computers on "encryption errands" .
We are at a point in history and in society where people are using their "beliefs" to further their ends of oppressing people who are not attempting to do harm to anyone. We are at a point where we are expected to "respect" other's beliefs even when those beliefs run directly counter to what can be observed by the naked eye, even when the exercise of those beliefs would cause harm to those in the immediate vicinity.
Like I said, skimming through to find the part which agrees with the argument you wanted to make anyway.
Is 1563649 a prime number?
"You can come from both ends and "meet in the middle" of the cipher to gain advantage sometimes."
My understanding, which may be mistaken, is that MITM attacks, or any kind of attacks, on data that has been encrypted with two or more encryption methods are unlikely to be successful. Since the patterns of encryption are different, finding coincidences is unlikely.
I was unable to find good information. Can you tell me where to find useful research?
excuse me for not rtfa
if you include several decodable messages into one encrypted one you get another layer of security but
im sure even kaiser wilhelm knew about this in his day and age
Free speech was meant to be free for all... how can anyone grow up in a nanny state ?