More on Hashing Functions - Security Series #4.2.1
Ben asked me a question this morning in the comments section of my last post. I started to answer and realized the
answer was getting WAY too long (and wide) for the comments section, so I am making a follow up post.
Ben Asked "Just so I am clear on Hashing, it is possible for two strings to result in the same hash value, right?"
Thanks for the question, Ben. I probably should have explained that better.
Yes it is possible for input values to have the same hash value, but depending on the hash function you use it becomes less and less likely to the point of being nearly impossible.
Two input values having the same hash value within a hash function is called a collision. Some hash functions have stronger "collision resistance" than others.
I showed the example of the MD5 hashing of the phrases "Jason" , "Model-Glue", and "SR-71 Blackbird".
472D46CB829018F9DBD65FB8479A49BB
2429B9A443D9C21B0698ADBE2F6E01C0
10F1C46CAF873486E530570E7A298BBB
472D46CB829018F9DBD65FB8479A49BB
2429B9A443D9C21B0698ADBE2F6E01C0
10F1C46CAF873486E530570E7A298BBB
Well, here are those same values hashed with SHA-256
7FA8A6E9FDE2F4E1DFE6FB029AF47C9633D4B7A616A42C3B2889C5226A20238D
5E8C4FBCDA824FD5E6FADC815E4C0F11E0867D585DFBB79F11369FAE9F2A7A74
E153B4C97FCFAC7016A276461E06504CB9F03B9A3ADF36072E1EC7F21308736B
7FA8A6E9FDE2F4E1DFE6FB029AF47C9633D4B7A616A42C3B2889C5226A20238D
5E8C4FBCDA824FD5E6FADC815E4C0F11E0867D585DFBB79F11369FAE9F2A7A74
E153B4C97FCFAC7016A276461E06504CB9F03B9A3ADF36072E1EC7F21308736B
And here they are hash with SHA-512
27166A235CD42FB7E5A45CB89F542760373DCDC779E1697DB283013718904201D4D05537E63FD3815B596511C8704C50791C7BA3C504CAB516E622BDC6EC09C9
C6F942199C90F77E55F08D36A5C5313EF97C31963DC54D9982351224C542BF580759C3101E8A92A9C703A2904E264626679CB5E68FBCB06A2DADDEC78813862E
4FF17CC3794CAB06B880FDA5507692ADBE5BA74EDFE570611F944F43DFFE4F0A0BED2F9CBC37FE1659336038ECABE47423FFA8FC8403459D7406E13A80173259
The SHA-512 hash probably won't even fit properly on this page.
So you can see that the chance of a collision becomes much smaller.
If we were to pass infinite strings of a length greater then the fixed-length of the hash, it is assured we would find a collision. But if you limit the length of your users passwords to 25 characters, and have a UUID hash of 35 characters then those 60 characters string should never yield a collision in a 128 character hash resulting from SHA-512.
So you can see that the chance of a collision becomes much smaller.
If we were to pass infinite strings of a length greater then the fixed-length of the hash, it is assured we would find a collision. But if you limit the length of your users passwords to 25 characters, and have a UUID hash of 35 characters then those 60 characters string should never yield a collision in a 128 character hash resulting from SHA-512.
I forgot to link to the previous post. Here it is.
http://www.12robots.com/index.cfm?event=showEntry&...
I really need to get SES URLs ;)
I must say Jason, I'm loving this security series. I've used some of these concepts before, but without really understanding the reasoning behind each.
You've succinctly explained these concepts in a way that I can easily grasp and (hopefully) will be able to implement just as easily in my own apps.
Looking forward to the rest of the series!
@Pete
Hey, thanks! That really means a lot. I've not been blogging for very long, and it is really nice to read feedback like that. I've been getting so few comments that I sometimes wonder if people were reading.
Again, thanks. I enjoy doing this, and it encourages me to hone my skills, so I plan on continuing. I just hope I can keep up the pace.
@Jason,
Looks good. When you mentioned "collision" that this is what was meant. I also didn't realize that different hashing functions resulted in different length strings. I had just always assumed that it came back with a 32 character string. This is really good to know (especially when you are designing your database schema to hold hashed values).
Thanks for clearing it up. I agree with Pete - the security series is most helpful!
@Ben
Thanks. I'm glad I was able to make it clear. I realized after your question that I did not really explain those topics very well. It's such a big subject. I probably could have made 2 more posts out of it. And maybe someday I will :)