Idea - Double hashing.

Discuss the many weaknesses of browser security and ways to mitigate the threat

Idea - Double hashing.

Post by 3vilp4wn on Wed Apr 03, 2013 12:35 pm
([msg=74875]see Idea - Double hashing.[/msg])

I recently got an idea about how to make a hash more secure against bruteforce, and impossible to dictionary attack.

Here's how it works:
1.) Take the password and hash it, so "admin" will become "21232f297a57a5a743894a0e4a801fc3" (I'm using md5 for this example.)
2.) Take the hash ("21232f297a57a5a743894a0e4a801fc3" in this case), and hash it again, so it becomes "c3284d0f94606de1fd2af172aba15bf3".
3.) Store "c3284d0f94606de1fd2af172aba15bf3" in your database. this limits bruteforce attempts to 32 character hex strings, and stops dictionary attacks on the first hash, and takes only twice the CPU.

Can anyone spot any flaws with this?
Do not mistake understanding for realization, and do not mistake realization for liberation
Evil Ninja Hackers
???
٩(͡๏̯͡๏)۶

1A4EAMboaXpgvUSmtRbVRqbfJrbyuGhyoo
User avatar
3vilp4wn
Poster
Poster
 
Posts: 144
Joined: Sun Feb 10, 2013 2:05 am
Location: The darkness.
Blog: View Blog (0)


Re: Idea - Double hashing.

Post by centip3de on Wed Apr 03, 2013 1:31 pm
([msg=74876]see Re: Idea - Double hashing.[/msg])

3vilp4wn wrote:I recently got an idea about how to make a hash more secure against bruteforce, and impossible to dictionary attack.

Here's how it works:
1.) Take the password and hash it, so "admin" will become "21232f297a57a5a743894a0e4a801fc3" (I'm using md5 for this example.)
2.) Take the hash ("21232f297a57a5a743894a0e4a801fc3" in this case), and hash it again, so it becomes "c3284d0f94606de1fd2af172aba15bf3".
3.) Store "c3284d0f94606de1fd2af172aba15bf3" in your database. this limits bruteforce attempts to 32 character hex strings, and stops dictionary attacks on the first hash, and takes only twice the CPU.

Can anyone spot any flaws with this?


Why not skip that and just go for SHA-2? There has been no significant attack on it (released, anyway). Seems a bit easier and safer to me.
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rick Cook
User avatar
centip3de
Moderator
Moderator
 
Posts: 1449
Joined: Fri Aug 20, 2010 5:46 pm
Blog: View Blog (0)


Re: Idea - Double hashing.

Post by WallShadow on Wed Apr 03, 2013 3:05 pm
([msg=74879]see Re: Idea - Double hashing.[/msg])

3vilp4wn wrote:I recently got an idea about how to make a hash more secure against bruteforce, and impossible to dictionary attack.

Here's how it works:
1.) Take the password and hash it, so "admin" will become "21232f297a57a5a743894a0e4a801fc3" (I'm using md5 for this example.)
2.) Take the hash ("21232f297a57a5a743894a0e4a801fc3" in this case), and hash it again, so it becomes "c3284d0f94606de1fd2af172aba15bf3".
3.) Store "c3284d0f94606de1fd2af172aba15bf3" in your database. this limits bruteforce attempts to 32 character hex strings, and stops dictionary attacks on the first hash, and takes only twice the CPU.

Can anyone spot any flaws with this?


OOOOO, a fun crypto problem at last! <3

Lets start from the top;

you can have a dedicated server recompute the dictionary, thus you will still be able to perform the dictionary attack. Though that would require the re computation of the entire database and at double the time. But what we can do instead of double hashing the entire dictionary? single hashing the hashes section of available md5 dictionaries. that way we don't need to waste time double hashing it.


Another of my hypothesis;

Collisions become *slightly* more frequent. Let me explain:
Let H(m) be your secure hashing function
Let a, b, c, d, e, f all be passwords that you will be hashing
Let:
H(a) = c
H(b) = c
H(c) = d
we don't care about H(d)
H(e) = f
H(f) = d
Let Alice, Beatrice, Elanor be users, and each use the passwords a, b, e, respectively.

First example; single hashing database;
Alice uses password a, it hashes to c
Beatrice uses password b, it hashes to c
Elanor uses password e, it hashes to f
# collisions = 1

Second example; double hashing database;
Alice uses password a, it hashes to c which hashes to d
Beatrice uses password b, it hashes to c which hashes to d
Elanor uses password e, it hashes to f which hashes to d
# collisions = 2

