MD5 - Not as safe as once believed

[thehorse13]

There is an interesting paper on altering files without changing the MD5 hash. Even more interesting, a tool that can be used for POC.

This information was passed to me through a mailing list and I think that it is an interesting read. Many of us here should pay attention to this paper and as a side note, I am glad to see that others in the security field feel the same way that I do about MD5.

*Snip*

The full details may be acquired at the following link:

http://www.doxpara.com/md5_someday.pdf

A tool, Stripwire, has been assembled to demonstrate some of the attacks
described in the paper. It may be acquired at the following address:

http://www.doxpara.com/stripwire-1.1.tar.gz

Incidentally, the expectations management is by no means accidental --
the paper's titled "MD5 To Be Considered Harmful Someday" for a reason.
Some people have said there's no applied implications to Joux and Wang's
research. They're wrong; arbitrary payloads can be successfully
integrated into a hash collision. But the attacks are not wildly
practical, and in most cases exposure remains thankfully limited, for
now. But the risks are real enough that responsible engineers should
take note: This is not merely an academic threat, systems designed with
MD5 now need to take far more care than they would if they were
employing an unbroken hashing algorithm, and the problems are only going
to get worse.

Some highlights from the paper:

* The attack itself is pretty limited -- essentially, we can create
"doppelganger" blocks (my term) anywhere inside a file that may be
swapped out, one for another, without altering the final MD5 hash. This
lets us create any number of binary-inequal files with the same md5sum.

* MD5 uses an appendable cascade construction -- in other words, if you
happen to find yourself with two files that MD5 to the same hash, an
arbitrary payload can be applied to both files and they'll still have
the same hash. This leads to...

* Attacks are possible using only the proof of concept test vectors
released by Wang -- the actual attack is not necessary.

* Stripwire emits two binary packages. They both contain an arbitrary
payload, but the payload is encrypted with AES. Only one of the
packages ("Fire") is decryptable and thus dangerous; the other ("Ice")
shields its data behind AES. Both files share the same MD5 hash.

* Digital Signature systems are vulnerable, as they almost always sign a
hashed representation of data rather than the data itself.

* This is an excellent vector for malicious developers to get unsafe
code past a group of auditors, perhaps to acquire a required third party
signature. Alternatively, build tools themselves could be compromised
to embed safe versions of dangerous payloads in each build. At some
later point, the embedded payload could be safely "activated", without
the MD5 changing. This has implications for Tripwire, DRM, and several
package management architectures.

* HMAC's invulnerability has been slightly overstated. It's definitely
possible, given the key, to create two datasets with the same HMAC.
Attacker possession of the key violates MAC presumptions, so the impact
of this is particularly questionable.

* Very interesting possibilities open up once the full attack is made
available -- among other things, we can create self-decrypting
executables (fire.exe and ice.exe) that exhibit differential behavior
based on their internal colliding payloads. They'll still have the same
MD5 hash.

* Several doppelgangers may (relatively quickly, as per Joux) be
computed within a single multicollision-friendly block. As such, the
particular selection of doppelganger sets within a file can itself be
made to represent data. It's relatively straightforward to embed a 128
bit signature inside an arbitrary file, in such a way that no matter the
value of the signature, a constant MD5 hash is maintained. This is
curiously steganographic.

* Many popular P2P networks (and innumerable distributed content
databases) use MD5 hashes as both a reliable search handle and a
mechanism to ensure file integrity. This makes them blind to any
signature embedded within MD5 collisions. We can use this blindness to
track MP3 audio data as it propagates from a custom P2P node.
"Strikeback" capacity against executable trafficking is even more
pronounced -- it's possible to create application installers that
self-modify with host identifying characteristics but still successfully
retransmit on P2P networks under the global search hash.

[gore]

Another reason why Blowfish is better at everything ;)

[thehorse13]

This paper pretty much sums up why we don't use tripwire at our shop. I pissed and moaned about it and eventually got my way when I asked who would assume responsibility when I prove that I can indeed modify filez and keep the MD5 hash the same.

;)

[Striek]

We discussed this with a professor of mine. It was the first thing he told us when we came back to school in September - "MD5 has been cracked."

For some reason though, he still insists on MD5 sums for all evidence we collect during investigations, and hasn't covered any methods on migrating to a more secure hash algorithm. I have migrated all my tools to use the SHA1 checksum, mostly because it's also a part of the coreutils package and is *almost* as universally available and recognizeable as MD5. I stopped using MD5 in September.

It would be quite interesting to demonstrate realistically how this new technique could be used. I'm going to have to try it once I'm done this semester.

