md5 Debate

Discussions of secure PHP coding. Security in software is important, so don't be afraid to ask. And when answering: be anal. Nitpick. No security vulnerability is too small.

Moderator: General Moderators

LiveFree
Forum Contributor
Posts: 258
Joined: Tue Dec 06, 2005 5:34 pm
Location: W-Town

md5 Debate

Post by LiveFree »

feyd vs Jeff of PHP Nuke Evolution

feyd here says md5(md5())'ing a string decreases the entropy and makes it less secure ....

(In MSN)

now, lets say the md5 to test is: 35kjsdf908sdflk4598g
JeFF says:
if you go put that into an md5 cracker
JeFF says:
it will crack it in 5 minutes
JeFF says:
now
JeFF says:
lets md5(35kjsdf908sdflk4598g);
JeFF says:
now our NEW md5 is 345908sfdsdfklj45987f
JeFF says:
if you go put that into an online cracker, there is NO WAY IN HELL you will EVER get 35kjsdf908sdflk4598g out of it
JeFF says:
it would take YEARS to do

I would like to see proof of ANYONE crackign double md5()
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Post by John Cartwright »

I don't know the technical details behind this, but every time you md5 and md5 hash you greatly increase the chance of a collision.. there is no debate, it is fact.
Gambler
Forum Contributor
Posts: 246
Joined: Thu Dec 08, 2005 7:10 pm

Post by Gambler »

Simpler, faster, more secure: md5($string.'sa2t') .
Last edited by Gambler on Wed Feb 22, 2006 5:31 pm, edited 1 time in total.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

What does being able to look up a hash in an online, likely rainbow or dictionary, "cracking" table have to do with double hashing being more or less secure? It's all about math, very intensive math.


Here's several references where we've debated the security of it before. If you want real proof, decouple the hashing function and break it apart.
viewtopic.php?p=195736#195736 I'd suggest reading the whole thread.

Since I shouldn't have to dig out the answers for you, search under my name and Roja's for "entropy" .. there are many occasions we've both mentioned how it reduces the security. Pick up several high level books on Cryptography and Math while you're at it.

If you want to learn even more, I'd suggest making your own implementations of hashing algorithms, learn about salts and the increased security thereof.
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

If someone is that worried about security why don't they just use the PGP encryption? I don't know if that is feasible or not but I'm sure you could write a PHP script that would utilize PGP. I thought the main purpose of md5 is to ensure that you don't have a plain text list of passwords. Sure you might be able to crack 1 in 5 minutes, but even if you could crack one every 5 minutes, it would still take over 9 years to crack a million of them.
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Re: md5 Debate

Post by Roja »

Tucker wrote:feyd vs Jeff of PHP Nuke Evolution
First, taking a private conversation, from someone else, posting it in public, and using it to challenge someone else is well.. seven bad steps in one.

If you can't have the discussion yourself, invite that person to come here, or vice versa. However, you asked a question, and I'm happy to help explain.
Tucker wrote:feyd here says md5(md5())'ing a string decreases the entropy and makes it less secure ....
That is correct.
Tucker wrote:JeFF says:
if you go put that into an md5 cracker
Stop there.

There is no such thing. There are rainbow tables - which we mentioned in the last thread where you asked about double md5. A rainbow table is a collection of precomputed md5's. They do the md5(value), and store (to a db usually) the result. Then they do lookups on it (select). Thats it. No cracking.
Tucker wrote:JeFF says:
it will crack it in 5 minutes
Wrong. It will do a lookup near instantly if the site is any good. If not, it will add it to the queue to look for, and possibly email you when it finds it (not in 5 minutes!).
Tucker wrote:JeFF says:
now
JeFF says:
lets md5(35kjsdf908sdflk4598g);
JeFF says:
now our NEW md5 is 345908sfdsdfklj45987f
JeFF says:
if you go put that into an online cracker, there is NO WAY IN HELL you will EVER get 35kjsdf908sdflk4598g out of it
JeFF says:
it would take YEARS to do
Like we said in another thread, the *brute force* strength is lowered - which is based on the entropy. Thats a totally different type of attack.

