2
$\begingroup$

This might be a very easy question. Let's consider cryptographic hash functions with the usual properties, weak and strong collision resistance and preimage resistance.

For any given output, obviously there are multiple inputs. But is that necessarily an infinite number of preimages, for any given hash value?

How would I go about giving a formal proof that there exists no crypto hash function $h$ such that there is a given value $v = h(m)$ for which the possible set of inputs $m^*$ is finite? Would this necessarily break collision resistance?

$\endgroup$
  • 1
    $\begingroup$ Small note: commonly actual hash algorithms include the size of the input somehow in the padding, so hashes such as SHA-2 do not accept infinite input (but trying to input $2^{128}$ bits of data for SHA-512 is about as infinite as it comes). $\endgroup$ – Maarten Bodewes Feb 15 at 22:54
  • $\begingroup$ While the current answers point out that it is not necessary for a cryptographic hash function to have this property, I think that all CHFs that are used in practice do have this property. I think most of those functions have an even stronger property: a uniform distribution of outputs. Proving this is an other thing though. $\endgroup$ – Paul Feb 16 at 12:21
  • $\begingroup$ @Paul yes, thanks. I was trying to find out whether that is a necessary feature, is that a consequence of the required properties, or is that some kind of a "coincidence" that we happen to design such hash functions. While the answers below do answer my formal question, I'm also interested in the above. Apparently a uniform distribution is not a requirement, yet practical hash functions do seem to distribute their output uniformly. $\endgroup$ – Gabor Lengyel Feb 16 at 13:16
  • 1
    $\begingroup$ @GaborLengyel Well, if a CHF has a uniform distribution of outputs, then the probability that two arbitrary messages have the same hash is $2^{-n}$, where $n$ is the number of output bits. If the output is not uniform, this probability is higher. So a not-uniform CHF is possible, but you need more output bits for the same cryptographic strength. $\endgroup$ – Paul Feb 16 at 15:10
5
$\begingroup$

For any given output, obviously there are multiple inputs.

This is not true. Namely, for any is not true. There are outputs such that multiple inputs produce them - this is consequence of pigeonhole principle. But we cannot claim that this holds for any output for any hash function. This can be true for some specific hash function only.

... proof that there exists no crypto hash function ...

There is no proof because this statement is simply false. Here is a simple example of a hash function that has many hashes that have finite number of preimages.

function hash(x){
    if (x.length <= 64) {
        return 
            '1' ||
            '0000000000000000000000000000000000000000000000000000000000000000' ||
            sha3(x);
    } else {
        return
            '0' ||
            sha3(x) ||
            '0000000000000000000000000000000000000000000000000000000000000000';
    }
}

The number of inputs that produce hashes starting with '1' is finite.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Insightful, thank you. Yet practical hash functions seem to have a uniform distribution of values and I struggle to really understand where that comes from, why that looks like the best. I think if distribution is really uniform, all outputs will be assigned to an infinite number of inputs. $\endgroup$ – Gabor Lengyel Feb 16 at 13:19
  • $\begingroup$ @GaborLengyel: "seem to have a uniform distribution" - cryptography is not the field where you can rely on feelings. Examples: 1) Message 0100100001100101011011000110110001101111 seems to be random, but means "Hello": 01001000 = 0x48 = 72 = 'H', etc. 2) Let's encrypt some text with a Caesar cipher. The results seems to be impossible to decrypt... for the most people, but not for a student who is studying math or cryptography. 3) The Windows random number generator (en.wikipedia.org/wiki/CryptGenRandom) seemed to be random and secure enough. We can only rely on a proof. $\endgroup$ – mentallurg Feb 16 at 14:37
  • 1
    $\begingroup$ I understand that (I learned some crypto a while ago), and in a way that's exactly the point. Are these crypto hash outputs actually uniform, could that be proven for a specific algorithm? Because they seem to be. :) If that's the case, would my original question (in the title) be true for that hash? I'm not expecting an answer, I was just thinking about this. Thanks for your input! $\endgroup$ – Gabor Lengyel Feb 16 at 14:45
2
$\begingroup$

We expect the cryptographic hash functions look sort of random (completely undefined). We expect them to have relatively well-distributed output. If a cryptographic hash function has finite or no output on any value on the range, I'll be surprised.

The basic requirement for hashing is the collision resistance and this requires nothing beyond that.

One, however, can design one by using any secure existing cryptographic hash function that doesn't produce some outputs. Consider the SHA256 that has classical generic 256-bit pre-image and secondary pre-image resistances and 128-bit classical generic collision resistances. Now consider a new hash function SHA256x defined as:

$$\operatorname{SHA256x}(m) = 1\mathbin\| \operatorname{SHA256}(m)$$

The SHA256x has 257-bit output, however, the values $0\mathbin\|\{0,1\}^{256}$, i.e. values starting with zero, never occur. It has the same resistance as SHA256. Of course, such construction has no value at all, other than pedagogically.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Why do we expect "well-distributed output", which I guess would be ~as close to unifrom as possible. You have just shown a hash function that has all the necessary properties, but distribution is not uniform. How exactly is this less practical or less efficient than the known ones? Would known hash function's output only be "well-distributed", or would it actually be uniform? Could there be a hash function that somehow "makes sense" without the "well-distributed" property? I accepted the other answer as that more directly answered my original question, but yours was helpful too, appreciated. $\endgroup$ – Gabor Lengyel Feb 16 at 13:28
  • $\begingroup$ In Cryptography, any bias can be exploitable. Yes, we can design one easily with an existing one. But nobody cares that as long as you are designing a backdoor, etc. Try to design one explicitly, without using an existing one and this or similar technique, it will be hards. In hash functions, while designing the avalanche property/effect is necessary. The random flip in the avalanche effect may imply the close to a uniform but I've no proof for that. $\endgroup$ – kelalaka Feb 16 at 14:43

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.