How Hash Algorithms Work (2007)
metamorphosite.com
How Hash Algorithms Work (2007)
1–10 of 61 posts
Re: How Hash Algorithms Work (2007)
#2>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing.
Don't hashing functions have collisions?
Re: How Hash Algorithms Work (2007)
#3>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?
Yes. This is trivially obvious by reasoning that a hash is a function that maps arbitrary data to data of a fixed size. There must be collisions otherwise it couldn't hash any possible string.
Usually you want a hash that maps similar strings to completely different output hashes (and I guess that's what the author actually wanted to describe). But that is not a necessity of a hash function, just a usual property.
Re: How Hash Algorithms Work (2007)
#4>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?
> Also, it should be computationally infeasible to find any other word which also hashes to [...]
He knows there are collisions, he just chose to start with the simplest explanation and add the useful details as he moves on. It's fine by me, even though engineers tend not to like that (they prefer accuracy from the word go).
Re: How Hash Algorithms Work (2007)
#5>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?
You're right but I'm guessing the writer is thinking of the limited list of English "words".
1.46 x 10^48 = sha1 possible outputs
~7.5 x 10^5 = total English words [1]
If you computed all ~750,000 hashes for all known English words, none of the sha1 hashes will match sha1("cat"). I'm guessing that you still wouldn't get a collision if you include all words from all world languages.
For "words" to generate a collision, you'd have to increase the input domain by allowing "words" to mean any sequence of bytes (e.g. bytes of jpg image or audio file).
[1] https://en.oxforddictionaries.com/explore/how-many-words-are...
Re: How Hash Algorithms Work (2007)
#6>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?
> Don't hashing functions have collisions?
They do. The text is somewhat misleading and not properly explaining that.
All hash functions have collisions. But from a cryptographically secure hash function we expect that nobody is able to find such a collision. They exist, but the computational power to find one is not available to humans.
Re: How Hash Algorithms Work (2007)
#7>The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. Don't hashing functions have collisions?
> Don't hashing functions have collisions? They do. The text is somewhat misleading and not properly explaining that. All hash functions have collisions. But from a cryptographically secure hash function we expect that nobody is able to find such a collision. They exist, but the computational power to find one is not available to humans.
More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
Re: How Hash Algorithms Work (2007)
#8As someone extremely new to this; can this procedure be worked backwards to retrieve the original text? If no, why not?
Re: How Hash Algorithms Work (2007)
#9As someone extremely new to this; can this procedure be worked backwards to retrieve the original text? If no, why not?
You can't retrieve the original text because information is lost in the process and many inputs hash to the same value. However, if the range of inputs is relatively limited, you can try hashing inputs until you find the right hash (see rainbow tables for discovering user passwords from the hash value).
Re: How Hash Algorithms Work (2007)
#10As someone extremely new to this; can this procedure be worked backwards to retrieve the original text? If no, why not?
Not all operations are reversible, which makes it difficult to work out a simple inverse. Of course you could work backwards to find out which inputs could lead to a particular result, but this set of possible inputs would grow rapidly as you work your way back through the algorithm, making it nigh impossible to work out the original message, even if you have some idea what it's supposed to look like.
Of course this is assuming that the hash algorithm doesn't have any weaknesses you could exploit.