2
$\begingroup$

It is often said in judicial opinions and legal briefs that the hash value derived from a file is like a fingerprint that uniquely corresponds to the source file. While this may be true in a practical sense, I question whether it is literally true. It is my understanding that the hash function is a many-to-one function, and therefore multiple source files could produce the same hash value. I understand that the utility of the hash function is that making a small change to a source file does not result in a small change to hash value derived from that file.

$\endgroup$
  • $\begingroup$ If any of the answers did address your question, you can accept it via the green checkmark on the left. If not, I reckon asking the 4 answerers for details or clarifications is the best option. $\endgroup$ – Clement C. Aug 23 '18 at 20:19
  • $\begingroup$ Thank you for your help. $\endgroup$ – GAS4 Aug 23 '18 at 20:26
0
$\begingroup$

It is my understanding that the hash function is a many-to-one function, and therefore multiple source files could produce the same hash value.

An arbitrary file, with many million bytes is mapped to a few bytes typically. So there ought to be collisions.

For a good cryptographic hash function it is however hard to compute a message which results in a given has value. See e.g. preimage attack.

In the legal community, hash codes are generally taken as being unique identifiers.

Note that this is a mapping from a huge set (e.g. $2^{8\cdot 10^6}$ possible elements) to still a very large set (e.g. $2^{160}$ elements).

I understand that the utility of the hash function is that making a small change to a source file does not result in a small change to hash value derived from that file.

It should result in a noticeable change in the hash. E.g. see the properties listed here.

$\endgroup$
  • $\begingroup$ Can I add a topic from another discipline (e.g., Law) to an answered question? How? Thank you. $\endgroup$ – GAS4 Aug 20 '18 at 19:08
  • $\begingroup$ @GAS4 What do you mean by "add a topic"? $\endgroup$ – Clement C. Aug 20 '18 at 19:17
  • $\begingroup$ My question is currently under the topic hash function. I wanted to add the topic law, so that people from that group will see the question. $\endgroup$ – GAS4 Aug 20 '18 at 19:19
  • $\begingroup$ @GAS4 I don't think [law] is a tag that exists on Math.SE, unfortunately. $\endgroup$ – Clement C. Aug 20 '18 at 19:29
  • $\begingroup$ I know, It’s on a different stack exchange site. I just thought there might be a way to copy it onto that site by using the topics. But I guess not. No problem. Thank you. $\endgroup$ – GAS4 Aug 20 '18 at 19:31
0
$\begingroup$

Yes. People have created examples of this for many popular has functions. See this answer.

$\endgroup$
0
$\begingroup$

Yes, different files can produce the same hash value. As you say, a hash function goes from a "big" discrete space $\mathcal{X}$ to a smaller image space $\mathcal{Y}$, and is thus many-to-one.

A good hash function, however, will take images "as uniformly distributed as possible" on $\mathcal{Y}$, in order to minimize the probability (over the input) that such a collision occurs.

(For many applications, one would also ask that the hash function be "hard to reverse-engineer" -- see the crypto paragraph on the Wikipedia article.)

$\endgroup$
  • $\begingroup$ Thank for confirming this. In the legal community, hash codes are generally taken as being unique identifiers. See for example, ca5.uscourts.gov/opinions/pub/17/17-41116-CR0.pdf. I think it would be helpful to articulate, at the appropriate technical level, the point made in your second paragraph, regarding good hash functions. $\endgroup$ – GAS4 Aug 20 '18 at 18:28
  • $\begingroup$ @GAS4 This is what's roughly explained in this other paragraph. One more formal way to capture it (with no randomness in the choice of the input $x$ ("the file"), but instead in how the hash function is chosen (at the beginning of the program, randomly from a small-ish family of hash functions $\mathcal{H}$) is captured by the concept of universal hashing. $\endgroup$ – Clement C. Aug 20 '18 at 18:33
  • $\begingroup$ Basically, if you have a family $\mathcal{H}$ of hash functions from $\mathcal{X}$ to $\mathcal{Y}$, the universal hashing requirement asks that for any two (arbitrary, worst-case) different inputs $x,x'\in\mathcal{X}$. $$\Pr_{h\in \mathcal{H}}[ h(x) = h(x') ] \leq \frac{1}{|\mathcal{Y}|}$$ where the probability is over the (uniformly random) choice of $h$ from $\mathcal{H}$. $\endgroup$ – Clement C. Aug 20 '18 at 18:36
  • $\begingroup$ Note that such a guarantee is for all $x\neq x'$, so even if $x$ only differs from $x'$ by a single bit, the hash should differ with high probability. @GAS4 $\endgroup$ – Clement C. Aug 20 '18 at 18:38
0
$\begingroup$

Yes. At least for the common hash functions, different files can produce the same hash, because those hash functions return byte arrays of constant length.

This is easily proven by the fact that there is an infinite number of possible files, and only a limited number of hashes. For example, for SHA1 there are $2^{160}$ possible hashes, for SHA512 $2^{512}$, etc. (And obviously there is an infinite number of files. E.g. start with "0", and add another "0" ad infinitum.)

But it might be possible to construct a hash function of variable length for which the answer would be no. See this answer for some ideas on how to do that. Though that would depend on calling a variable output-length function a hash function.

$\endgroup$

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.