Thus we have shown a terribly hypothetical scenario where double hashing has caused additional unnecessary collisions. Hence you *can* also say that a birthday attack is more applicable. Though this is purely hypothetical and might not come into play until you have ~1 mil passwords where this might occur some 1 to 10 times. maybe.
So you better goddamn salt those passwords >:(



And finally, lets consider the fact that collision finding attacks have already greatly reduced the time it takes to find a collision for a given hash. Although your method would increase the time it takes to find the collision, it only does so by 2 times. a quick math calculation:

the best attack so far takes 2^21 time to find a collision. to find a collision by brute force, it would technically take 2^128 time because of the 128 bit digest size. you double the time it takes for the best collision finder, as such it would take 2 * 2^21 = 2^22 . By comparing the times 2^128 and 2^22, you barely put a dent in it. For reference sake, 2^21 time is said to take only a few seconds on a regular computer.



As cent said, it's best to simply move on. Go on to SHA-2 or better yet SHA-3, use the larger hash sizes (if you have a choice between 256 bits and 512 bits, use 512), and salt it all.


Reference: https://en.wikipedia.org/wiki/MD5
User avatar
WallShadow
Contributor
Contributor
 
Posts: 613
Joined: Tue Mar 06, 2012 9:37 pm
Blog: View Blog (0)


Re: Idea - Double hashing.

Post by 3vilp4wn on Wed Apr 03, 2013 6:07 pm
([msg=74889]see Re: Idea - Double hashing.[/msg])

centip3de wrote:Why not skip that and just go for SHA-2? There has been no significant attack on it (released, anyway). Seems a bit easier and safer to me.

There only needs to be one flaw...
But, yes SHA2 would be better.
The point of double hashing wasn't really security, but having a fun crypto problem to think about :D

WallShadow wrote:you can have a dedicated server recompute the dictionary, thus you will still be able to perform the dictionary attack. Though that would require the re computation of the entire database and at double the time.

*facepalm*
Where was my brain when I said that? O.o

WallShadow wrote:But what we can do instead of double hashing the entire dictionary? single hashing the hashes section of available md5 dictionaries. that way we don't need to waste time double hashing it.

Huh, true. That way the hash tables would take up half as much space and take half as long to compute. It would still take the same amount of time in the CPU (or GPU) though.

WallShadow wrote:Collisions become *slightly* more frequent.

True, but it's not noticeable unless you have some several million users.

WallShadow wrote:And finally, lets consider the fact that collision finding attacks have already greatly reduced the time it takes to find a collision for a given hash. Although your method would increase the time it takes to find the collision, it only does so by 2 times. a quick math calculation:

the best attack so far takes 2^21 time to find a collision. to find a collision by brute force, it would technically take 2^128 time because of the 128 bit digest size. you double the time it takes for the best collision finder, as such it would take 2 * 2^21 = 2^22 . By comparing the times 2^128 and 2^22, you barely put a dent in it. For reference sake, 2^21 time is said to take only a few seconds on a regular computer.

True. When I was thinking of this, I was thinking of the type of hash cracker that computed hashes on the fly. For that, it would take twice as long to crack correct? Or have I misunderstood you?

WallShadow wrote:As cent said, it's best to simply move on. Go on to SHA-2 or better yet SHA-3, use the larger hash sizes (if you have a choice between 256 bits and 512 bits, use 512), and salt it all.

Yeah, like I said, the purpose of this wasn't really to use it, more to have a fun crypto problem to think about.


Thanks explaining that to me :)
Do not mistake understanding for realization, and do not mistake realization for liberation
Evil Ninja Hackers
???
٩(͡๏̯͡๏)۶

1A4EAMboaXpgvUSmtRbVRqbfJrbyuGhyoo
User avatar
3vilp4wn
Poster
Poster
 
Posts: 144
Joined: Sun Feb 10, 2013 2:05 am
Location: The darkness.
Blog: View Blog (0)


Re: Idea - Double hashing.

Post by WallShadow on Wed Apr 03, 2013 7:18 pm
([msg=74894]see Re: Idea - Double hashing.[/msg])

3vilp4wn wrote:
WallShadow wrote:But what we can do instead of double hashing the entire dictionary? single hashing the hashes section of available md5 dictionaries. that way we don't need to waste time double hashing it.

Huh, true. That way the hash tables would take up half as much space and take half as long to compute. It would still take the same amount of time in the CPU (or GPU) though.


by this i mistakenly named it a dictionary, where it is actually a rainbow table. you could take a pre-computed rainbow table, take the md5 column of the rainbow table, and then compute the hashes of those. that way, you only have to perform a single hash operation per password, instead of a double hash operation as what you would have to do with a dictionary attack.



3vilp4wn wrote:True. When I was thinking of this, I was thinking of the type of hash cracker that computed hashes on the fly. For that, it would take twice as long to crack correct? Or have I misunderstood you?


Dictionary attacks can be used when you want a specific hash to be cracked. hash collisions finders on the other hand are used to find 2 strings that have the same hash value (meaning you'll find the passwords of random users, not of 1 specific user). now that i rethink it, doing a double hash will complicate the process of collision finding because most collision finders don't have a setting to 'find strings that look like hashes', however it is possible. Though the thing with collision attacks only comes into play when you have very large lists of passwords such as a million. look into the birthday paradox if you want to see what i'm talking about.
User avatar
WallShadow
Contributor
Contributor
 
Posts: 613
Joined: Tue Mar 06, 2012 9:37 pm
Blog: View Blog (0)



Return to Web

Who is online

Users browsing this forum: No registered users and 0 guests