My advice for everyone is to just use SHA1; it's as readily available as MD5, and hasn't been cracked yet,

Can't Tripwire be set up with a different hashing algorithm? I moved my Aide to SHA1 in October.

[Soda_Popinsky]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post809981) by thehorse13
This paper pretty much sums up why we don't use tripwire at our shop. I pissed and moaned about it and eventually got my way when I asked who would assume responsibility when I prove that I can indeed modify filez and keep the MD5 hash the same.

;)

Then what was your alternative to tripwire / MD5?

I am glad to see that others in the security field feel the same way that I do about MD5.

What was your beef with MD5 to begin with?

[thehorse13]

We do have a solution that is similar to tripwire/MD5. However, the details cannot be posted in public.

My beef with MD5 has always been the same. The hash cannot guarantee integrity. The paper I have attached provides a POC very similar to the internal POC done here almost 6 months ago. Because of the huge amount of policy and red tape in place here, anything that introduces a hole in an otherwise air tight case is a baaaaaad thing.

[gore]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post809998) by thehorse13
We do have a solution that is similar to tripwire/MD5. However, the details cannot be posted in public.

DUN DUN DUN DUN DUN DUN DUN DUN DUN DUN DUN DUN DO DO DO, DO DO DO,

007, Horsey, The Horsey.

LOL

OK I'm done. lol

Anyway, depending on the box, I suually use Blowfish, but I really like SUSE Linux as it comes with Encryption which allows 4096 bit, and that is on this box, which is used for an FTP server.

Guess Quantum encryption is the next step huh ;)

One time keypads would work well, and are almost un-crackable when used properly, but who uses them properly? Remember the Russians? "Well hey since keys are hard to come by why not everyone use the SAME key??? As long as the same one gets used only once per office it should be OK right?"

Obviously not, lol.

I should come up with my own encryption standard. Gore138 or something. Un-crackable because whenever a crack is attempted it auto self destructs and takes the machine with it lol. Buahahaha.


I'm sure 4096 bit has been cracked by someone and that there is something higher, but really, is my cooking recipe THAT important? Maybe if I owned Kraft a recipe would need it.

[phishphreek]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810014) by gore

I'm sure 4096 bit has been cracked by someone and that there is something higher, but really, is my cooking recipe THAT important? Maybe if I owned Kraft a recipe would need it.

Thats silly... Kraft puts their recipes on the back of the box!
Or, you can just get it from their site...

http://www.kraftfoods.com/kf/

Duh! :D :p

[thehorse13]

Seriously though. MD5 collisions are pretty scary (limited output yet infinite input). To better understand my issue, let's say that you have some PWs that are hashed and you are able to mod a PW to match the original MD5 hash, the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed. This is only one example of collisions (other algorythms have the same issue) but think of what will happen when exploits/softwarez come out that allow for quick controlled collisions. Time to look into other algos as Striek suggests.

For those who scoff at such notions, keep in mind what platforms use this exact model for passwords. Our good friends at Cisco and just about every *nix OS on the planet.

[Striek]

the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed

The scary part is that you wouldn't need to set a new password. Two (or as many as you can find) password will soon be able to open the same account. It's only a matter of time now, and that time seems a lot shorter than it did 6 months ago.

SHA1 can't be too far off either. It's time to include stronger algorithms for general distribution.

[hypronix]

SHA-0 has been already compromised and last I heard SHA-1 was "in the works" so to speak. It is obvious - if yet unpractical - that hash functions are not collision-free [because they have a limited output]. However to get to the point where you can generate files with the same hash... that's something completely different. It won't be long until we'll be able to see carefully engineered apps with NOP sleds placed in such a way that the final hash is the same as the original... but the other modifications of the file would be very operational :)

Yet for the time being it does seem like a good idea to move to at least SHA-1

[Soda_Popinsky]

So whats ahead then? What algorithms are next in line?

And a quick question, as of now it isn't "possible" for an attacker to say replace a file on a website with that same file + backdoor, and maintain the MD5, right? I haven't sat down with the paper yet but it looks like the differences in fire and ice are how they are encrypted? So for POC's sake, they used a file that would be easy to create another file with the same MD5 (I think they call it the doppelganger) but as of now could they take a program like netcat and create a doppelganger? Or are they just making evidence that it will might soon be possible?

[hogfly]

MD5..while under "attack" is still NIST approved, and therefore should be able to withstand any scrutiny. I don't know if this PoC will begin to really affect anything..it's too early to tell. Has anyone here ever had an MD5 collision? I know I never have.
Obviously SHA-1 or SHA256 is the way to move, but MD5 is still viable as a means of verification.

