10
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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'$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is not an efficient construction (i.e., not polynomial time) so I don't think that it necessarily reflects what happens with polynomial-time constructions. $\endgroup$ – Yehuda Lindell Jan 12 '18 at 5:21
  • $\begingroup$ @YehudaLindell In regards to the input length N it has the same complexity as SHA256. The lookup + random number generation is only done for 256-bit values so the complexity of that sub-function in regards to N is actually O(1). $\endgroup$ – Tobias Bengtsson Jan 12 '18 at 5:29
  • $\begingroup$ Several probs with your "I'm a hash function" thin. Most important: the table of stored values will quickly grow beyond feasibility of storage and handling. Furthermore, you're wrong when saying Infeasible to find two different messages with the same hash value: YES (in fact, impossible) as you're only handling 256 bits… which voids your imposible as there are only that many pidgeon holes to fill until you' end up producing a collision yourself due to the fact you've run out of space. And to put a tongue-in-cheek ending to it: you're a nice target for timing attacks as well as brute-force. $\endgroup$ – e-sushi Jan 12 '18 at 5:32
  • $\begingroup$ @TobiasBengtsson Looking again at your answer, it's not a hash function anyway since it requires state and requires a secret value. $\endgroup$ – Yehuda Lindell Jan 12 '18 at 6:39
  • $\begingroup$ @e-sushi A timing attack is only possible with a weak implementation. The table size issue is dependent on what the function is used for, some hash functions are used for a short time and then reseeded, for example Python's hash(). Regarding the brute force and pigeonhole issues, I'm not really sure how it is worse than SHA256 itself. Note though that I was sloppy when I wrote this and introduced an error, I've edited now but maybe that was the issue you referred to. In any way, I never said that this was a good algo :) $\endgroup$ – Tobias Bengtsson Jan 12 '18 at 12:49

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.