Jeff is talking about a rainbow table attack. To reduce the chance of that, the proper solution is to use a salt. Adding a salt prevents a rainbow lookup. Because its not md5(value), its md5(value+salt). In addition, the salt changes if implemented properly, so it reduces their time to do the search. Finally, adding a salt *increases* entropy, making it stronger against a brute force attack.
Tucker wrote:I would like to see proof of ANYONE crackign double md5()
I'd like to see proof of anyone cracking md5. He's describing a rainbow table lookup.
LiveFree
Forum Contributor
Posts: 258
Joined: Tue Dec 06, 2005 5:34 pm
Location: W-Town

Post by LiveFree »

a) I have his full permission, know him as a personal friend

b) he says you can easily code a cracker using VB or C, etc.

c) How can you not think a md5 cracker is NOT POSSIBLE?

d) Just loop through every number -> letter combo and see if they match the md5()
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Post by josh »

Tucker wrote: b) he says you can easily code a cracker using VB or C, etc.
not for md5, or any other hash, if he can crack md5 hes got a lot of explaining to do..
Tucker wrote: c) How can you not think a md5 cracker is NOT POSSIBLE?
because it is a one way hash, that's like saying based on your fingerprint I can reconstruct your facial features with no outside data, sure if i had a database of peoples faces and their fingerprints I could match it up. This is a metaphor for the rainbow table Roja and feyd are talking about
Tucker wrote: d) Just loop through every number -> letter combo and see if they match the md5()
That's called a brute force,


While your friend does have some validity he is for the most part confused

Yes the md5 of another md5 will result in often a longer string, that doesn't matter, the brute forcer is still trying plain-text passwords against the hash

ex. md5(123) = 55555555555 (psuedo)

md5(555555555) = 66666666666 (psuedo again)

the attacker when brute forcing will now try every number:

md5(md5(121)) != the hash
md5(md5(121)) != the hash
md5(md5(123)) == the hash


see how that works? Effectively all you did was double the CPU cycles (per attempt), but factor in the lowered entropy and you are shortening the time per hash it takes to brute force.

Sorry to say your friend is misinformed
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Post by Roja »

Tucker wrote:a) I have his full permission, know him as a personal friend
So have him come here and speak for himself.
Tucker wrote:b) he says you can easily code a cracker using VB or C, etc.
He's using the wrong term.
Tucker wrote:c) How can you not think a md5 cracker is NOT POSSIBLE?
I know the math. There have been multiple *compromises* of the equation that drives md5, each reducing its effectiveness. However, it has not been completely cracked. You are using imprecise vocabulary, and what you mean by crack is not the correct term as used in this context.

You cannot crack md5.
Tucker wrote:d) Just loop through every number -> letter combo and see if they match the md5()
Thats not a crack. Thats a brute force attack. A crack would allow you to find the solution *without* iterating over every combination.

The key for MD5 is 128 bits. We can calculate the brute force key space with 2^128 = 3.4E38. A special hardware based key cracker for MD5 that can try one billion (1E9) keys per second will take 1.08E22 years to go through all possible keys. You can expect to get most keys in about half that time which will take 5.39E21 years. It is estimated that the sun will go nova in 1E9 years.

See why compromises in the formula matter?

If we find a compromise, we have a shortcut that lets us get a potential solution faster. Several have been found for MD5, reducing the time to solution by dramatic amounts. The time to solution is now so low that it is considered a weak algorithm.

Doing a double md5 reduces the entropy. It makes it *easier* to brute force. It makes it *harder* to do a table lookup.
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

Tucker wrote:d) Just loop through every number -> letter combo and see if they match the md5()
Can't you md5 say a 1gb file? So that would be 256^1,073,741,824. How long do you think that would take?
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Post by josh »

Longer then you will live to see the result
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Post by Benjamin »

Exactly :wink:
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

It actually doesn't take long to hash a 1GB file.
User avatar
Ambush Commander
DevNet Master
Posts: 3698
Joined: Mon Oct 25, 2004 9:29 pm
Location: New Jersey, US

Post by Ambush Commander »

But it would take a long time to cycle through all possible combinations for 1GB files.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

No argument there. :)
Post Reply