[netRealm]

I'm not very knowledgeable on this subject, but what if we use two different hash methods? If we use both MD5 and SHA-1, on a file, how hard would it be to make modifications that would be undetectable to both? From what I understand, it would be very difficult because a modification that's undectable to one hash method could be detected by the other hash method. Don't know if it would work, but I think redunant security is a good policy.

[hypronix]

Well AFAIk that's why security certificates from sites include both a SHA and RSA [IIRC] signature so as to give more than one way of checking the authenticity. If both hashes are included then it should be exponentially complex [even if, say, a collision for SHA-1 was found] to create a second file different than the original yet with the same hashes.

[gore]

And anyone who wants to bad enough, will do it. Imagine if you could trojan Microsoft updates, now are you saying some ass wouldn't LOVE to have that many zombies? They would work on this night and day t do so no matter how hard it may be.

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810071) by thehorse13
Seriously though. MD5 collisions are pretty scary (limited output yet infinite input). To better understand my issue, let's say that you have some PWs that are hashed and you are able to mod a PW to match the original MD5 hash, the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed. This is only one example of collisions (other algorythms have the same issue) but think of what will happen when exploits/softwarez come out that allow for quick controlled collisions. Time to look into other algos as Striek suggests.
I think you are failing to recognize the actual scope of the issue. It's more for long strings of data that it might be an issue. It would be difficult to impossible to end up with a string less than 32 bytes long (such as passwords/phrases) that was different source but same MD5 output.
Saying "AHA, MD5 is compromised" when someone can inject a few arbitrary blocks into a file and break it is silly.
If you could jump with enough force you could achieve escape velocity; it doesn't mean it's necessarily going to happen. ;)
Additionally, your dislike for Tripwire seems misguided given that it can use other hashing algorithms.

For those who scoff at such notions, keep in mind what platforms use this exact model for passwords. Our good friends at Cisco and just about every *nix OS on the planet.
Erm, since when do *nixes use MD5 to store passwords? Have I been asleep?

[The Grunt]

Erm, since when do *nixes use MD5 to store passwords? Have I been asleep?

Slack uses it by default IIRC.

[Tim_axe]

phpBB uses (or at least used) MD5 to store password hashes.

Seriously though. MD5 collisions are pretty scary (limited output yet infinite input). To better understand my issue, let's say that you have some PWs that are hashed and you are able to mod a PW to match the original MD5 hash, the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed. This is only one example of collisions (other algorythms have the same issue) but think of what will happen when exploits/softwarez come out that allow for quick controlled collisions. Time to look into other algos as Striek suggests.

Given only an MD5 hash (output), you have no idea what the input is. It could be a hash of a large Word document, or the hash of a password. The problem is that given the output, you don't know what the input was [1]. So, the problem here is that we aren't at the point where we can say "Give me an input that produces hash_x" without knowing the input. Currently these methods analyze the input, and find ways to intermix/change some data to produce the same MD5 by exploiting how the MD5 is computed. We can't work backwords: So as of right now, we would have to somehow know the password we are trying to crack as a prequsite to calculating an input collision to use to get into the system and take over it. When we can acturally use it for this, we already have a better solution (the actual password).


I too agree that the collisions are scarry. But for now we are left out in the cold on the real developments: We only know of two vectors that hash the same, so we can only substitue those two for each other to produce the same MD5 hash, and we can only do this if it happens where MD5 is at its initial state. [2]

Judging from the article, they (Wang & Joux) are working on ways to find similar substitutions in the files that are more predictable and controllable, and possibly having the ability to find a place to plant whatever you want undetected by MD5.

As of right now, you could only find the changes if you were looking for them (SHA-1 hashes compared along with MD5, looking for irregularaties -- stripwire PoC does this) and they can only do something if there is a backdoor/timebomb in the program that is designed to look for this. In the PoC, stripwire looks for these changes (with SHA-1), and upon finding the trigger condition in Fire (specific SHA-1 hash), the timebomb ticks and explodes.


Take a look at the attached examples that show what the current code is limited in. I produced two JPEG image files of the AntiOnline banner. The underlying JPEG image code is the same as I only changed the headers by prepending the example vectors. This has the side effect of causing most programs to not recognize the images as images. If you grab IrfanView, which is able to find JPEG headers later in the file than they should be, it will ignore the first 128bytes that are there only included to fool the MD5 computations. MD5 the two images, and they will have the same MD5. Do a binary comparison; they are different. To make this work, the modified files are 128bytes longer than the orignal JPEG'ed logo. If we could calculate the correct values to put into the file at a later place, we could potentially render the image correctly without changing file size[3]. But we (the general public) do not have the knowledge currently to do what Wang & Joux are currently doing. My examples are just a rather weak attempt at demonstrating what they have so far showed and explained to everyone.



