Has any crypto hash function been proven to be surjective?

Question

This answer claims that "it is not proven that all outputs of SHA-1 are possible." Has any crypto hash function been proven to produce all possible outputs (i.e., to be surjective over the codomain of all possible numbers $[0, 2^n]$, where $n$ is the number of bits of the hash)?

Answer 1

Has any crypto hash function been proven to produce all possible outputs (i.e., to be surjective…

Not when looking at the practically used hash functions like the SHA-2 family, but when looking at the theoretical constructions we don't tend to practically use… the answer is "yes".

• "No" for practically used hash families like SHA-2

  At least, not when we're talking about cryptographic hash functions we practically use. Actually, the reason for that is pretty obvious if you think about it for a second. Quoting a 2010 answer by Pornin at StackOverflow:

  … surjectivity proof for a random oracle requires an awful lot of computing power, substantially more than mere attacks such as preimages (2^n) and collisions (2^(n/2)). Consequently, a good hash function "should not" allow a property such as surjectivity to be actually proven. It would be very suspicious: security of hash function stems from the intractability of their internal structure, and such an intractability should firmly oppose to any attempt at mathematical analysis.

  As a consequence, surjectivity is not formally proven for any decent hash function, and not even for "broken" hash functions such as MD4. It is only "highly suspected" (a random oracle with inputs much longer than the output should be surjective).

  ^{(emphasis mine)}

• "Yes" for more theoretical hash constructions

  The fact that hashes we practically use don't come with such proof doesn't mean it isn't possible to theoretically create such a hash function. For a nice example of such a construction with implying proof, check Lindell's answer. (Btw.: I would call it an example of a Chaum-van Heijst-Pfitzmann Hash Function instead of attributing it to Damgård like Lindell does, but that's just an aside.)

  The reason(s) why we don't prefer to practically use such hash constructions is a different question.

Answer 2

The answer is YES for constructions of hash functions that are not used in practice. For example, there is a construction by Damgård that is based on the discrete log problem and works by computing $h(x_1\|x_2)=g^{x_1}\cdot h^{x_2}$, where $g$ is a generator of the group. If $h$ is chosen randomly in the group, then it is hard to find a collision in this function, unless you can solve the discrete log problem. By applying the Merkle-Damgård transform, you get a hash function that takes inputs of any length. Thus, this is a collision resistant hash function.

It is easy to see that this function is surjective. Specifically, $g$ is a generator of the group, so for every $h'\in\mathbb{G}$ and for every $x_2$ there exists a value $x_1$ such that $g^{x_1}\cdot h^{x_2} = h'$.

Answer 3

Since the question is whether any cryptographic hash function is proven to be surjective, let me construct a hash function and show that it is

1. a cryptographic hash function, and
2. surjective.

Let's devise a hash function where I am the random oracle. For any 256 bit value you give me, I will give you back a 256 bit value (the hash).

In my drawer, I have a secret table with all the input and corresponding hash values that I have previously calculated. If the value is in there, I simply return the hash value.

If the number is not in the table, I have a (secure) random number generator that will generate a new random number from the set of 256-bit numbers that are not in the hash value column in the table, with a uniform probability distribution. I fill the table with this new key-value pair and hand the hash value to you.

Taken from Wikipedia, a crypto hash function has 5 main properties. Let's see whether they hold in this case:

• Deterministic, i.e. same input yields same output: YES
• Quick to calculate: YES, just need a lookup or a random number generation (though it is of course still impractical for other reasons)
• Infeasible to generate a message from its hash value except by trying all possible messages: YES, it is provably impossible due to the randomness
• A small change to a message yields a totally different hash: YES
• Infeasible to find two different messages with the same hash value: YES (in fact, impossible)

So far, we have only defined a function from 256-bit to 256-bit values. Let's extend this function to the same domain as SHA256 by simply taking the SHA256 value of any input greater than 256 bits, pass this value to the function as defined above, and return the result. EDIT: Removed since it creates a trivial attack, see if you can find it!

Regardless of whether SHA256 is by itself surjective, we can still prove now that the function as a whole is simply by proving that the subdomain of every 256-bit value in the domain maps to a unique 256-bit value in the image of the function, and considering the fact that the subdomain and the image is of the exact same size.

What we end up with is a cryptographic hash function that is provably surjective. Note that there is nothing in the definition of a cryptographic hash function that says it has to be stateless; obviously all "real" ones are for practical reasons. It is much harder to construct such a function that is provably surjective and as e-sushi points out, none of the ones in use have been proven to be that.