Hashing Collision

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

Post Reply
pixelDepth
Forum Newbie
Posts: 3
Joined: Tue Aug 22, 2006 3:27 am

Hashing Collision

Post by pixelDepth »

Hey Guys :)

I read a post in a thread (Sha256 - Code Snippets) that said doing something like this...

$password = md5(md5($pass));

...increases the chance of a collision.

Here is the post by jshpro2...
jshpro2 wrote:hashing an already hashed string increases the chance of a collision. It is possible to migrate to a new hash, you add a new field to your database that will store the sha256 hashs when users log in, and then proceed to authenticate on the md5 like usuall. once everyone has logged in once (or the majority of users) you switch your login sequence to check the sha256 values intead, after that works remove the md5 field. For users that did not login, you reset their password to a random string and email it to them. Much more secure.
Just wondered why that would be?

I myself use Sha256 by feyd (thanks mate ;)).

Cheers :)
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

I'm no expert, and I can't seem to search it using my keywords but my understanding of it is this. It's not definite that the resulting hash will be lower in strength, it's just more likely.

Hashing relies upon entropy.

Defintion of entropy: A measure of the degree of disorder. Often used in Physics/Chemistry.

That's how hashes works. A good hash has high entropy, and thus the likelihood of generating that same hash from another value will be very small (many millions or billions to one). If you then hash that hash again, the entropy of the resulting hash *may* be slightly lower. I have no clue of the inner working of this so I can only make an educated guess that trying to increase entropy of something with high entropy stands more possibility of being lower in entropy than what you had originally.

Let's see what the wikipedia says: Hmm... actually not a lot ( http://en.wikipedia.org/wiki/Hash_collision )
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Post by jayshields »

Where's iamsure these days? :lol: :(
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

I'd rather not get into the math of hashing as it's quite complex, so I'll say this: yes, hashing is about entropy. A double hash, such as the one posted, removes almost all the entropy. I only have to find a hash collision for the first hash. Your code takes care of everything else. Sound like you're wasting time? In all probability the message hashed first is weak. Instead of trying to obfuscate it, increase the entropy by using a one-time pad. You'll get better results if your message is over one block size. The key being a one-time pad, as in you use a different one every time.

The block size for md5 is 256-bits or 32 bytes while the block size for sha256 is 512-bits or 64 bytes.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

feyd wrote:the block size for sha256 is 512-bits or 64 bytes.
Hmm, then why is it called sha256 and not sha512?
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Oren wrote:Hmm, then why is it called sha256 and not sha512?
The output of it is 256 bits.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

Thanks feyd :wink:
pixelDepth
Forum Newbie
Posts: 3
Joined: Tue Aug 22, 2006 3:27 am

Post by pixelDepth »

Thanks guys :)

feyd,

Hope you don't mind me asking...

What do you need to be able to create an algorithm like Sha256, or even any of the md's (md4, md5 etc)?

I've taught myself the bitwise operators, I know how they work, but I have yet to write my own version of any algorithm out there (md5 for example). I know there are scripts out there already, but it's more of a learning thing then anything else, just want to better my knowledge in this area.

Do you need some Math degree? If so, i'm out :p

Cheers, and thanks for your Sha256 script :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

pixelDepth wrote:What do you need to be able to create an algorithm like Sha256, or even any of the md's (md4, md5 etc)?
To make a PHP version of one or create your own, name-in-lights? A PHP version requires reading, understanding and implementing the specification for the algorithm. It involves a lot of complex math and only gets more complex the more secure and larger the hash becomes. To create your own (that would be accepted at large) requires a cryptographic background, publishing papers and being open to the scrutiny and crazy math or the cryptographic community. It takes quite some time for a hashing function to be considered strong as they are initially all considered weak until their math and strength can be proven.
pixelDepth wrote:I've taught myself the bitwise operators, I know how they work, but I have yet to write my own version of any algorithm out there (md5 for example). I know there are scripts out there already, but it's more of a learning thing then anything else, just want to better my knowledge in this area.
The cryptographic specification papers on the various algorithms come with sample hashes and often include the register states for the entire hash to get that result so it's fairly easy to test once you get the algorithm in a processing state.

For SHA256 there were no other pure PHP solutions at the time (as far as anyone on the board could find at least) so I had no example versions to base mine off of. The Javascript version found uses operators PHP does not have, so the PHP version requires a bit more work to do the job. In the end, I ditched trying to even copy an existing version from another language and went right to the NSA source paper.
pixelDepth wrote:Do you need some Math degree? If so, i'm out :p
I do not have a math degree as of right now.
pixelDepth wrote:thanks for your Sha256 script :)
My pleasure. It was my little contribution to it.. I hope to release v2 of it at some point relatively soon (being within six months or so.) SHA512 and SHA1024 are in the cards too, I just haven't gotten around to them just yet.
pixelDepth
Forum Newbie
Posts: 3
Joined: Tue Aug 22, 2006 3:27 am

Post by pixelDepth »

Thanks for the information, I think it may be a little beyond me. I just don't have the Maths to do it :)

I look forward to v2 and future versions.

Cheers.
Post Reply