[1] - We know that a 128bit MD5 hash output can represent an infinate number of inputs. Because of MD5's inherent collisions, you can't be 100% sure what the input is because the input you used is just as valid as any other input imaginable (that has the same output).

[2] - Simply put, the two example test vectors can only be substituted for each other at the beginning of the file, where the original file begins with one of them. Thus we can construct a file that begins with them to work, but we're unlikely to come across this given an arbitrary file. The vulnerability itself is applicable to changing virtually anything anywhere, but we've only been provided with rare vectors that were probably considered safe (by happening primarily in controlled situations instead of in the wild) by Wang & Joux.

[3] - Simply, we don't know how to calculate these "doppelganger" blocks. If we could, we could include them in arbitrary files while preserving the MD5 hash. Wang & Joux are leaps and bounds ahead of us here, as they are leading the way by already doing this.

[hypronix]

I don't think it would be at all possible to identify the original data that has been passed through the hash because a hash function has a fixed output length which means data is being mangled around. Take a look at the algorithm's description if you will... I don't think there's a readily available method to reverse it.

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810149) by The Grunt
Slack uses it by default IIRC.
No, it doesn't.

[Striek]

I think the technical infeasibility of generating a specific file to match a specific MD5 sum is irrelevant. Try to prove the integrity of your evidence in a courtroom using MD5 sums, and watch the defence come up with two files like this. Now watch yourself stutter and stammer.

No jury cares how technically infeasible it is. They see two different files with the same signature and they see an unreliable algorithm. Therefore they see compromised evidece, or at least reasonable doubt.

Which, for all intents and purposes, makes MD5 about as useful as CRC32 in a courtroom now.

[gore]

Slackware = DES I think.

[The Grunt]

DES?

[gore]

Most Linuxes I've seen default with DES. MD5 and Blowfish are an option. DES means compatible with more OSs, while Blowfish isn't, but to me I would rather use Blowfish.

[thehorse13]

Erm, since when do *nixes use MD5 to store passwords? Have I been asleep?

Do I really have to answer that? LOL. ;)

Actually, I think it's more of a matter of you not being born yet. There are many older *nix systems that use MD5 to hash passwords. We have several of these dinosaurs as do many Governments.

I think you are failing to recognize the actual scope of the issue.

You are focusing solely on the technical implications. My point is that the technical ramifications are shadowed (for now) by the legal ones. As someone pointed out, a NIST approved hashing algorithm will no longer hold water in court, or in my case, Government. I don't think it's outside of reason to believe that someone will indeed find a way to further exploit collisions.

Additionally, your dislike for Tripwire seems misguided given that it can use other hashing algorithms.

My dislike for Tripwire lies with their sales clowns telling me that they offer an impenetrable product when in fact we all know there are papers freely available that detail how to beat Tripwire. This isn't, in my opinion, misguided. However, to be fair, yes, they do offer additional hashing algorithms.


As always, nice doin business with ya chsh. :)

[Maestr0]

I would just like to note that MD5 was developed in '91 by good ole RR. To avoid the export restrictions on DES (The UNIX default) some BSDs(Free maybe?) use MD5 by default.. As far as MD5, this is not a preimage attack its a collision and theoritcally all hashes have collisions,so take that to court,. :) Hash functions are NOT encryption fucntions, Anyone relying on a HASH function only without an actual encryption routine is not a real attempt at security anyhow.


P.S. Tim_Axe is the only person in this thread who appears to know WTF he's talking about,


-Maestr0

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810483) by thehorse13
Do I really have to answer that? LOL. ;)
Actually, I think it's more of a matter of you not being born yet. There are many older *nix systems that use MD5 to hash passwords. We have several of these dinosaurs as do many Governments.
Yes, you do because really, your response here is contrary to your wildly exaggeratory "almost every *nix on the planet". It's an OPTION, not a DEFAULT, and I would wager not widely in use.
Oh, FYI, I was born in 1981, well before the advent of MD5, since you are evidently too lazy to read my profile. I even used unixes back in the early 90s too.

