"A Comprehensive and fundamentally innacurate guide"
Saying they're unique is just very very wrong.
How Hash Algorithms Work (2007)
21–30 of 61 posts
Re: How Hash Algorithms Work (2007)
#22>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?
> If you are given the value of what 'cat' hashes too but you didn't know what made it, you would never be able to find out that 'cat' was the original word.
This is false or inaccurate at best too. More correct would be that it should be computationally infeasible for any one entity to have any reasonable chance to obtaining the inverse of a hash, in the foreseeable future.
With all hashing functions in existence, it's always theoretically possible to find the inverse, and that should be pointed out.
Re: How Hash Algorithms Work (2007)
#23>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 collisio…
> 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).
That is way overkill - the input domain could just be strings of words. Each word of a typical English text adds about one byte of entropy (2^8 states). We get a probable collision by having a number of text states around the square root of the number of hash states (because of the birthday paradox). So, sqrt(10^48) = 10^24 = (10^3)^8 which is about (2^10)^8. So the space of ordinary 10-word strings is big enough to give a sha-1 collision, without invoking inputs like binary files.
Re: How Hash Algorithms Work (2007)
#24The title probably should be 'Cryptographic Hash Algorithms'. The definitions from the post are approximately true for cryptographic hashes but not really for hash functions in general.
Does anyone have a "more" comprehensive guide they can recommend? There were parts of this I really liked but some of the "why" left me confused.
Re: How Hash Algorithms Work (2007)
#25Title is missleading. From the title I expected something about how to design a hash algorithm, but the article is just a walk through the specific operations SHA-1 performs w/o further explanation.
Can anyone recommand resources about the actual design of (cryptographic) hash algorithms?
Re: How Hash Algorithms Work (2007)
#26Earlier quoted context omitted.
> 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.
>They do. >All hash functions have collisions. This is wrong. There is something called a perfect hash function: https://en.wikipedia.org/wiki/Perfect_hash_function >a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is a total injective function. They are very handy for hash tables with constant worst-case lookup…
While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guarantees over the frequency of collisions.
In the more general case, for a hash function with n bits output, the pigeon hole principle demands that we have a collision at least every 2^n inputs.
Re: How Hash Algorithms Work (2007)
#27It's a nice article, although they probably need to say that they're talking about cryptographic hashes earlier on, at least mention that some hashes are very easy to find collisions with.
Re: How Hash Algorithms Work (2007)
#28What is the name of the hashing algorithm broken down in the article?
Re: How Hash Algorithms Work (2007)
#29This is really a walk through of the SHA-1 algorithm.
It's also worthwhile to note that the statement that a hash takes a string and reduces it to a fixed length string is a little misleading. They really work at the binary level and this is seen in the example where the input is converted to binary assuming ASCII and the output hex encoded.
Re: How Hash Algorithms Work (2007)
#30This is really a walk through of the SHA-1 algorithm. It's also worthwhile to note that the statement that a hash takes a string and reduces it to a fixed length string is a little misleading. They really work at the binary level and this is seen in the example where the input is converted to binary assuming ASCII and the output hex encoded.
This is really a test of ycombinator users.