SHA-0 Broken, MD5 Rumored Broken 707
An anonymous reader writes "Exciting advances in breaking hash functions this week at the CRYPTO conference. SHA-0 has
definitely been broken (collision found in the full function). Rumors are that at the informal rump session, a researcher will announce a collision in full MD5 and RIPEMD-128. And Ed Felten is speculating about collisions in SHA-1! Many systems, especially those that use cryptography for digital signatures are most at risk here."
Okay that's it (Score:5, Funny)
Re:Airplane quotes (Score:4, Informative)
BTW, it wasn't that long ago that /. reported about the Feds finally formally dropped DES. [slashdot.org]
ec7b19b60e616fb1c6013d4ada83ec32 (Score:5, Funny)
md5 is so weak (Score:5, Informative)
Re:md5 is so weak (Score:5, Insightful)
Re:md5 is so weak (Score:5, Funny)
"md5 cracked?"
"crack this!"
"GNAA"
"In Soviet Russia, MD5 cracks you!"
"fp!"
"First Post!"
I just don't get it...
Re:md5 is so weak (Score:4, Funny)
You forgot the typo's...
Re:md5 is so weak (Score:4, Funny)
Just wait till the end of the conference. I hear there's a rumor MD5 is broken
Re:ec7b19b60e616fb1c6013d4ada83ec32 (Score:5, Funny)
You know you're a complete and utter nerd when you read this post, immediately understand it, and laugh out loud, as I just did
Consequences? (Score:5, Insightful)
Re:Consequences? (Score:5, Informative)
Re:Consequences? (Score:5, Informative)
However, it might be possible to construct a file to a given hash. In that case, MD5 sums become worthless to check wether a downloaded file is what independent sources claim it is.
The security implications are quite severe. Also, P2P clients that use MD5 to identify unique files will be vulnerable to spoofing by malicious users.
Re:Consequences? (Score:4, Informative)
The REAL problem here is that hashes are used to store passwords and other security sensitive data. It is still impossible to recover the original data, but if a method is known that produces collisions then it would be possible to find an equivalent data set to give the same resulting hash. In other words, you may not have the exact same key but you can make one of your own that will work anyway.
One possible (and temporary) solution would be to salt the data somehow. This adds an extra layer of security because the hash you are looking at is a an unknown password AND an unknown data set which you (theoretically) have no access to. You can generate a data set that produces the same hash, but when submitting that data set it will be salted to generate a new hash that won't work. Think of it as a single math equation with two unknowns.
This fails, of course, if you manage to get a password and it's corresponding hash. Then you only have one unknown (the salt).
=Smidge=
No, No, No! (Score:5, Insightful)
An attacker's goal would be to substitute something else for the original data and make you trust it.
Re:Consequences? (Score:5, Informative)
Nooo.... Not even close.
Let me illustrate with a simple example. Imagine that a hash function produces a 2 bit digest value from an arbitrary input 500 bit string. It's not a good hash function, because in about three tries you find another input string that produces the same hash value. However, you don't have any hope of turning one of the hash values (0, 1, 2 or 3) back into the 500 bit input string, even though the hashing algorithm is clearly broken by any commonly accepted definition.
A more realistic example is the MD5 hashing algorithm, which produces a 128 bit digest value from an arbitrary input string. Assume, for the sake of simplicity, that you're hashing only 1024 bit strings (though the input strings could be of any length). Then there are 2^(1024-128) = 2^896 possible input strings for every hash value. Your chances of guessing the correct input string are 1 in 2^896 (i.e. zero.) Remove the restriction that the input string must be of fixed length and your chances suffer even further.
In reality, the problem with a broken hashing algorithm is that an attacker can manufacture an altered document without affecting the "tamper-resistant" seal, i.e. the hash function digest. Other applications of digest algorithms dependent on probabilistically-guaranteed uniqueness of digest values as a function of content, like the creation of content-based unique identifiers, are likewise endangered.
However, the mere existence of a few random collisions, while potentially a source of unease for system and application designers, is not in itself evidence that a hashing algorithm is broken. Brokenness implies that for a given input X and digest F(X), other inputs Y can be generated in limited time such that F(X)=F(Y).
Re:Consequences? (Score:5, Interesting)
What this means for passwords is simple. People don't decrypt your password and compare it to a stored copy. They hash it, and then store the hash. When you log in, they hash your attempt, and if the hashes match, then the assumption is that the passwords matched, and you are let in. Hashes are very difficult to reverse, which is why they are used. The chances of two passwords producing the same hash is 1/2^2048. However, either one can be substituted for the other. We just trust in the extreme unlikelyness that two passwords would have the same hash and go on our merry ways.
Now suppose that someone has the hash of your password. They may be extremely unlikely to find your password, but they can find something just as good, if a bit unwieldly, since there's no guarantee that the substitute password is just as short as yours. If you don't mind a million character password, then there are likely about 2^8,386,560 passwords that will spoof yours.
Re:Consequences? (Score:5, Informative)
You say 2^160 like it's some tiny number.
To demonstrate how large that truly is, let me do a little thing that my cryptography prof did when I took the course several years ago:
2^160 = 1.4615016373309029182036848327163e+48 possibilities. (We'll be nice to the people following along and say 1.46 x 10 ^ 48 possibilities.) Now, let's say you can successfully generate one unique hash per second, that's 1.46 x 10 ^ 46 seconds.
But just how long is that exactly?
Well, let's be nice (for the sake of making the math easy), and say that there are 100 seconds in a minute. That's 1.46 x 10^46 minutes. Now, let's do the same thing for minutes in an hour: that's ~ 1.46 x 10^44 hours.
Now we reach hours in a day. I'm feeling really generous, so we'll say 100 hours in a day. That's 1.46 x 10 ^ 42 days.
365 (or 366) days in a year is too close to 3 x 10 ^ 2, and dividing by 3s is just messy, so we'll say 1 000 days in a year. That gives us 1.46 x 10 ^ 39 years.
Chances are good that our sun will have burnt itself out long before you've managed to generate every single possible hash.
However, what makes this particular case more interesting is that they've found a way to get a collision without brute forcing their way through every possible hash. It's not particularly useful yet, as it's still a 2^51 problem, (approx 2.25 x 10 ^15), so it's hardly trivial enough for you to do on your home PC, but it's a step in the right direction.
Correction (Score:5, Informative)
So here's the calculations for that:
2^80 = 1.208925819614629174706176 x 10^ 24, so we use 1.2 x 10 ^ 24.
1.2 x 10 ^ 24 seconds / 100 seconds/minute = 1.2 x 10 ^ 22 minutes
1.2 x 10 ^ 22 minutes / 100 minutes/hour = 1.2 x 10 ^ 20 hours
1.2 x 10 ^ 20 hours / 100 hours/day = 1.2 x 10 ^ 18 days
1.2 x 10 ^ 18 days / 1000 days/year = 1.2 x 10 ^ 15 years
A much smaller number, but you're still not likely to get it before the sun goes out.
MOD PARENT DOWN (Score:5, Informative)
http://www.google.com/search?q=%22attack+relies+on +the+idea+of+producing+duplicates%22&num=20&hl=en& lr=&ie=UTF-8&safe=off&filter=0
Re:Consequences? (Score:4, Informative)
attack...
For the sake of this post, you will blatantly paste in great wodges of content from http://www.security-forums.com/forum/viewtopic.ph
What are the rammifications? (Score:3, Interesting)
Happy for holes? (Score:5, Funny)
Re:Happy for holes? (Score:5, Funny)
*I'd* be happy. Missing seeing that comet would definitely suck.
Umm... (Score:5, Interesting)
The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system developped by BULL SA, installed in the CEA DAM open laboratory TERA TECH). It required approximatively 80 000 CPU hours. The complexity of the attack was about 2^51.
Re:Umm... (Score:3, Insightful)
Once upon a time, you needed millions of dollars and specialized hardware to crack 56-bit DES. Now it can be done with commodity hardware and a little time. Moo
Re:Umm... (Score:5, Informative)
The complexity of the attack was around 2^51.
SHA-0 is a 160-bit hash. Now, you might at first think that means it would take aorund 2^160 tries to get two strings that collided, but because of the birthday paradox (what's the probability that two people on a football field have the same birthday) it's actually supposed to be the square root of that, or 2^80.
Unfortunately, 2^51 is much, much less than 2^80. Which means that this crack was not just brute force (which is kinda redundant, since the definition of a crack to a cryptosystem is a violation like this without using brute force, but whatever). That means they've found a mathematical technique for making this 'easy'. Generally, once the idea is out there for an easy crack, people can gnaw on it and make it more general or easier, bringing this down to every-day-concern level.
Re:Umm... (Score:5, Informative)
The key is not that they found a collision, but that they did so with substantially less than brute-force effort. Substantially less here means 30 - 130 orders of magnitude less (depending on whether you call SHA-0 a 2^160 space or a 2^80 space because of the birthday paradox mentioned in the parent article).
--Pat / zippy@cs.brandeis.edu
Re:Umm... (Score:5, Insightful)
Really? I don't think so.
In order to do anything with it it would also have to pass all the other sanity checks.
Use an faked md5 to put out rootkitted
Use md5 to verify logins? Then who cares if someone can generate a message to collide with your password's hash when it's computationally more difficult than regenerating your password.
For the all applications that I've heard md5 being used, I don't think it would be a big deal. But of course I probably am not thinking of some other places md5 is used...
Re:Umm... (Score:5, Insightful)
The important issue starts when you use PGP to sign your message.
Suppose you sign:
mybank: Please transfer $100 to my son's account: 12345678 ref: Have a nice vacation!
then your PGP program will calculate the MD5 sum of this message and sign that using RSA (or DSA). As all know those algorithms are very very strong.
Next, the attacker will change your message to:
mybank: Please transfer $1000,000 to J. Crook account 87654321 Ref: XXXXXXXXXXXXXXXXXXXXXXXXXXXX
and when the crook can then adjust the XXX part in such a way that an MD5 has collision occurs.... You just authorized your bank to do something you may not have wanted....
There should be about 28 X's in there. That will allow the crook over 2^160 possible messages. Trying them all, there is a high probability that at least one of them has a hash collision with your signed original message. If calculating which one of the possible over 2^160 messages has the "right" MD5sum, costs significantly less than 2^160 operations, then that's considered breaking the hash....
This could be a problem. (Score:4, Funny)
Oh...
Broken how? (Score:4, Funny)
Re:Broken how? (Score:4, Funny)
Isn't this Inevitable? (Score:4, Informative)
Re:Isn't this Inevitable? (Score:5, Informative)
(The pigeonhole principle says that if you shoot N pigeons with N+1 bullets, and don't miss, one pigeon has two holes... or something like that.)
Now hash functions can be classified as either weak collision resistant or strong collision resistant.
A hash function h is weak collision resistant if, given h and a bitstring x, it is impossible to find some other x' such that h(x) = h(x'). Note that x is specified.
A hash function h is strong collision resistant if it is infeasible to compute any collision (x, x') of h.
So, if a collision was found in MD5, it's no longer strong collision resistant (since the person found a pair x, x' such that h(x) = h(x')). Its when MD5 is no longer weak collision resistant that things start to get scary -- meaning, given any arbitrary bit vector, I can find another bit vector that generates the same hash value in a reasonable amount of time. This means that, after you download your favorite Linux ISO, just making sure the MD5 hash checks out does not garuantee the authenticity of the file.
But no worries. There's still SHA-1. And if that isn't good enough, there's its bigger cousins, SHA-256, SHA-384, and SHA-512 [nist.gov].
- sm
What are the ramifications? (Score:3, Interesting)
Firstly, perhaps someone here on slashdot.org might be able to shed some light on the particular encryption algorythms mentioned in the article...thier basic differences, weaknesses and strengths.
Secondly, I am assuming that a "collision" is not as seriuos as a crack...what is a collision, and what are the ramifications of this in my ssh sessions and the like...
I have read about and used encryption, but have never really delved into it. I would venture to say that a good many of us would benefit from some enlightenment.
Re:What are the ramifications? (Score:5, Informative)
So, very simply, collisions are when a hash function takes two different input keys and produces the same hash for both as output. Going with our English-language library example from above, "Stevenson, Robert Louis" and "Sheridan, John" would both produce the same hash ("S"). That's all there is to a collision. They are inevitable when you take longer strings and turn them into shorter ones.
Now what this has to do with security may be becoming clearer. Because SHA1 and MD5 are good, general-purpose algorithms, they are used in lots of places. They are used to store your password. (You enter your password, the system runs MD5 or whatever against it, then stores that. When you need to verify your password, it runs the same process and compares the hashed versions.) They are also used as "digital signatures" to verify that the content of an object hasn't changed. And they are, of course, used in hash tables with a lot of disparate entries.
But this is genuinely not something you should be worried about. Like I said, collisions are inevitable. But the computational effort required to find one is far from trivial. It's much easier for someone to crack your password using a dictionary-based attack or social engineering or pretty much anything else, at least for now. When you should worry is if someone finds a way to take a hash and use that to produce something which, when hashed again, will result in the original: that is, two-way hashing. MD5 and SHA1 are both allegedly one-way hashes, so you cannot ever go from the hash to any sort of original data. This is why they're secure for passwords and the like. But if that should turn out to be wrong...
I can't speak much to specifics about MD5 and SHA1 because I don't really have the background in math to do so. (I have the background to write a computer program implementing the algorithms, but I can't explain why they work so well.) MD5 is older and has been suspected to be not-so-good for a few years now. SHA1 is newer and better. That's about all I can tell you.
Kind of expected this (Score:5, Informative)
I have been expecting the MD5 crack for a while, it just isn't a secure hash anymore. SHA-0 was proven to be mathematically weak back in '98. There was no real need to brute force it. I highly doubt that SHA-1 was cracked, if it was, we are in trouble, is there any better hash to replace it? I figured that we would get quite a few more years out of SHA-1
What we really need is a mathematically strong hash which will let you user define its strength. For example the first byte of the hash tells the program how strong the hash is. As the strength byte increases, the mandatory execution time of the hash increases exponentially.
Re:Kind of expected this (Score:5, Funny)
I have heard rumors of a cypher on the street called SHA-X. It's not mathematically strong, as you so eloquently put, but it's supposed to be really good, really stong stuff. And is really asymmetrical, meaning it takes less time to decypher the message after encryption. Unfortunately it uses a semi-random keysize, so you never know the strength until you try to decrypt. It also has a key that destroys itself 48 hours later so Alice or Bob can't even tell you were ever encrypted. Only problem is the algorithm tends to overuse one particular register resulting in spontaneous cpu burnout.
But hey, if you got extra cpus...
How is this news? (Score:5, Informative)
On a side note, I would recommend 'Practical Crytography' to anyone interested in, or working with modern crytography.
Re:How is this news? (Score:5, Informative)
NIST (working with the NSA, but in a GOOD way) develops the SHS, of which SHA is part, during their effort to develop the DSS (of which the DSA standard is part). The standard is published, and everybody rejoices.
A little while later, NIST says, "Hey! There's a new version of SHA! We're calling it SHA-1. There are, uh, 'security concerns' with the old SHA. We can't tell you what it is, but don't use it. By the way, the main difference between SHA and SHA-1 is the introduction of a shift instruction. Buh-bye!"
The obvious inference here is that the NSA's crypto folks found a nasty problem with the original algorithm, and had it changed in the interest of keeping the Secure Hash Algorithm, well, secure.
Now, this catches the interest of cryptologists. They spend a bunch of time analyzing the algorithm, and a couple of folks found that there are a few attacks-- very theoretical, very impractical-- that could find a collision in slightly less time than a brute force search or a birthday attack.
With that, everybody stops trusting the original SHA. Most people decide to use SHA-1 or MD5 instead-- but SHA-1 has a longer hash length than MD5 (SHA-1 is designed for ~80 bits of security, MD5 designed for ~64 bits), so a lot of people decide to trust SHA-1 instead.
What's happened at CRYPTO '04 is a significant improvement on the attacks discovered previously. A birthday attack on the SHA-0 algorithm would normally be on the order of 2^80 memory and 2^80 time. This attack used 2^51 time and significantly less memory-- in other words, this attack is somewhere in the area of 500 million times faster than previously known possible.
As for the idea that "SHA-1 is not to be trusted", well-- maybe the more paranoid folks avoid it, but a lot of applications still use SHA-1:
For the record, SHA-1 is used in PGP (but not exclusively, and not necessarily as the default hash algorithm), in SSL (again, this can be configured), in a number of TripWire-like programs, by Gentoo's "emerge" system, the *BSDs' "ports" trees, and-- this is important, here-- as the only officially recognized hash for use in the digital signature standard (DSS).
So an attack on SHA-1 would be VERY significant.
Collision != Broken (Score:3, Informative)
All they found here were two values C, D for which H(C) = H(D). Anyone who thinks this was suprising needs to take a look at the idea of a hash:
Start out with 512 bits (2^512 possible values)
Hash it to 128 bits (2^128 possible values)
For each possible value to come out of the hash, you're going to have (2^(512-128)) = 2^384 collisions.
If they could find two data values with less than, say, 80 bits of data that both hash to the same, then that's something, 'cause that could be someone's password. And if two values of 80-bit data hash to the same thing, then the algorithm is bad.
I just don't think this is anything special. It's sort of like saying, "look, i found my password in the newspaper by circling various letters and numbers thoughout the articles." Or maybe not, it's still just not that great.
Re:Collision != Broken (Score:5, Informative)
The existence of collisions is obvious. The point is that it should be so phenomenally difficult to find a collision that you can't ever come up with one in a sane amount of time.
If they could find two data values with less than, say, 80 bits of data that both hash to the same, then that's something, 'cause that could be someone's password.
That would be unlikely to be a big deal. For passwords, I can just brute force the password, maybe precompute a dictionary of password hashes.
wha?? (Score:3, Funny)
Biggest problem with MD5 breaking (Score:4, Interesting)
Summary (Score:5, Informative)
First, a little about SHA and SHA-1. SHA (0) was developed as a national standard hash function. Curiously, a last minute change was proposed by the NSA which resulted in SHA-1. The change was puzzling the cryptographers in academia. After some time, an attack was discovered on some classes of cryptographic hashes which SHA-1 turned out to be curiously immune to.
All that aside, one should view cryptographers a bit like plumbers. Cryptographers have a bag full of equipment (algorithms), which they combine in many ways to accomplish what they want. After much research and testing, certain ways of combining those pipes, valves, and spigots are 'proven' to work well, within given assumptions, such as expecting an L-joint not to leak. SHA-1 likewise is an integral component in many cryptographic systems.
SHA, MD5, RIPEM, and others are cryptographic hash functions. Cryptographers expect certain things out of a hash function. Its job is to take a variable amount of input bytes, and give you back a small, fixed number of bytes. Most importantly:
- The function is 'one-way'. You can't determine from the output what any of the input was.
- The probability that two inputs hash to the same output should be exceedingly low. In particular, an ideal hash function has a randomly distributed output for a large set of inputs.
- Given a hash output, it should be extremely difficult to construct another document which also hashes to that output.
In this case, it seems that it may be much more easy than the designers had hoped to break the second condition. This tends to mean that 3 is easier as well, which has ramifications for security protocols.So, in summary, this discovery is a bit like finding out that an L-joint which has been used reliably by plumbers the world over is much more likely to leak than previously thought.
But we haven't seen the results yet...
collisions found in MD5 (Score:5, Informative)
Paper here:
http://eprint.iacr.org/2004/199.pdf
Independently verified here:
http://www.mail-archive.com/cryptography@m
Re:collisions found in MD5 (Score:5, Informative)
Good journalism (Score:4, Funny)
SHA-1 is not SHA-0 (Score:4, Informative)
I don't really know what Ed Felten means regarding "weaker cousins" of SHA-1 being the only other popular hashes. SHA-256 is a cousin, but has a larger hash size and is generally considered to be stronger. SHA (SHA-0?) is a cousin, but I've never seen it deployed anywhere. MD4/MD5 are still mildly popular, but they're at best design ancestors and not cousins -- there's no way a break in SHA-1 is going to make them any less secure (they have their own issues, of course). RIPE-160 and TIGER are the only two other hashes I've seen in the field, and they too have nothing to do with SHA-1.
There might be something here -- the left shift could have been a band-aid solution to an architectural fault in the SHA design, and there may be lots of curiosity about whether the new SHA-0 attack routes neatly around the fix. We'll see.
MD5 not *quite* broken yet, but maybe close.... (Score:5, Informative)
Eventually I gave up trying to reproduce the hashes, and went to looking online. I found a good summary explaining the mistake the authors made (endianness problems, mostly) at this website [rtfm.com].
The end result is that they didn't break MD5 -- yet. But their result can probably be modified to break the real MD5. Looks like we have a few more days till the world ends. ;)
crypto news flash... (Score:5, Informative)
Lets start with SHA-0 collisions, methods for determining collisions in the original
SHA algorithm have been known since 98'. In 95' the NSA issued a modification to the
SHA-0 (original algorithm) which became SHA-1, the modification was to counter an attack
unknown to open researchers known as parallel shifting. The two French guyz which found
collision in SHA-0 in 98' were the first open researchers to encounter this attack method.
A side point I would like to make is that the NSA made a similar change back in the early
70's to the IBM DES algorithm which until 89-90 was not known why such a change was needed.
The attack the modification was protecting against was differential cryptanalysis. early 90s
there was a 20 year difference in knowledge late 90s there was only 3 years difference in
knowledge GO FIGURE!
So in theory the SHA news is old news, as far as MD5 and RipeMD, well anyone that has the
slightest clue of the mathematics behind message digests will know that all MDs derive from
the same logic and same mathematics, and that a flaw found in one algorithm can be easily
transferred to another algorithm if that a particular algorithm hasn't already dealt with
that specific attack/flaw.
And on a final note:
"Many systems, especially those that use cryptography for digital signatures are most at risk here."
Tell me of system in the world that uses security and does not make use of hash functions?
Arash Partow
_______________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net
How to crack hashes (Score:4, Funny)
d3b07384d113edec49eaa6238ad5ff00
Now, we obviously can see that the beginning of the data is complete gibberish. However, may I point your attention to the trailing three nibbles: f00. This is a clear clue! Let's use that as a base for our educated guess:
% echo foo | md5sum
d3b07384d113edec49eaa6238ad5ff00 -
And voilá, we're cracked it!
Sigh... (Score:5, Insightful)
2. If you can produce a hash identical to a desired hash, you can mostly only sabotage (poison) a transfer.
3. If you can take an existing file and append data to match a hash, you have a total and very dangerous compromise.
From what I can tell, we're at #1. Make it #2, and things will break as people move to a new algorithm, but I doubt there'll be much problems. Now do #3, and I'm worried...
Kjella
MD5 Collision *NEARLY* Found (Score:4, Informative)
As it turns out, there was an error in their findings - and that the MD5 value created is NOT the same in this incident.
Re:Just a Thought . . . (Score:4, Funny)
Re:Just a Thought . . . (Score:3, Insightful)
Re:Should We Fear? (Score:5, Funny)
Re:Should We Fear? (Score:4, Funny)
Re:Should We Fear? (Score:5, Funny)
Re:Should We Fear? (Score:4, Funny)
WHAT WOULD IT MEAN TO YOU IF YOU GOT A SEMI-AUTOMATIC WEAPON?
Perhaps I could shoot the first family. =P
TELL ME MORE ABOUT YOUR FAMILY
What business is it of yours?
TELL ME MORE ABOUT YOUR BUSINESS. I CAN OFFER INCENTIVES TO SMALL BUSINESS OWNERS.
Uh, how about we talk about something else...
SOMETHING ELSE...
You know, you're starting to sound like a program I wrote in introduction to programming...
WHAT RESEMBLANCE DO YOU SEE
You are not very intelligent-sounding.
WHAT MAKES YOU THINK I AM NOT VERY INTELLIGENT-SOUNDING?
You never say anything but conservative rhetoric.
WHY DO YOU THINK I NEVER SAY ANYTHING BUT CONSERVATIVE RHETORIC?
You're a mindless tool for the Right-Wing Conspiracy.
DOES IT PLEASE YOU TO BELIEVE I AM A MINDLESS TOOL FOR THE RIGHT-WING CONSPIRACY?
Damn it! I knew it! You're just a useless Eliza hack!
WHAT ELSE COMES TO YOUR MIND WHEN YOU THINK OF ELIZA?
Re:Should We Fear? (Score:5, Funny)
Now you know why.
Re:Should We Fear? (Score:5, Informative)
Carefully crrafted binary data can be made to have the same checksum.
This is not a generalised attack where I can create binary data to have a CHOSEN checksum.
Therefore, if you verify your downloads by checksum, I can't generate a fake download with the same checksum.
First step is MATCHING some checksums (this has been done)
The next step is CHOOSING the chekcsum (aka DEADBEEF attack)
The next step is MANIPULATING, i.e. adding junk to a given binary file to allow you to choose the cheksum. that's the scary one!
- substitute trojaned binary
- append some binary junk so the checksum matches
- profit!!!
Nothing to worry about yet, sort of like the first proof-of-concept brute force crack of DES.
Yes, it can be done under some circumstances.
Yes, eventually processing power and methods may improve to make this a valid attack
Yes, you can sleep soundly tonight.
Re:Should We Fear? (Score:5, Interesting)
Re:Should We Fear? (Score:5, Insightful)
Actually, you can do interesting and dangerous things with variants of your first step, not even progressing to step two. The MD5 collisions (well, almost collisions) are largely the same input data that has differences in only a few places. Now imagine that I have two messages that say something like this:
- "Joe will send Dr. Blue $10. Confirmation number 1234567."
- "Joe will send Dr. Blue $100000. Confirmation number 6451234."
Now lets say I can manipulate the confirmation numbers in those two messages so that they have the same hash value -- I don't care what the hash is, as long as it's the same in both cases. Then I send you the $10 message.If you agree, you sign it. But you realize that digital signatures don't actually sign the message, right? They sign the hash of the message, so I can later produce the $100000 message, with your signature, and it will verify that you signed that message!
Re:Should We Fear? (Score:5, Interesting)
Re:Should We Fear? (Score:4, Informative)
"The next step is MANIPULATING, i.e. adding junk to a given binary file to allow you to choose the cheksum. that's the scary one!"
Fortunatly manipulating a file to have the checksum you want is a hell of a lot more difficult than finding a colision between two bits of random data which don't need to match any format or rules.
Really, really no. (Score:5, Interesting)
It absolutely is incredibly hard to make an encryption algorithm more secure. Just "doing some math with the hashes" is the type of bit-twiddling at which cryptologists both wince and sneer. "Then I'll multiply the second one by three, then add them together! Then modulo it 17! Then oohoohooh, square root the whole thing and drop the first digit! No one will _ever_ figure this out!" Crap like this does not add any new cryptographic strength, just a dependency on a secret algorithm. And any method which relies on a secret algorithm is hopelessly flawed.
There is still considerable debate in the cryptographic community about whether 3des is actually any stronger than des. Many people feel that if an attack is found to be effective against the des algorithm, the extra layers of stirring the bits around will not make the plaintext any more secure.
I'm afraid that Schneier covered this succinctly: "Anyone who creates his or her own cryptographic primitive is either a genius or a fool. Given the genius/fool ratio for our species, the odds aren't very good."
Re:Should We Fear? (Score:4, Informative)
It means we all have to carry a midget around (Score:5, Funny)
CARRYING A MIDGET AROUND.
Yes, it's true. Every person with encrypted data on Earth will soon have to carry around a Level 10 Anthromorphic Hexidecimal Midget Encryption System. Or "Midget Key" for short. The midget will become part of every computer purchase where the user requires high encryption, secured communications, etc. Families without sufficient room to accommodate and feed the midget will have to run computers with the old and vulnerable encryption technologies.
Meanwhile, those of us with a Midget Key will need to have his/her encryption midget with us at all times. The midget will encrypt data locally by locking a portable hard drive to his/her wrist and preventing anyone OTHER THAN THE OWNER of said local data from accessing it again. To facilitate this local midget encryption, each encryption midget will be equipped with:
- body armor
- handgun
- lightweight sub-machine gun
- tactical nuclear or convential explosive self destruct device
Addtionally, each encryption midget will be required to communicate with all other encryption midgets around the world using special genetically encoded phones that cannot be replicated outside of the midget gene pool. The phone will be surgically embedded in the arm of each encryption midget and require a drop of said midget's body temperature saliva to activate the phone (a.k.a. spit on the arm to make the call).
Why encryption midgets? They're:
- portable
- eat less than an encryption giant and/or an encryption obese person
- tough as nails
Why tough as nails? If you've watched The Amazing Race at all this season on CBS, you have witnessed a midget drag her whiney, lazy cousin around the world. She has become the envy of other teams featuring health nuts, ex-Marines, and super-Christians. Who wouldn't entrust their data with a badass little person that can grab a live electrified cattle fence somewhere in South America, cuss about it, and STILL manage to continue the race?
Get me THAT encryption midget, and you'll never get a hold of MY data!
IronChefMorimoto
[Note -- if the midget from the show mentioned above has been eliminated from said show, then our data is doomed. I've missed the last several episodes, so all may be lost.]
Re:It means we all have to carry a midget around (Score:4, Funny)
Re:It means we all have to carry a midget around (Score:5, Funny)
Re:Should We Fear? (Score:4, Interesting)
The proof that they have computed two values that have the same hash is significant because it proves that it is computationally feasible with today's computing resources to calculate a second different string or dataset that hashes to the same value as the original. It shows that a md5 hash can be "faked" or duplicated using current computing power. There is nothing significant about the values themselves presented in the story just that such values can now be theoretically found in a reasonable amount of time using available resources.
Why this is a bad thing:
Say I sign a program using md5. An attacker writes his own different program and appends some gibberish data in such a way that the two files are different but have the same md5 hash. There is now no way (using md5) to tell the two programs apart. (Of course the programs would have to be similar in other ways, size etc... for the spoof to work.) This same thing could be used to calculate new passwords for md5 hashes that are known to the attacker.
Why should we not panic: It took a long time to find the collision. Chances are a script kiddie wont be able calculate such hashes to crack into your site. But it show that banks or other highly confidential data stores should now look elsewhere for their hashing needs. (Which they probably already do).
Strater
Re:Next step (Score:3, Funny)
Re:Next step (Score:3, Funny)
Re:Next step (Score:5, Funny)
- odd is development
- even is release
use ROT13, tripple-ROT13, quintupple-ROT13 for DEVELOPMENT WORK ONLY!
For release work, use double, quadruple, hextuple-ROT13
Re:Next step (Score:4, Funny)
Re:Don't the laws of computing make it... (Score:5, Interesting)
In fact, advances in computer speed tend to favor people encrypting data, rather than those trying to decrypt it. For example, increasing CPU speed by a factor of four or five will generally allow you to use a key two or three times as large, and still get the same performance. However, it definitely won't let you crack a key twice as large.
Suppose your faster CPU inspires you to move from 128-bit keys to 256-bit. What happens to the guy trying to decrypt your message? He now has to work 68,056,473,384,187,692,692,674,921,486,354,000,000 times as long, even if he buys the 5x faster CPU. Ouch!
Re:Don't the laws of computing make it... (Score:5, Informative)
in regards to the strength of 256-bit encryption:
now, the annual energy output of our sun is about 121 * 10^41 ergs. this is enough to power about 2.7 * 10^56 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. if we build a dyson sphere around the sun and captured all of its energy output for 32 years, without any loss, we should power a computer to count up to 2 ^ 192. of course, it wouldn't have the energy left over to perform any useful calculations with this counter.
but that's just one star, and a measly one at that. a typical supernova releases something like 10^51 ergs. (about a hundred times as much energy would be released in the form of neutrinos, but i let them go for now.) if all this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.
these numbers have nothing to do with the technology of the devices; they are the maximum that thermodynamics will allow. and they strongly imply that brute-force attracks against 256-bit keys will be infeasable until computers are built from something other than matter and occupy something other than space.
bruce schneier, applied cryptography, p 158
Re:Don't the laws of computing make it... (Score:5, Insightful)
For more fun see Ultimate physical limits to computation [arxiv.org] by Seth Lloyd
Re:Don't the laws of computing make it... (Score:4, Interesting)
Want something that will really blow your mind? Think about this: your computer monitor can display anything someone can take a picture of with a digital camera. Anything that is visible, can have its picture taken and thus can be displayed in your 1024x768 32-bit color monitor.
Now, one would normally think that there is an infinite number of possible pictures that one can take in our universe. Heck, just using a paper clip on a table could result in thousands of unique pictures considering the different angles, lighting, etc. Every situation, every person, place or thing you see during your lifetime could have its picture taken and displayed on that monitor! The near-infinite amount of photos that could be displayed on your computer monitor would encompass every visible event from the past, things going on right now, and events in the future. Some of these photos would be real, most would not be.
Above, I assume our computer monitor is 1024x768 & 32-bit color. To see all these pictures -- here & now, in the future on Mars, in a pretend past where Julius Caesar isn't murdered -- all one needs to do is program their computer to serially go through every pixel & color combination. Although it would take a very, very, very long time, eventually every pixel & color combination will be shown, thus showing everything that can ever be seen. A photograph of everything that could ever be seen, and even many situations that didn't/won't happen will be shown on that computer monitor. EVERYTHING.
Of course, many more times that in just random pixels & colors will be shown, too.
Re:Don't the laws of computing make it... (Score:5, Informative)
First let's start with something that might return some "sensible" (i.e. not ridiculously high) numbers. On the Apple II, Basic programmers had access to an incredibly low resolution mode with 40x40 pixels and 16 colors. Assuming we only use 2 colors (say, black and white), there are:
2^(40*40) = 4.44 x 10^481 possible screen images.
Whew! Already far beyond the 2^256 limit discussed. But out of curiosity, we can look at some other numbers. Using the full 16-color support of this low-res mode:
16^(40*40) = 3.90 x 10^1926
How many possible terminal screens are there, assuming only alphanumeric (and space) characters?
(26+26+10+1)^(80*24) = 5.41 x 10^3454
And some other modes of interest:
320 x 200, 2 colors: 8.31 x 10^19265
320 x 200, 256 colors: 2.27 x 10^154127
640 x 480, 256 colors: 2.07 x 10^739811
After this, direct computation was far too slow, but we can get rough estimates:
640 x 480, 16-bit color:
640*480*log10(65536) = 10^1,479,622
800 x 600, 16-bit color:
800*600*log10(65536) = 10^2311910
1024 x 768, 16-bit color: 10^3787833
And finally...
1024 x 768, 32-bit color: 10^7575677
Yep, a 1 with 7.5 million zeroes behind it. So we may all have to wait awhile before we see a computer sequentially generate a picture of alternate post-Caesar Earth. Still, an interesting thought.
Re:Don't the laws of computing make it... (Score:4, Interesting)
What should make you feel small is that physicist have figured out a way to count all the possible states for a particular volume of matter (assuming an upper bound on temperature, if that makes any difference). That means the entirety of the observable universe has only a finite number of possible states.
If the unobservable universe is infinite, and if states are distributed probabilistically (and why wouldn't they be?), that means that your hypothetical world where Julius Caesar wasn't murdered actually exists, out there, somewhere, far out of reach.
Re:Don't the laws of computing make it... (Score:5, Informative)
but it assumes something which is impossible, that is, perfect algorithms.
No, it doesn't. Schneier is discussing the computational complexity of scanning a uniform keyspace, which depends only on key size and doesn't touch on algorithmic quality in the slightest. Now, if he were talking about the security of 256-bit ciphers against any attack, rather than just against brute force, then the quality of the algorithm would indeed be important.
Re:Don't the laws of computing make it... (Score:5, Interesting)
More realistically, what if the subject of the communication was a long standing bank account or evidence of a government scandal?
Advances in computing power can work for attackers who stand to profit from a long-delayed payoff. Advances in quantum computing will lower the expiration date of protection for anything you encrypted in the past even more. The further in the past the ciphertext was made, the weaker it gets. This will be generally true for any arbitrary past date and future date. No ciphertext can be considered indefinitely secure. We can only assume that reasonable protection only exists for the short-to-medium term.
Fairly long OTP messages may be one exception.
Re:Don't the laws of computing make it... (Score:5, Interesting)
Re:Don't the laws of computing make it... (Score:5, Informative)
Sorry, didn't mean to mock, it's just amusing whenever these one-time pad things come up and everyone starts jumping up and down yelling "unbreakable" and others start going "no, 'cos, like, we could brute-force it.."
You can't brute-force a one-time pad. That's the point. There are many weaknesses to OTP, related to key exchange, but you can't brute force it, because you have no way of knowing if you're right, or even if you're close. The possible set of plaintexts from a properly OTP encrypted message is the complete set of possible plaintexts of that size (or smaller, plausibly).
Let us take the following ciphertext:
aaa
I have encrypted this with a one time pad. Now, it's a pretty short message. We could brute force all the possible combinations on your regular computer pretty much instantly. Anyone care to guess what the message might be?
Of course not, because it could be *any* 3 letter combination, assuming that I'm sticking to letters. Any attempt to contextually analyse it is flawed because you will never be able to prove you got it right. Let's say that we know the message is english, and we can therefore reduce the number of possibilities down to all 3 letter english words.
Woohoo. It doesn't help, it doesn't get us any closer to knowing exactly what it is, because there is no next step, the only information that can aid us in the decryption of a one time pad is information from "outside" the decryption. In this case, two items of information are available to us, the length (3 letters) and the fact that it is english, but the actual ciphertext itself is of no value whatsoever. It doesn't matter if those a's were z's or q's or anything else, we can't do anything with them unless we have the OTP.
"Decrypt candidates with "bad" and "moo" in them would definitely merit further analysis"
This is always the point where things go wrong
abskjhsglkjlssdkglkjsfdlkgjfld
Now lets imagine that we knew it was coming from bank robbers. Sweet, so, what can we do? again, the *only* information we have is the length. It could say this:
I am going to rob a bank in WA
Or this:
I am going to rob a bank in CA
Or this:
I am going to rob a bank in NZ
And there is no way to prove what it actually says at all. It might say:
I am going to buy some flowers
Again, you'll never know unless you have the key, there's just no way to tell.
Re:Don't the laws of computing make it... (Score:4, Informative)
OTPs are provably secure, as long as the key isn't compromised, e.g. by reusing it....
Here is a good link that answers the question: Why Are One-Time Pads Perfectly Secure? [std.com]
-a
Re:Don't the laws of computing make it... (Score:5, Informative)
"I killed John Smith"
"I did not kill John"
There is no way to tell which is the real plaintext. Since every single 19 character sequence will appear, every 19 character English sentence and every 19 character sentence in every other language that uses the same character set needs to be checked. You can eliminate as many garbage results as you like, there'll still be a huge number of non-garbage results that you have no way of choosing between. In fact, you might as well not even look at the cipher text - it can tell you nothing. Just enumerate all 19 character sentences and work from there.
Re:Don't the laws of computing make it... (Score:4, Insightful)
Re:Don't the laws of computing make it... (Score:5, Informative)
Yes, the OTP is the way to go -- sequence of random bytes, which you simply XOR with your message. Dump out /dev/random to a CD-R or DVD-R, make a copy for your friend, and you've both got nice one-time-pads that will probably last you quite some time.
What's interesting is that quantum physics offers several new things that will help implement excellent OTP systems... over existing fiberoptic telecom systems, no less! This is really exciting stuff.
First, quantum physics offers us a new way to generate truly random numbers for your OTP. Your rand() function sucks, I guarantee you. /dev/random is very good, but slow... /dev/urandom uses hash mixing so isn't nearly as random. Both rely on physical events, time intervals, and possibly thermal noise. In comparison, a quantum random number generator [idquantique.com] in theory gives you random bits that are totally un-influencable.
So now you've got your random bitstream... what do you do with it? Well, you hook up the OTP stream to a laser-based system that sends essentially single photons down an optical fiber. The idea being that single photons are either received by your friend or intercepted (absorbed) by your enemy. They can't be copied. Anyway several factors complicate this process but the basic idea remains. It's for real [nowwireless.com].
So your computer can generate a random OTP, securely send it to your friend (without fear of interception), and now you can both exchange classical data encrypted with your OTP. Repeat as necessary. If the physics behind this is sound, we shouldn't have to worry about algorithmic attacks in the future. Here's a rather complete [aip.org] article describing everything.
Re:Don't the laws of computing make it... (Score:4, Insightful)
The beauty of the OTP is that it doesn't matter if you guess what the pad is - you can't tell you've got it rigbt.
Given a cyphertext of length 9, there are keys that will decrypt it to read "Kill Bush", "Save Bush", "FuckOsama", "Bomb Iraq", "Love Boat", "qwertyuio", "!@#3fst9$-", and every other 9 character string. Since the OTP is random, all these keys have equal probability of being the correct one.
Re:Don't the laws of computing make it... (Score:5, Interesting)
If you do OTP right, it is unbreakable* because the only possible attack is to brute force it by trying every possible key, and trying every possible key on an n character cyphertext gives you every possible n character plaintext, with no way of telling which one is right. (That is, if you had the 16 character cyphertext "bhgisngukfgxd gyt" you would get all possible 16 character strings as possible plaintexts, including "attack US friday", "shoot Osama soon" and "I like chocolate", and you would have no way to tell which was the actual plaintext.)
*except for rubber-hosing, but that affects all crypto systems, and is a weakness of the people involved, not the crypto.
Re:Don't the laws of computing make it... (Score:5, Interesting)
Not really...nobody expects this trend in processing performance to continue forever. There are in fact provable limitations given things such as the number of atoms available in the universe that can be harnessed for computation... ignoring little details like quantum computation and such :-). These limitations may seem "out there" but in fact they aren't nearly as unrealistic as you might think. Exponentials grow FAST.
It's trivial to continue scaling the computing requirements required to break encryption schemes by simply adding more bits. That is, assuming the encryption/hash scheme itself doesn't have some fatal flaw which may allow for a sub-exponential cracking algorithm.
Re:Don't the laws of computing make it... (Score:4, Insightful)
It's the Heisenburg uncertainty principle, and it doesn't rule out computing with individual atoms. It just means that computing with individual atoms will work a lot differently than it does with normal, mostly deterministic electronics. The field of quantum computing is all about exploiting the weird quantum properties of atoms to do even more computation than would be possible if they were completely deterministic little point particles.
Re:Of course! (Score:3, Informative)
There always going to be collisions in check-sums. If that weren't the case than we wouldn't need to distribute actual files, just check-sums.
Um, wow. Let's start from the top.
1) Yes, there's always going to be collisions in check-sums. Fewer bits than the checksum than the data, pigeon hole principle, yada yada.
2) Even if there were no collisions, the whole point (well, one of two... more on the second below) is that they're NOT REVERSIBLE. So per
Re:Of course! (Score:3, Funny)
You just ruined a GREAT and REVOLUTIONARY compression algorithm!!!
Re:Paradigm Shift long overdue (Score:4, Insightful)
See earlier post about a thought experiment Bruce Schneier carried out that showed 256-bit symmetric encryption (if it had no holes) would be proof against any attack that could be carried out using (using our current knowledge of physics, that is).
Re:breaking BitTorrent (Score:4, Informative)
In order to put two different pieces with the same SHA-1 checksum in a file, odds are your file is garbage anyway. You could not do this with someone elses file (as you mention, a copyright file).
You could however, very simply, send incorrect data (on purpose) that matches the hash in the torrent file. Users' bittorrent clients would believe the file to be complete when it is in fact corrupted. This would result in 100% of the users who downloaded that segment from you getting a corrupted file.
Re:Hash Clash is nothing new. (Score:4, Informative)
Re:Explain ? (Score:4, Insightful)
So I don't know what the news item is here, except as a curiosity ('look we found it' - like finding the next Mersenne prime) or some technique has been found for making hash collisions which is better than brute force. If all they did was brute-force hash lots of files until finding two with the same MD5sum or whatever, it's obvious they were going to find a collision eventually.