You are focusing solely on the technical implications. My point is that the technical ramifications are shadowed (for now) by the legal ones. As someone pointed out, a NIST approved hashing algorithm will no longer hold water in court, or in my case, Government. I don't think it's outside of reason to believe that someone will indeed find a way to further exploit collisions.
I was focusing on the technical implications because that was where my disagreement lay. Of course in court it will be an issue, I agree with that.
At any rate, some of what you posted is blatantly overblown:
To better understand my issue, let's say that you have some PWs that are hashed and you are able to mod a PW to match the original MD5 hash, the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed. This is only one example of collisions (other algorythms have the same issue) but think of what will happen when exploits/softwarez come out that allow for quick controlled collisions.
Show me a collision for a 30 character password, then one for a 20 character password, then one for a 10 character password. I will be genuinely surprised.

[Striek]

P.S. Tim_Axe is the only person in this thread who appears to know WTF he's talking about,

And does that make you smarter because you were, in your own insignifigant opinion, able to realize that?

What difference does it make if I don't know what I'm talking about? That's why I come here. If I post anything incorrectly, I would hope that somebody points out my error. If everyone knew what they were talking about, nobody would come here. Do you think you're insulting us by telling us this, or that this is some kind of epiphany for us?

BTW, Horsey has already forgotten more than you will ever know in this matter. The fact that you can quote a few historacal and Googleable facts in a discussion forum proves nothing. Telling us all that we know nothing also proves nothing except the fact that you somehow believe that you can make that judgement.

And just for your sake, hash algorithms and public key encryption algorithms are essentially the same thing. They're what peope call one way algorithms, meaning that in both cases, one cannot compute the original input (i.e. the original message or the prime factors of a private key) if one knows only the output (i.e. the digest or the public key).

I am aware that I know nothing. That's why I'm here. My education is nothing but the continued discovery of my own ignorance.

In the future, please confine your insults to private messages where they will not degrade this forum.

[Soda_Popinsky]

Show me a collision for a 30 character password, then one for a 20 character password, then one for a 10 character password. I will be genuinely surprised.

If it were possible, wouldn't it be seen in a rainbow table? I wonder how big the biggest rainbow table is...

[Maestr0]

And just for your sake, hash algorithms and public key encryption algorithms are essentially the same thing.

I rest my case. The statement was not intended to be insulting but to allow interested parties to pursue information on the topic which is based on the facts and the research involved as opposed to listening to people who think hash functions and public/private key encryption are the same thing. *sigh* If you want to know the difference, click on my little profile and go find one of the many messages I have posted pertaining to encryption, and read some of Tim_Axes while you're at it, you might learn something which is why you said you're here. As for the MD5 attack, people have been aware of flaws in it for years and knew that it would be broken eventually jut like MD 1-4. The attack used the Biham/Chen technique to find a collision. This means two seperate pieces of input produced the same piece of output. Is this bad? Yes. Is this a diasaster? Not really. All hash functions have collisions the idea being that its just really,really hard to find them. Using the Biham/Chen method made it easy enough to discover one. This is not the same as a preimage attack which would have far more people worried. A collison attack does not allow you to create the hash of your choosing. You have to use the hash the collison that is found, and. Like Tim_axe was demonstrating the biggest problem with this is with signed code/and signatures. It could allow some one to get one piece of code signed and the substitute it for the other, IF they had the collision, but this isnt really realated to passwords. If someone has your password file of MD5 hashes, they arent going to look for a collision. They're going to run a dictionary attack on it and crack the shit out it. You'll have the whole list cracked before you find a collision on one password. My point is no one should have your password file in the first place, and if your relying on MD5 or some other hash function to protect you from a weak password you are SOL. Faster ways of finding the collisions will be found, of that I have no doubt. But hopefully by then people will be using another function for signing like SHA1 (which will also be broken, of that I also have no doubt) this is the nature of cyrpto. You make something, you break it. You make something better. Repeat.


-Maestr0

[Striek]

Oops. My bad. I guess that statement was misleading.

What I meant was that they both rely on the concept of a one way algorithm, albeit, yes, the mathematics of each are entirely different.

Really, what I was trying to say was that IMHO a good hash algorithm is as good as a good encryption algroithm, if it's all you need.

[hypronix]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810551) by Maestr0
They're going to run a dictionary attack on it and crack the shit out it. You'll have the whole list cracked before you find a collision on one password.
-Maestr0

Well actually, what they find might be a password collision rather than the actual password... it would be quite a bummer if a complicated 30 character, alpha-numeric and special character password had a collision with a 5 character dictionary word [okay it might be unlikely but get the point].

From the point of view of the attacker they don't care what they find, be it password or collision, as long as the hash matches.

