2
$\begingroup$

I've been studying digital signatures and hash functions recently, and I was wondering: Do hash functions exist which will never produce collisions?

$\endgroup$
  • 2
    $\begingroup$ Not unless its range is larger than or equal to its domain. Collisions are inevitable in all other cases because of the pigeonhole principle. $\endgroup$ – pg1989 Jan 2 '15 at 2:57
  • $\begingroup$ There exist one-way functions which have no collisions, but obviously their output will be at least the size of the input. $\endgroup$ – CodesInChaos Jan 2 '15 at 15:48
11
$\begingroup$

This is impossible for any generally useful hash: a hash must map all inputs to a fixed-length output, but you normally want to be able to take variable (and fairly long) inputs. The problem is that there are more inputs than outputs: you normally want to be able to hash any string up to a fairly big length, but the hash itself should not be too long, and there are more long strings than short ones.

$\endgroup$
  • 2
    $\begingroup$ Yeah... that's the pigeon principle in action $\endgroup$ – Gianluca Ghettini Jan 4 '15 at 23:36
3
$\begingroup$

Yes they are called Perfect hash functions on wiki. If you follow the link at the bottom of the page there are links to articles and source code. Logically they do not have fixed length output.

$\endgroup$
  • $\begingroup$ Perfect hash functions are not cryptographic hash functions as their domain is finite. $\endgroup$ – Thomas Jan 5 '15 at 15:01
  • $\begingroup$ @Thomas, a nitpick: pers FIPS 186-4, the input domain of SHA-256 (widely acknowledged to be a cryptographic hash function) is bitstrings of less than $2^{64}$ bits, which is a large but not infinite domain. $\endgroup$ – fgrieu Jan 5 '15 at 17:54
  • $\begingroup$ @fgrieu Indeed, but that can be considered practically infinite for most intents and purposes - perfect hash functions on the other hand usually have such a small domain that they can hardly be called cryptographic. most of them, anyway. (in my experience) $\endgroup$ – Thomas Jan 6 '15 at 1:06
  • $\begingroup$ @Thomas So has anyone been able to prove that all perfect hash functions must have small domain where they're not of practical use? If not, the answer is completely relevant, but with a caveat of something like "No perfect hash shown has been found that has a large enough domain to be useful for cryptographic purposes" $\endgroup$ – Steve Sether Jan 6 '15 at 17:09
  • $\begingroup$ A fixed length hash function type exists and are well known for common purposes, logically they will have collisions, none colliding hash functions must be varying length, they also exist. if your for example validating that a file has not changes and want to reduce the probability of a collision then use two functions perhaps something common like md5 then something longer like whirlpool, if the size of the file is also validated the probability of a collision can be held minimum. to be certain you can use a varying length none colliding perfect hash function. $\endgroup$ – vbms Jan 10 '15 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.