1
$\begingroup$

I suppose this question addresses surjectivity and injectivity. We talk about collisions but did we prove yet rigidly that this function is not reversible?

EDIT: Accepting the answer based on Dirichlet Box Principle (if domain is bigger than codomain innevitably there will be collisions). I agree that for mappings $h:\{0,1\}^*\rightarrow \{0,1\}^{256}$ the function is not injective and therefore not bijective

$\endgroup$
3
  • $\begingroup$ Just how surjective is a cryptographic hash like SHA-1? any use? $\endgroup$
    – Paul Uszak
    Mar 27 at 18:05
  • $\begingroup$ I think that the good folks here prefer that when "a new question arises", a new question be arisen :-) It keeps the answers more concise. $\endgroup$
    – Paul Uszak
    Apr 1 at 12:50
  • $\begingroup$ Ok, well this question is closed, I will open a new one then $\endgroup$ Apr 1 at 13:19
6
$\begingroup$

Background

  • Terminology

    • Injective : one-to-one
    • Surjective : onto
    • Bijective : one-to-one and onto.
  • Pigeonhole-Principle

    The pigeonhole principle goes back to 1624. We can state it as; if there are $m$ pigeons and $n$ holes with $m>n$ then when the pigeons are placed into the holes, there is at least one box that has more than one pigeon.

    We can look at the traditional example; 101 pigeons and 100 holes. Place each hole one pigeon, and you will get 1 pigeon not placed into a hole so one must put this pigeon into a hole that has already one pigeon. Therefore there is one hole more than one pigeon.

    The pigeonhole principle doesn't state that each hole must be filled. It is possible that 101 pigeons are places into one hole (a big one). This still applies to the pigeonhole principle.

    With a small note: although the pigeonhole principle is a very simple argument it forms the basis of the combinatorics.

  • Cryptographic Hash Functions (CHF): CHF maps arbitrary data into a small fixed hash space $$H:\{0,1\}^*\to \{0,1\}^\ell$$ where $\ell$ is the fixed output size and it is 256 for SHA256 and $\space{}^*$ is the kleene star and in short here it forms a set that includes empty string and all finite binary strings.

    There are XOF hash functions (e.g. SHAKE of SHA3 series) that the output size is determined during the digest request. In any case, one can see that the input space is larger in practice!

    There are 5 main properties we want from CHF's

    1. Deterministic: the same message always results in the same hash value.
    2. Effective: It must be quick to compute the hash value for any given message
    3. Irreversible: it must be infeasible to find a message that produces the given hash value.
    4. No easy collision: finding two different messages with the same hash value must be it is infeasible.
    5. Avalance: Any small change to a message should change the hash value randomly so that the new hash value appears uncorrelated with the old hash value.

    The 3. and 4. have formal definitions that we consider on the security and the below definitions comes from Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.

    • preimage-resistance — for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $x$ such that $h(x') = y$ when given any $y$ for which a corresponding input is not known.
    • 2nd-preimage resistance, weak-collision — it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given $x$, to find a 2nd-preimage $x' \neq x$ such that $h(x) = h(x')$.
    • collision resistance, strong-collision — it is computationally infeasible to find any two distinct inputs $x$, $x'$ which hash to the same output, i.e., such that $h(x) = h(x')$.

Collisions

With the pigeonhole principle there exist at least two input $m_1$ and $m_2$, $m_1 \neq m_2$ such that $\operatorname{SHA256}(m_1) = \operatorname{SHA256}(m_2)$. This implies that collisions are inevitable!

The collision security is bounded by the birthday paradox and roughly for a hash function with $\ell$-bit output, it has $\mathcal{O}(2^{\ell/2})$ cost with 50% probability.

No Injective

Once you have a collision this implies that a function (SHA256 here) cannot be a bijective function, since is not injective. Therefore we cannot talk about an inverse.

Surjective?

Even we don't know that SHA256 is surjective. To see that SHA256 is surjective, one has to find or show that the $2^{256}$ outputs occur.

Finding out this is impossible, since, one at least must try $2^{256}$ distinct inputs and this is infeasible.

On the other hand, showing SHA256 is surjective is problematic since it will indicate that SHA256 is not secure!

If we model SHA256 as pseudo-random function as Meir Moar did and limit the input space equal to output space then a hash value doesn't occur with probability $(1-1/n)^n$ and that is $1/e$ when $n \to \infty$. This is also the portion of the output hash value is not occurs. For the modeled SHA256 this makes $~2^{254.56}$ has values empty.

However, the input space is not limited to 256-bit. In this case, the probability of being empty becomes smaller and smaller $(1/e)^\frac{input-space}{output-space}$. And for both cases, we are still don't know until we look for all values.

If reversible

Assume that SHA256 is reversible then this means that it doesn't have the pre-image security at all. Given the has value one can find the pre-image using the reversible. This is not simple news, you would have heard that immediately.

There is no proof that SHA256 has 256-bit preimage security, however, any attack that has less than 256-bit search will still require substantial work to achieve to break the pre-image resistance. All of the current attacks are on the reduced rounds.

A good example from history is this; MD5 has imminent collisions, however, it has still pre-image resistance ( the best non-brute-force pre-image attack is still slower than brute-force in practice). So, even any collision attack better than the generic collision attack ( the birthday attack), we don't expect that the pre-image resistance will be broken.


The cost of MD5 pre-image attack by 2009 by Yu Sasaki and Kazumaro Aoki.

This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5. The memory complexity of the attack is $2^{45} \cdot 11$ words.

$\endgroup$
8
  • $\begingroup$ Any reason to downvote? $\endgroup$
    – kelalaka
    Mar 27 at 6:53
  • 1
    $\begingroup$ Re. Surjective? : By mathematical nomenclature, a surjective 256 bit input function does not have $2^{256}$ outputs. And surjectivity is proven via the collision rate. $\endgroup$
    – Paul Uszak
    Mar 27 at 20:23
  • $\begingroup$ @PaulUszak that question has limited input size. we did not restrict it here. Added some for this $\endgroup$
    – kelalaka
    Mar 27 at 20:50
  • $\begingroup$ @PaulUszak which one? this question or your question? Can you prove that I did not upvote both or not? Or do you know who upvoted or not magically? Could you check my voting casts? $\endgroup$
    – kelalaka
    Mar 28 at 8:14
  • 1
    $\begingroup$ I really don't get it. If you talk about the pre-image and collision resistance definitions, yes, It is a good definition and I've given the source where it is taken. Rest is my words and of course the influences of the background that I've. $\endgroup$
    – kelalaka
    Apr 1 at 13:47

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.