But I agree entirely that nobody should get access to the files that are password-related.

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810543) by Striek
And does that make you smarter because you were, in your own insignifigant opinion, able to realize that?
He makes a good point though, if you actually do read the research material it kinda refutes what you, TH, and others (somewhat including myself) have been saying... I got the chance to read it through, and now I understand it better.

What difference does it make if I don't know what I'm talking about?
LMAO! Thanks for the sig material man!

That's why I come here. If I post anything incorrectly, I would hope that somebody points out my error. If everyone knew what they were talking about, nobody would come here.
That's not necessarily true, but if you only see that one set of motivations, you probably aren't open to knowing about others.

BTW, Horsey has already forgotten more than you will ever know in this matter. The fact that you can quote a few historacal and Googleable facts in a discussion forum proves nothing. Telling us all that we know nothing also proves nothing except the fact that you somehow believe that you can make that judgement.
Mmmmhmmm... TH, is your ass sore from all the kissing it's been receiving lately?

And just for your sake, hash algorithms and public key encryption algorithms are essentially the same thing. They're what peope call one way algorithms, meaning that in both cases, one cannot compute the original input (i.e. the original message or the prime factors of a private key) if one knows only the output (i.e. the digest or the public key).
BWAHAHAHAHAHA!
What difference does it make if I don't know what I'm talking about?
Just FYI, Public Key encryption and hashing are way different. In the case of the former, you actually use it to encrypt data, and the public key you give out describes how to DECRYPT the data, to obtain a copy. Hashing is to Encryption as eating breakfast is to working in a cereal packing plant....

I am aware that I know nothing. That's why I'm here. My education is nothing but the continued discovery of my own ignorance.
Then why argue with someone who obviously has a bit more experience and knowledge than you do? This isn't the third grade, TH doesn't need people to "pick his side". If he has responses he will surely provide them, and I highly doubt anyone is going to lose any sleep over a disagreement on a web forum (but then again these days you never know).

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810544) by Soda_Popinsky If it were possible, wouldn't it be seen in a rainbow table? I wonder how big the biggest rainbow table is...
It should show up, yes. If I'm able to pick up my dual 100GBs I'm going to try generating some of the smaller rainbow tables for MD5 and see if there are any collisions, mostly because rainbow tables and hash collisions have been a matter of passing interest for me for a few months now.

[Striek]

/begin male pissing contest -- round 3

Then why argue with someone who obviously has a bit more experience and knowledge than you do?
Because arguing can be fun sometimes.

In reference to hashing and encryption being the same thing, I was referring to the process of computing a public key from the private and vice versa, not computing the ciphertext. It just came out all wrong. Hence my previous post.Hash functions are NOT encryption fucntionsWhat I was trying to say was the similarity between the two is in the fact that calculating a private key from a public key can be somewhat likened to calculating a message from the digest. It's a very rough comparison, I know.

I wasn't trying to kiss ass, either. I was merely trying to dispute the fact thatTim_Axe is the only person in this thread who appears to know WTF he's talking about, which I took to mean "You're all idiots." Apparently, that was not his intent.

That's why I come here. If I post anything incorrectly, I would hope that somebody points out my error. If everyone knew what they were talking about, nobody would come here.Should readThat's why I come here. If I post anything incorrectly, I would hope that somebody points out my error. If everyone knew what they were talking about all the time, nobody would come here.
Granted, many peeople come here for the community and to share what they know, but how much fun (and admit it, the ego boost wouldn't be as good either) would it be if you couldn't say anything that somebody didn't know?

My whole point with MD5 being compromised is that despite the fact that the technical ramifications are small, the legal ones are enormous. It's just smarter migrate to a better algorithm now, rather than face an argument like this if you use MD5 to verify evidence integrity.

/end round 3

[The Grunt]

Hashing is to Encryption as eating breakfast is to working in a cereal packing plant....

lol, nice analogy. I'll have to use it to describe the difference for my not as geeky as me friends.

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810589) by Striek
Because arguing can be fun sometimes.
It's a rare thing when someone so freely explains they were trolling.

In reference to hashing and encryption being the same thing, I was referring to the process of computing a public key from the private and vice versa, not computing the ciphertext. It just came out all wrong. Hence my previous post.What I was trying to say was the similarity between the two is in the fact that calculating a private key from a public key can be somewhat likened to calculating a message from the digest. It's a very rough comparison, I know.
You're still very incorrect. A hash is a reproducible set of bit values based on the contents of a given piece of data. A public key is a specific sequence of bits that act as directions for encrypting data. It is generated from the private key. It is not based on the data in the private key strictly speaking; it is generated from the private key in a fashion which ensures only the private key can read the data the public key encrypts.
The fundamental difference: hashes are based on the data they are created from, public keys are not necessarily based on the data in the private key -- which is I might add a security measure. If you have no data from the private key to work from, you would have to bruteforce every combination of bits in the key length. As 1024bit keys would have 1.79[...]e+308 (1.79 * 10^308) possible combinations, it would take a long while to bruteforce.

