5 ms·

>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?

• bhaak 10y ago
  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.
• marklgr 10y ago
  > 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).
• jasode 10y ago
  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-there-in-the-english-language https://en.oxforddictionaries.com/explore/how-many-words-are...
  • comicjk 10y ago
    > 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.
• hannob 10y ago
  > 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.
  • blauditore 10y ago
    More precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
  • isolli 10y ago
    To be fair, it is better explained later in the text. But definitely misleading. > Also, it should be computationally infeasible to find any other word which also hashes to '...'
  • winston1984 10y ago
    >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 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 time.
    • halomru 10y ago
      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.
      • chris_va 10y ago
• clishem 10y ago
  > 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.
  • JohnStrange 10y ago
    Not only that it's also false from a practical perspective because you can easily find out that 'cat' was the original word by going through a list of hashes of all English words (>rainbow table attacks). That's why you use salts.
  • fooza 10y ago
    Only now I understand why people use (sic)