Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

MIT Research: Encryption Less Secure Than We Thought

Soulskill posted about a year ago | from the but-still-pretty-darn-secure dept.

Encryption 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."

cancel ×

157 comments

Sorry! There are no comments related to the filter you selected.

God says... (-1, Offtopic)

Anonymous Coward | about a year ago | (#44567323)

the second.

10:10 By the which will we are sanctified through the offering of the
body of Jesus Christ once for all.

10:11 And every priest standeth daily ministering and offering
oftentimes the same sacrifices, which can never take away sins: 10:12
But this man, after he had offered one sacrifice for sins for ever,
sat down on the right hand of God; 10:13 From henceforth expecting
till his enemies be made his footstool.

10:14 For by one offering he hath perfected for ever them that are
sanctified.

10:15 Whereof the Holy Ghost also is a witness to us: for after that
he had said before, 10:16 This is the covenant that I will make with
them after those days, saith the Lord, I will put my laws into their
hearts, and in their minds will I write them; 10:17 And their sins and
iniquities will I remember no more.

10:18 Now where remission of these is, there is no more offering for
sin.

10:19 Having therefore, brethren, boldness to enter into the holiest
by the blood of Jesus, 10:20 By a new and living way, which he hath
consecrated for us, through the veil, that is to say, his flesh; 10:21
And having an high priest over the house of God; 10:22 Let us draw
near with a true heart in full assurance of faith, having our hearts
sprinkled from an evil conscience, and our bodies washed with pure
water.

Re:God says... (-1, Flamebait)

Anonymous Coward | about a year ago | (#44567369)

Who gives a fuck what you think your imaginary friend said?

Fuck you, fuck your bible, fuck your god ... fuck off.

Re:God says... (-1)

Anonymous Coward | about a year ago | (#44567431)

His imaginary friend as you bigoted people put it, has been proven to exist more than your global warming religion. But I'm sure you will be modded up and he will be a troll.

SLashDolt really sucks these days, WTF this article is another captain obvious.

Re:God says... (-1)

Anonymous Coward | about a year ago | (#44567557)

Both of your examples are utterly retarded nonsense.

Re:God says... (-1)

Anonymous Coward | about a year ago | (#44567727)

If your most productive response to such remarks cannot be more eloquently worded than a spewing of expletives, you may want to consider not bothering to say anything at all in the future when people bring such matters up... since, and I sincerely mean no disrespect here... but it doesn't really makes you sound all that intelligent

What if it is we who are figments of God's imagination, and not the other way around at all?

Re:God says... (1, Offtopic)

SleazyRidr (1563649) | about a year ago | (#44568257)

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.

Re:God says... (1, Insightful)

Anonymous Coward | about a year ago | (#44568329)

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.

Disregard... (2, Funny)

Anonymous Coward | about a year ago | (#44568601)

Any sentences that starts with, "What if it is we..."

Re:God says... (1, Interesting)

another_twilight (585366) | about a year ago | (#44569635)

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.

What does this have to do with Computors? (5, Funny)

For a Free Internet (1594621) | about a year ago | (#44567373)

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.

Re:What does this have to do with Computors? (0)

Anonymous Coward | about a year ago | (#44567679)

I know this is modded into oblivion, but it made me laugh. Lighten up people!

Re:What does this have to do with Computors? (0)

Anonymous Coward | about a year ago | (#44567811)

Yeah, kind of funny, the guy says is an atheist but he believes in a "Free Internet" which is almost like believing in a religion nowadays.

Re:What does this have to do with Computors? (0)

Anonymous Coward | about a year ago | (#44568733)

Read some of his other posts. I like the communist screeds, but they're a little Trotskyist to be too credible today. I don't know if the guy is completely nuts or not, but he has a wonderful troll-y shtick going on. Or maybe I have twisted standards when it comes to appreciating /. comments...

Re:What does this have to do with Computors? (0)

Anonymous Coward | about a year ago | (#44569893)

"The Internet is free" is a religion. "The Internet should be free" is a statement of value. "Jebus got better after his government executed him" is crazy talk. "I wish Jebus had gotten better after his government executed him" is just fine.

good news for NSA (5, Interesting)

minstrelmike (1602771) | about a year ago | (#44567381)

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.

Re:good news for NSA (4, Insightful)

DigitAl56K (805623) | about a year ago | (#44567427)

I severely doubt this is news to the NSA.

Re:good news for NSA (2, Interesting)

BronsCon (927697) | about a year ago | (#44568459)

Shit I'm not even a crypto expert and it wasn't news to me. If you know what part of a stream of data is supposed to look like and you know where in the stream that part of the data should be, you can attack that part of the stream to determine at least a portion of the decryption key. From there, you try the partial key at set intervals within the datastream and look for anything else familiar, such as file headers or plain ol' empty space, additional patches of data you can fill in from things you already know. Lather, rinse, repeat, until you have the whole key.

Re:good news for NSA (5, Informative)

Shaiku (1045292) | about a year ago | (#44568841)

I read the article. The impression I got was that it will still take the same time today that it would have taken yesterday to break encryption, but it turns out that the metric used to demonstrate an algorithm's effectiveness at hiding information was inadequate for electronic communication. In a nutshell, the latest math explains that most encryption systems are vulnerable to side-channel attacks, even if you might not have realized it. But side-channel attacks have been employed for a long time, so those who do security already knew this anecdotally.

Re:good news for NSA (5, Insightful)

doublebackslash (702979) | about a year ago | (#44569075)

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 (3, Insightful)

blincoln (592401) | about a year ago | (#44570357)

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 (1)

intermodal (534361) | about a year ago | (#44567437)

This is hardly news at Fort Meade. If we're hearing about it now, the NSA probably has had the same knowledge for years.

Re:good news for NSA (5, Interesting)

Anonymous Coward | about a year ago | (#44567587)

Maybe, maybe not. Consensus has shifted, and many researchers no longer believe that the NSA has the best and the brightest, or that they possess much fundamental cryptographic insight not already available to civilian researchers.

When the NSA tried to sneak a back door into an optional random number generator specified in a recent NIST specification, they were almost immediately caught by academics. http://en.wikipedia.org/wiki/Dual_EC_DRBG

On the other hand, operationally they're clearly second to none. Security engineering and penetration involve much more than basic mathematical insight.

Re:good news for NSA (1)

Anonymous Coward | about a year ago | (#44567807)

On the other hand, operationally they're clearly second to none. Security engineering and penetration involve much more than basic mathematical insight.

Edward Snowden proved the first point wrong and the second point right.

Re:good news for NSA (5, Funny)

minstrelmike (1602771) | about a year ago | (#44568005)

When the NSA tried to sneak a back door into an optional random number generator specified in a recent NIST specification, they were almost immediately caught by academics. http://en.wikipedia.org/wiki/Dual_EC_DRBG [wikipedia.org]

They probably should have taken lessons from Xerox if they wanted to embed random numbers in documents.

Re:good news for NSA (2)

lgw (121541) | about a year ago | (#44569571)

I'm not sure what the intent was with Dual_EC_DRBG! It's a bit silly to believe it was "sneaking in a backdoor" because (1) people figured it out using techniques the NSA knew were public, and more importantly (2) the dang thing is so slow there's no way anyone ever would have used it in the first place.

The first you can argue was NSA arrogance, but the second? The second is just weird. I could believe the NSA trying to sneak in a backdoor, but one that obviously no one would use? I don't even?

Times have changed (3, Interesting)

Anonymous Coward | about a year ago | (#44567763)

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.

Re:good news for NSA (3, Informative)

Bob the Super Hamste (1152367) | about a year ago | (#44567493)

But at the same time

It’s still exponentially hard

.

Re:good news for NSA (3, Insightful)

MarkvW (1037596) | about a year ago | (#44567651)

And, if you let them, the NSA will be owning exponentially expensive taxpayer-funded stuff that is then used to spy on taxpayers.

Re:good news for NSA (2, Insightful)

Anonymous Coward | about a year ago | (#44567501)

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 (4, Funny)

freeze128 (544774) | about a year ago | (#44567927)

Good! If it gets exponentially closer, that means it will never arrive!

Re:good news for NSA (2)

camperdave (969942) | about a year ago | (#44568383)

Um... Zeno died of an arrow wound trying to prove that.

Re:good news for NSA (5, Funny)

VortexCortex (1117377) | about a year ago | (#44569161)

Um... Zeno died of an arrow wound trying to prove that.

"I used to believe in an infinitely divisible universe like you,
then I took an arrow in the knee."
- Zeno

Re:good news for NSA (2)

nospam007 (722110) | about a year ago | (#44568013)

This works only if the content is only encrypted _once_.
If you encrypt it twice, there will be no correlation, no recognizable content.

Re:good news for NSA (0)

Anonymous Coward | about a year ago | (#44568151)

One more reason to like the forward thinking of truecrypt allowing you to use different ciphers at the same time.

Re: good news for NSA (1)

jd2112 (1535857) | about a year ago | (#44568369)

That is why I always double encrypt everything in ROT-13.

Re:good news for NSA (1)

dog77 (1005249) | about a year ago | (#44570483)

Hide the encryption algorithm used in the inner encrypted data and it will be even more difficult to find a correlation.

Just Great (5, Funny)

Anonymous Coward | about a year ago | (#44567415)

Just great, Now instead of 100 Quintillion years, it's only going to take 100 Trillion years to decrypt my porn

Re:Just Great (4, Funny)

Anonymous Coward | about a year ago | (#44567541)

I have changed my key from '1234' to '123456' to mitigate this...

Re:Just Great (0)

dgatwood (11270) | about a year ago | (#44567695)

That's amazing! I've got the same combination on my luggage!

Re:Just Great (0)

sinij (911942) | about a year ago | (#44567713)

It must be your birthday!

Re:Just Great (0)

UltraZelda64 (2309504) | about a year ago | (#44567817)

I know, which is why I use the code 12345678: to be different and have a combination that is harder to guess because no one else would have imagined it. Ever.

Re:Just Great (1)

Anonymous Coward | about a year ago | (#44567971)

you're not funny. just stop trying.

Re:Just Great (0)

Anonymous Coward | about a year ago | (#44568333)

All Hail President Skroob!

Re:Just Great (0)

Anonymous Coward | about a year ago | (#44567747)

Jokes on you, they just cured death.

Huh? (3, Insightful)

Black Parrot (19622) | about a year ago | (#44567425)

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:Huh? (5, Interesting)

Arker (91948) | about a year ago | (#44567517)

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.

Re:Huh? (3, Informative)

Anonymous Coward | about a year ago | (#44567631)

There is no "cipher equivalent", unless you're doing something stupid like using ECB mode. [wikipedia.org]
No modern encryption scheme works by simple one-to-one substitution; you use a nonce [wikipedia.org] or an IV [wikipedia.org] with a chaining mode so that even if the same plaintext appears several times, either in the same document or over multiple messages, it will "never" (neglible chance) encode to the same value twice.

Re:Huh? (1)

sinij (911942) | about a year ago | (#44567683)

Without getting into boring details, as poster above mentioned, it is ensuring correct implementation of known secure algorithms that is important. Not entropy or some other pseudo-scientific attempt to get a shortcut to tenure.

Short of breakthrough in quantum computing modern crypto is secure. If you are using AES-256 or anything else FIPS certified - you are still going to be OK.

Re:Huh? (1)

Anonymous Coward | about a year ago | (#44568349)

The parent is absolute balderdash! Entropy is not pseudo-scientific. Short of one-time pads, there is no perfectly secure algorithm since all we do know is that no computationally simple inverse for many trapdoor functions in the open literature. For all you know, someone might have figured out a way to invert Feistel networks efficiently and is quietly stealing billions of dollars. The only known way to measure resistance against information-theoretic (but not purely theoretical) attacks is using information-theoretic tools, and entropy is the fundamental concept of information theory. Entropy is the basis on which all modern communication methods are designed, including whatever medium you are using to transport this comment from Slashdot to your device.

And Prof. Medard does not need tenure; look up her bio.

Re:Huh? (1)

lgw (121541) | about a year ago | (#44569625)

Shannon entropy and unicity distance [wikipedia.org] has more to do with provably unbreakable system than practically unbreakable. Why is a one-time pad unbreakable (assuming a good RNG)? When can a shorter key be unbreakable? What's the minimum key length needed to make an ideal cypher unbreakable for a given plaintext? Why is compression before encryption so important, how exactly how important is it?

Purely academic questions like this are mocked by engineers in every field, but it's that sort of pure research that leads to the breakthroughs that you just can't get from incremental refinement of what's proven to work.

Re:Huh? (0)

Anonymous Coward | about a year ago | (#44567653)

So not quite as bad as it sounded then.

Initially, it sounded like if they know a particular file is on your HDD (say, a funny cat GIF), and they have a copy of the unencrypted version of that file, then it becomes easier to decrypt the entire HDD. But if I understand what you are saying correctly, they would also need to know where on the HDD the encrypted version of the funny cat GIF is.

Some plaintexts can be guessed (0)

Anonymous Coward | about a year ago | (#44570271)

they would also need to know where on the HDD the encrypted version of the funny cat GIF is.

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?

That's why you shouldn't use plain text (4, Funny)

NotQuiteReal (608241) | about a year ago | (#44567689)

Use Word! Those zippy-looking XML-ish .docx files are all messed up!

Re:Huh? (2)

Speare (84249) | about a year ago | (#44567839)

If you want a visual analogy that works, think of the "WOPR guesses launch codes" scene in War Games. In that movie, it's really just eye candy to drive tension in the plot, but it works in that general way for larger texts. If WOPR could somehow compute or infer that the third digit of the launch code is A, and can't be any other letter, then it "locks" that digit down and looks for other inferences it can make. Code breaking and sudoku overlap here too.

Re:Huh? (-1)

Anonymous Coward | about a year ago | (#44567869)

This is a general problem with fancy-pants mathematicians, they see a formula and thinks that they understands it. The result is insane amounts of misapplied statistics, crackpot theories like the wormhole theory and a bunch of dead ends in QM.
Never let a pure mathematician do work unsupervised.

Re:Huh? (1)

Morpf (2683099) | about a year ago | (#44567519)

Well actually: If you guessed one bit correctly and you knew this, you would have made the problem half as easy. But maybe I just understood you wrong, so feel free to correct me. ;)

Re:Huh? (1)

sinij (911942) | about a year ago | (#44567613)

This has to do with theoretical vs. practical attacks against algorithms. Crypto algorithms evaluated based on concept of existential forgery, meaning that adversary can establish some correlation between encrypted message and truly random message. We are talking q2^128 for most cases. This does not mean that practical attack is available, or that it can be effectively computed.

Re:Huh? (5, Informative)

Trepidity (597) | about a year ago | (#44567701)

As usual, the paper [arxiv.org] 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 [wikipedia.org] lead to too-strong claims, compared to a more precise analysis.

Re:Huh? (5, Funny)

Hatta (162192) | about a year ago | (#44567907)

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.

Interesting times (3, Insightful)

DigitAl56K (805623) | about a year ago | (#44567489)

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:Interesting times (1)

DigitAl56K (805623) | about a year ago | (#44567499)

their/there, before the gn's jump all over me for a typo ;)

Re:Interesting times (3, Funny)

nigelo (30096) | about a year ago | (#44567851)

There, there - They're there.

FUD (3, Interesting)

sinij (911942) | about a year ago | (#44567491)

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.

Re:FUD (0)

Anonymous Coward | about a year ago | (#44567729)

This isn't about brute force, this is about partial plaintext matching. What it really means is that plaintext matches are an even greater vulnerability in encryption than previously assumed. This also confirms that full-drive encryption of an OS drive is barely better than an empty admin password when it comes to security.

Re:FUD (2)

sinij (911942) | about a year ago | (#44567809)

>>>This also confirms that full-drive encryption of an OS drive is barely better than an empty admin password when it comes to security.

This is an absurd claim.

There is no such thing as "plaintext matching", you probably thinking about CPA (chosen plain text attack). Things like nonce, CBC and random IV make sure that such matching impossible.

Re:FUD (0)

Anonymous Coward | about a year ago | (#44567847)

Every HDD encryption program I know of uses some type of way to ensure that one sector of text that is known won't help much.

XTS-AES in TrueCrypt is one example. If I know sector 45 is all zeroes, it means squat to decode data on sector 44 or 46.

Yes, some encryption programs still use ECB mode, but again, some encryption programs stash the password in some obfuscated part of the machine so they can auto-encrypt files.

Yes, the randomness is an attack, but with modern NIST algorithms, it has long since been dealt with.

Re:FUD (0)

Anonymous Coward | about a year ago | (#44567773)

So....your saying it's silly that government IA regulations stipulate that we need to use a 15 character passwords on all the systems we work with and requires so many special character classes to pass complexity validation that anyone short of a savant needs to write them down to remember them?

Re:FUD (3, Insightful)

Anonymous Coward | about a year ago | (#44567853)

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:FUD (1, Interesting)

sinij (911942) | about a year ago | (#44567901)

This isn't dismissive hand wave. What they discovered is a marginal concern, especially when dealing with on-the-way-out algorithms (e.g. 3DES). Authors are FUDsters not because what they discovered is false, but because they are making huge deal out of it, and some illiterate CIOs within government circles listened and redirected resources to mitigate this non-issue.

Re:FUD (2)

c0d3g33k (102699) | about a year ago | (#44568129)

This isn't dismissive hand wave. What they discovered is a marginal concern, especially when dealing with on-the-way-out algorithms (e.g. 3DES).

"Dismissive hand wave" refers to your terse dismissal and accusations of FUD while providing nothing more than personal opinion as evidence. If there is a basis for your assertions, prove it with links to actual proof that this is nothing.

Authors are FUDsters not because what they discovered is false, but because they are making huge deal out of it, and some illiterate CIOs within government circles listened and redirected resources to mitigate this non-issue.

You must be in the field, then, and have inside knowledge. You come across as someone who is offended by the behavior of attention seeking scientific peers and are calling them out. Fine. But the MIT research article and the paper it describes don't support your claims - they appear to be a typical report of interesting research by MIT researchers and a fairly typical scientific paper. They don't seem to be making a huge deal out of anything. So your assertions must be based on additional information that we don't know about. If there is evidence to support your accusation of FUD and 'making a big deal', show us why you believe this is true. Otherwise you're just some /.er throwing out insulting accusations. Back those accusations up with something substantial and we might all learn something useful.

Re:FUD (1)

lgw (121541) | about a year ago | (#44569671)

It's quite unlikely the authors "are making huge deal out of it". Never, ever confuse the journalist writing about science with the scientist.

Re:FUD (1)

sinij (911942) | about a year ago | (#44570457)

I am not. This is being made a huge deal out of right now by people who matter (but shouldn't) since about three years ago. This paper isn't even the first time academics parade this flavor of red herring, this why I find this specific instance so annoying. Insufficient entropy for random seeding my foot. We know how to seed, have done it for decades without any issues. Now they want to see formal analysis of this (and nothing else). How is that going to result in better cryptography?

Re:FUD (0)

Anonymous Coward | about a year ago | (#44568085)

We are still talking ^n where to bruteforce N >>> heat death of universe

You shouldn't assume the worst case for the attacker. While it's not likely to happen, it's entirely possible they guess it correctly on the first try.

The paper is a little esoteric and hard to explain to non-math types, but essentially what it means is that there are ways to reduce the theoretical average time-to-crack in specific situations. One example they give is that by altering localized noise around an RF card reader, forcing re-transmission of the coded message, the attacker can gain a slight advantage because of how some encryption systems use entropy in their key generation.

Another example which is much more relevant to most people, is the paper offers a mathematical proof that using any real word in a password causes a reduction in the worst-case time to crack. In layman's terms it's because an attacker can make an educated guess about what the next character in the password is based on a statistical analysis of the language the word is from.

So if casual readers take anything away from the paper and article, it is this: Never, ever, use a real word in a password. Passphrases are plain and simple bad practice all around. Never, ever attempt to make up your own password, because humans suck at doing that.

Key Size implications (0)

Anonymous Coward | about a year ago | (#44567537)

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.

Re:Key Size implications (5, Interesting)

Em Adespoton (792954) | about a year ago | (#44567925)

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.

Three words... (1)

jettoblack (683831) | about a year ago | (#44567575)

Cooty Rats Semen

(If you don't get it, you need to see: http://www.imdb.com/title/tt0105435/ [imdb.com] )

Re:Three words... (0)

Anonymous Coward | about a year ago | (#44568253)

"I want peace on earth and goodwill toward men."
"We're the United States Government! We don't do that sort of thing."

Great movie.

Lets see it (0)

Anonymous Coward | about a year ago | (#44567585)

Pics or it didnt happen

Its all about buying more time! (1)

globz (2832793) | about a year ago | (#44567603)

Cryptop = buying time

University of Ireland is gibberish (3, Informative)

Anonymous Coward | about a year ago | (#44567611)

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".

Common mistake. (5, Interesting)

Hatta (162192) | about a year ago | (#44567649)

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.

Re:Common mistake. (0)

Anonymous Coward | about a year ago | (#44567827)

The obsession with averages and normal distributions will be remembered as a blemish on 20th century science.

Re:Common mistake. (1)

jkflying (2190798) | about a year ago | (#44568205)

So they forgot to take into account that the median seed had to compete with a bunch of other seeds, while the farthest seed didn't? Sounds like shoddy prediction work to me.

Re:Common mistake. (0)

phantomfive (622387) | about a year ago | (#44568557)

Think of that every time you read a prediction about global warming. Especially when you find someone who believes that scientists can predict everything about climate, because hey, it's Science.

Compression first (1)

kwerle (39371) | about a year ago | (#44567687)

Isn't this (one reason) why any good encryption system compresses what it is encrypting first? To maximize the data's entropy?

Re:Compression first (0)

Anonymous Coward | about a year ago | (#44567981)

Compression doesn't increase entropy.

Re:Compression first (1)

kwerle (39371) | about a year ago | (#44569383)

http://en.wikipedia.org/wiki/Entropy_(information_theory)#Data_compression [wikipedia.org]

If a compression scheme is lossless—that is, you can always recover the entire original message by decompressing—then a compressed message has the same quantity of information as the original, but communicated in fewer characters. That is, it has more information per character, or a higher entropy. This means a compressed message is more unpredictable, because there is no redundancy. Roughly speaking, Shannon's source coding theorem says that a lossless compression scheme cannot compress messages, on average, to have more than one bit of information per bit of message. The entropy of a message multiplied by the length of that message is a measure of how much information the message contains.

Re:Compression first (0)

Anonymous Coward | about a year ago | (#44568091)

No, it gives away the amount of "information" in the encrypted object, which has been used to extract for example the timing of pauses in VOIP and from that guess words.... if you want to do this the least you must do is then pack to set size before encryption which probably defeats the point...

Re:Compression first (0)

Anonymous Coward | about a year ago | (#44570191)

In VOIP case, compress-then-pad still make sense as even after padding to largest possible frame size, it is still much smaller than original data. Well, alternatively you can switch compression to CBR mode, instead of VBR mode (and, of course, disable any silence detection); it will likely also save some CPU cycles.

Re:Compression first (0)

Anonymous Coward | about a year ago | (#44570087)

No. (Properly used) modern crypto is completely safe against known/chosen plaintext attack, there are no need to hide any irregularities/known pattern/signatures in plaintext. Knowing them won't help attacker even a bit.

Only reason to compress-before-encrypt is that compress-after-encrypt just won't work (compression algorithms won't be able to see any patterns in ciphertext). It's to save space, not to improve security.

(FWIW, there are even cases when compression can introduce side-channel leak see recent BEAST and CRIME attacks on SSL).

Known or chosen plaintext (3, Informative)

Geirzinho (1068316) | about a year ago | (#44567799)

How is this in principle different from the known plaintext attacks (https://en.wikipedia.org/wiki/Known-plaintext_attack [wikipedia.org] )?

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.

Why make it easy? (0)

Anonymous Coward | about a year ago | (#44567841)

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.

Damn those information therrorists (1)

zAPPzAPP (1207370) | about a year ago | (#44567885)

We'd send our drones after them if they wouldn't hack them and send them back.

Can't they just eliminate the non-uniformity? (1)

Anonymous Coward | about a year ago | (#44567905)

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.

Re:Can't they just eliminate the non-uniformity? (1)

Anonymous Coward | about a year ago | (#44568221)

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?

The point of this paper is that iterated SHA512, or any other cryptographic operation you care to name, doesn't have perfect uniformity, and those deviations from uniformity have a far greater significance than anyone believed.

Whole-disk encryption a bad idea? (2)

Dorianny (1847922) | about a year ago | (#44568261)

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.

Re:Whole-disk encryption a bad idea? (0)

Anonymous Coward | about a year ago | (#44569815)

It depends a lot on how you do the whole-disk encryption. It *has* to be very resistant to chosen-plaintext and known-plaintext attacks, and unless you screw it up, you'll be using one of the feedback modes *especially* designed for disk encription AND a proper ESSIV which will give you good enough resistance.

Don't count on those images saving your ass by still resisting cryptanalysis 50 years down the line, though.

Signitures (0)

Anonymous Coward | about a year ago | (#44568555)

Does this men that by digitally signing an email I'm weakening the PGP encryption?

So what are you saying.... (1)

aztektum (170569) | about a year ago | (#44569755)

'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.

$10,000 offer (1)

slick7 (1703596) | about a year ago | (#44570181)

$10,000 to whomever can break this cypher.

sekg 1408 drnh @$?" xxth bhg9 douche bag

hjmp llmo 3860 ++%# jjgj mmnm muggle

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?