I wasn't trying to kiss ass, either. I was merely trying to dispute the fact that, which I took to mean "You're all idiots." Apparently, that was not his intent.
As I said, I think TH can speak for himself. In fact, I know he can.

Granted, many peeople come here for the community and to share what they know, but how much fun (and admit it, the ego boost wouldn't be as good either) would it be if you couldn't say anything that somebody didn't know?
I come here purely for debate, information exchange, and to poke fun at people who employ the use of their fingers without first engaging their brain (or eyes, or google for that matter). I don't consider it an ego trip to disseminate information, or help someone fix a problem. It's a small ego trip to laugh at people who write first and research second, but I consider the ego stroking to be outshadowed by the sheer entertainment value.

[gore]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810535) by Maestr0
P.S. Tim_Axe is the only person in this thread who appears to know WTF he's talking about,


-Maestr0

Where did I say anything in this thread that was incorrect?

[Negative]

Where did I say anything in this thread that was incorrect?

You said that Blowfish is better at everything... what about Rijndael? Both Rijndael and Twofish (Blowfish's sucessor) were running in the NIST competition for AES standard, and Rijndael won... someone definitely disagrees with you :p

[gore]

That's more of an opinion isn't it?

[hypronix]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810657) by gore
That's more of an opinion isn't it?

I tink I'll go with whatever the standard is ;) Not that I don't appreciate your opinions :)

Just as a side-note... how the hell does it make a difference what people think of people? First off whatever has been said in this thread were merely ideas and thoughts based on what started out as a speculation about MD5 and what's better to use for the future... since when can that be a reason for evaluating whatever gore, Striek, myself or whoever else actually knows about the topic of cryptography?

Admittedly Striek's comment about hashing and encryption was a bit vague... but holy f!ck people! :D

[Striek]

Yeah, it was too vague. I never intendended it to start something like this.

Sorry about that.

Hrmmm... feet don't tase so good when you put them in your mouth.

[!mitationRust]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810138) by chsh
I think you are failing to recognize the actual scope of the issue.
Hey, you're way out of line kid. Let's get some cold ****ing fizzy water on your head.
Why don't you go read the DOD-STD-5200.28 on encryption, then come back and tell thehorse how to do his job.

[thehorse13]

I've said it once and I will say it again, I welcome people to disagree with me especially when they provide reasons. Isn't that the point of a forum? As chsh has noted, I'm a big boy and I'm certainly capable of backing up my opinions. His style of responses and those similar never cost me a second of sleep. I'm comfortable with my level of knowledge and I never ever become defensive when someone challenges it.

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810682) by !mitationRust
Hey, you're way out of line kid. Let's get some cold ****ing fizzy water on your head.
Why don't you go read the DOD-STD-5200.28 on encryption, then come back and tell thehorse how to do his job.
Err, don't tell me YOU don't know the difference between hashing and encryption too! I'm beginning to think it's an epidemic.

EDIT: Even aside from the above, all I could find for various terms was "DOD-STD-5200.28 DEPARTMENT OF DEFENSE TRUSTED COMPUTER SYSTEM EVALUATION CRITERIA" located at: http://jcs.mil/htdocs/teinfo/software/did27.html which oddly enough does not mention encryption at all.

Perhaps you could link me directly, since I am apparently but a child and incapable of researching something that has nothing to do with the discussion at hand.

P.S: Since you evidently haven't gotten past a grade 8 reading level yet, I wasn't telling TH how to do his job, in fact, if you read the thread nowhere do I tell him he is wrong, I simply disagree with him on the scope of the issue, and his examples thereof.

[!mitationRust]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810723) by chsh

EDIT: Even aside from the above, all I could find for various terms was "DOD-STD-5200.28 DEPARTMENT OF DEFENSE TRUSTED COMPUTER SYSTEM EVALUATION CRITERIA" located at: http://jcs.mil/htdocs/teinfo/software/did27.html which oddly enough does not mention encryption at all.
Where the hell did you get that from, it's mentioned six times. If some could only read, some would know encryption has nothing to do with system security.
If you could read past the first couple pages that would help also. All you read was the table of contents! Like thehorse said, objectivity is the point of the forum. But what I've read from you in the past, it's safe to take catch's suggestion. Your mind is already made up, not to mention it's functioning in a closed-loop type manner.

