MD5 - Not as safe as once believed

[gore]

It's OK guys, one time keypads are still safe, if used properly

[chsh]

Originally posted here by MsMittens
To all: Since MD5 is now "crackable", and thus now becomes a questionable encryption tool for usage in integrity situations, what are viable, publically available tools that can be used? And how long before the general public is aware of this? Many linuxes suggest the use of MD5 (because it's "more secure") for shadow passwords.

Well I think there's really two issues to deal with here. MD5 as a hashing algorithm for generating file signatures, and MD5 as a password hashing algorithm.

EDIT: [...]

The trick with using this issue to exploit a system is to discover the colliding changes, and then append your arbitrary data into both the original and the malware. If Tripwire already knows the original as not having the apended data, then it will still notice. md5(x+q) = md5(y+q) doesn't mean md5(x) = md5(y+q) where x is the original and y is the collision. The most you could do without appending the data is break the app.

EDIT:
For evidence verification, I think this note about the scope of collisions is interesting:

FROM: http://www.doxpara.com/md5_someday.pdf
In addition, being limited to the MD5 initial state means only hashes calculated on a per-file basis can be made to collide; a full disc or partition sum will come across the doppelganger set at a vastly different initial state and fail to collide. With the full attack we could specify our colliding blocks against the MD5 state that would be found during a full disk or partition hashing operation. Of course, then the colliding set we generated wouldn t collide on a per-file basis. Thus far we can only adapt to a single MD5 state at a time.

As for password collisions, there are various problems with trying to develop them if my understanding is accurate.
You have to have two hashes within the acceptable password range that are capable of producing the same hash. On linux, the maximum password length is 127 bytes (for interactively entered passwords). This yields 2^1016 or 7.0222388080559215e+305 combinations if we set aside the fact that you can't enter certain NPC combinations and operate in theory.
We already know that for a given dataset of 128 bytes in length there are somewhere near 6 possible bits that can be swapped.
Assume that the minimal size of a password for a hash collision is 512+8 which is MD5's minimum block size (can't have a collision with less than two blocks) plus one byte. This means you have to have a 65 character password to even begin to contemplate a hash collision, AND the collision must exist as the same size. Not sure how that was missed, but the last step of the algorithm is to add in a 64 bits referring to the size of the data being hashed.
The proof of this (as was previously mentioned) would show in a rainbow table. It may be mathematically impossible to find an MD5 hash collision for a dataset less than 64 bytes in size, I'm not sure, but it would seem so if my understanding is correct.

It would seem to me that it makes sense to continue using MD5 for password hashing.

Are we going to see AES or others being "pushed" more now as alternatives? What about sites that use the MD5 hash as a verification of their product (which is pretty much commonplace for any Open Source project)? Is there in existence -- to anyone's knowledge -- any alternatives to tools like MD5sum? Are there projects that deal with this yet?

I know slackware uses GPG to provide PGP signatures for all their files.

This is what it boils down to: we know that MD5 is now "useless". So what are we going to do as alternatives?

I think it's really only "useless" to use as data hash verification. Certainly for this other algorithms are going to take over, though IMO it will be a very slow process. For passwords it still seems to be a decent solution, unless you're in the habit of using passwords longer than 64 characters.

[hogfly]

Msmittens: Yes, SHA1DEEP, found here is a good replacement:
http://md5deep.sourceforge.net/

Pay no attention to the project site name. It's a combination of md5deep and sha1deep. Basically..a recursive md5/sha1 tool.

Regarding all of the BS in this thread..you guys should really just grow up, and learn to disagree.

MD5 is still a viable hashing algorithm. As I said before, until NIST removes it from their standards list, it's viable and it WILL stand up in court. A junk science attack(when a lawyer reads that md5 can be 'cracked' and tries to throw it at you in court by saying "md5 has been cracked, how can you justify using it?") will do nothing more than embarrass the lawyer. The real problem there, is how well you can explain the method of how a hash is derived. And again, if it came down to it, the lawyer on your side could always subpoena someone from NIST, and get them to explain why it's a standard. Lawyers won't touch NIST.

[gore]

Originally posted here by hogfly
Regarding all of the BS in this thread..you guys should really just grow up, and learn to disagree.

If they learn to just disagree as you say they should wouldn't that mean MORE arguments, which is what you seem to be saying is stupid here? I mean seriously now, everyone says grow up, and people neg me saying to grow up.... What exactly does growing up solve? Nothing. If you think like a grown up and never question authority nothing gets done and no one would ever question a thing and misinformation would reign supreme.

I've read this and listened to how Tim was the only one who knew what he was talking about, and offered someone to prove one thing that I said as incorrect, and the only reponce I got out of that was something that was more opinion that fact based. Someone using DES over Blowfish, well, maybe that works better in the environment they operate in. I use Blowfish, it works in what I do better. 448 bit works fine which is what Blowfish can do.

One time pads are in my opinion still the best for security if you use them properly, but not every place on Earth has a high amount of keys or a way of getting them, so even though I'd say they were the most secure it doesn't mean they are going to be used.

You find something that's both secure and economical and work with it.

What I've seen so far is that the people in this thread are highly respected, except for me of course, half the people here still think I'm an idiot, including Jag, but that's OK, at least I know how to compile a Kernel and remember to type lilo when it's done instead of wondering why it won't work on IRC, and this thread still has arguments with people bitching about acting like little children.... Well so what? It's a discussion. Nothing personal hog I just can't stand the number of times a day people say grow up.

[Striek]

MD5 is still a viable hashing algorithm. As I said before, until NIST removes it from their standards list, it's viable and it WILL stand up in court.
...
Lawyers won't touch NIST.

Hmm... never looked at it that way. Good point.

But as for MD5deep being a replacement for MD5 (I think that's what you meant), it still uses the MD5 algorithm, just does it recursively. How could that be a replacement if it uses the same algorithm? <insert confused look here>

[The Grunt]

I think MD5deep uses BOTH SHA1 and MD5, so you would have to have a crack for both of them to be able to do anything at all.

[Striek]

md5deep is capable of using any of the MD5, SHA-1, or SHA-256 algorithms. The choice is up to the user.

So if a user chooses to use MD5, that's all you gotta crack.

And we all know you can't write a program that protects against incompetence. After all, I could still use crc32 to hash evidence if I really wanted to...

[hogfly]

Originally posted here by gore


Nothing personal hog I just can't stand the number of times a day people say grow up.

Indeed, and I don't want this to turn in to a soapbox..but learning to disagree+growing up == agreeing to disagree without lowering yourself to a level where personal insults are thrown at eachother.

Striek:
Md5deep isn't a replacement. The project includes 3 tools. Sha1deep, sha256deep and md5deep. Each obviously creates a hash for said algo type. sha1, and sha256 would therefore be the replacement.