LMAO! Thanks for the sig material man!
Yeah, I found some sig material aswell.
~catch
Ah chsh back trolling again...

The reason I ignored your questions was because I'd already answered them and to be honest, I really have better things to do with my spare time then to educate the likes of you. That is people who have already made up their mind and just wish to fight and post so much shit that it isn't practical for me to take the time to respond to every little piece.
He was right.

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810765) by !mitationRust
Where the hell did you get that from, it's mentioned six times.
Oddly enough, I read "more than the table of contents", encryption itself does not come up at all, merely data protection methods. Feel free to quote relevant bits.

If some could only read, some would know encryption has nothing to do with system security.
Funny thing is, you're going off on a tangent completely irrelevant to this thread, which I also pointed out and you continued to ignore.

If you could read past the first couple pages that would help also. All you read was the table of contents!
:rolleyes:

Like thehorse said, objectivity is the point of the forum. But what I've read from you in the past, it's safe to take catch's suggestion.
Of course it is, why let facts be such a bother when you can easily sidestep them and just flame the poster for saying something they didn't? I love that you brought up catch as an example, because frankly if you read EVERY thread we've debated in, he always runs away for "time away" or "work for a couple of weeks". He disappears when the facts stack up against him, rather convenient I might add. Hey, if you want to quote the best troll AO's had in recent memory, feel free.

Your mind is already made up, not to mention it's functioning in a closed-loop type manner.
Funny you say that given I already asked you to point me to a better source. I'm still waiting to see the pertinent section of said documentation. That you have avoided producing it is entirely catch-like behaviour. No wonder you like the guy so much.

[Striek]

Funny thing is, you're going off on a tangent completely irrelevant to this thread, which I also pointed out and you continued to ignore.

Pretty much everything posted here in the last two days has been irrelevant to the original topic of this thread. This thread was originally posted to debate the continued usefulness of MD5 as a hashing algorithm.

All opinions aside, I can only see one post on the page here which actaully says anything on the matter. This thread has turned an otherwise useful debate into an ego-bashing festival. It has served its purpose.

I for one am asking a mod to close this thread, as it is no longer contributing in a useful manner to this forum.

[MrLinus]

Before closing this thread, I'd like to take a stab at moving it back to what it was about. Keep in mind everyone that people can choose to contribute or not contribute any thread. They can also choose to decide what they want to contribute. I'll leave that to you to figure out..

That said, I have some questions for my own personal clarification:

!matationRust: The Orange Book Classification (http://csrc.nist.gov/publications/history/dod85.pdf) (aka DOD-STD-5200.28 DEPARTMENT OF DEFENSE TRUSTED COMPUTER SYSTEM EVALUATION CRITERIA) doesn't seem to indicate any reference to encryption. I always understood that it dealt with Access Controls specifically and the levels or types of Access Controls (MAC, DAC, etc.). Perhaps I'm misunderstanding your point as to where it refers to it. The only thing that I could find that was close was the question of integrity of a system. Is this what you were referring to? This does lead to my next question

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.

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?

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

[Striek]

MD5 being cracked shouldn't really come as a surprise. It happens with all forms of encryption (or hash algorithms) sooner or later; this is why we're not using MD4 anymore.

It should not pose a huge problem to anyone. Any security policy should cover what to do when your existing methods become useless. A plan should be in place for just such an occasion, because it *will* happen.

Many Open Source sites use MD5 as a verification tool, yes. However, the more constientious sites (kernel.org and kde.org come to mind) also sign those hash lists. Although theoretically, one could calculate the MD5 of a given file and replace it with a trojan (not yet, but it's coming soon), one could not yet sign that hash file with the proper key. As such, timestamping these hash lists by a trusted third party could serve as a temporary solution. This however requires the public to routinely check the timestamp and verify it with the release date, which might not happen as often as we'd like.

A more permanent solution would be to do the same thing we always do when the current encryption techniques become useless. Move to a better algorithm. Currently, the best alternative is SHA-1, since it is also included as part of the coreutils package and is therefore available on most every system that already has MD5 algorithms available.

So if MD5 being cracked is the end of the world for you, maybe you shouldn't be working in a field that required it.

[gore]

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

[chsh]

Originally posted here (http://www.AntiOnline.com/showthread.php?threadid=264461#post810834) 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 (http://www.AntiOnline.com/showthread.php?threadid=264461#post810927) 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 (http://www.AntiOnline.com/showthread.php?threadid=264461#post810933) 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.