2
$\begingroup$

Following the discussion on bijectivity and given that function inverse is studied on domain/codomain, I would like to ask whether we can find subsets where this function can be bijective.

Let's say the subset of all alphanumeric strings of exactly 5 characters. The cardinal of this subset should be Arangements of 62 characters in a line of 5 characters = 62! / 57! ~ 776 mln . This is definetely lower than 2^256 . Is this enough to say the function is injective on this domain or do I need to calculate every single value to make this conclusion? What happens to surjectivity in this case?

OBS: I might make confusion with continuous functions so do let me know if I have mistaken something.

Improve this question
$\endgroup$
4
  • $\begingroup$ I just want to ask myself whether the function can have an inverse. What is that inverse at this point I do not care. $\endgroup$
    – Roman Gherta
    Apr 1, 2021 at 14:55
  • 2
    $\begingroup$ In theory, any two different inputs could potentially map to the same SHA-256 hash, even if the chance of this happening is effectively zero. So I don't see any way of guaranteeing an inverse without checking every input. You could use the number of inputs to show the chance of a collision is very small, but you can't rule out a collision without checking each string. $\endgroup$
    – Eugene Styer
    Apr 1, 2021 at 15:17
  • $\begingroup$ SHA-256 can only output $2^{255.3}$ possible values due to collisions at a rate of $1/e$. $\endgroup$
    – Paul Uszak
    Apr 1, 2021 at 22:44
  • 1
    $\begingroup$ @PaulUszak: what you state above is correct for SHA-256 restricted to 32-byte input. It's not for SHA-256 with e.g. 55-byte input, which is expected to reach $>2^{255.99}$ outputs. $\endgroup$
    – fgrieu ♦
    Aug 6, 2023 at 17:03

2 Answers 2

Reset to default
3
$\begingroup$

Of course it is. If you tightly restrict the input domain, then the problem is simple. The function is deterministic, so just inject clusters of random bits within the input domain of interest (domain $A$). You then select unique hashes (co-domain $O$) and discard the colliding input/output pairs to create input sub-domain $B \in A$. You will have nullified collisions and will have a bijection as $B \to O$.

Note: We haven't seen collisions on SHA-256 output domains yet, but the above theory holds. And using this brute force approach, the co-domains become more biased towards a bijection as the input domain deceases in cardinality, as $p(\text{bijection}) \propto \frac{1}{|A|}$ through simple computability.

But I'm having a hard time understanding a cryptographic use for such strange domains. I'm unconvinced that sha256inv would actually exist at all as restricting inputs is kinda cheating. And they still only analytically compute one way as $\text{sha256}:B \to O$ which is due to fundamental pre-image resistance. $\text{sha256inv}: O \to B$ remains elusive. And general $\text{sha256inv}: O \to A$ must remain impossible as you've deliberately eliminated collisions which we know mathematically exist.

P.S. $|A|= 916 \times 10^6$, if you consider 5 no. 62 alphanumeric values chosen by total randomness. That's easily computable on an enthusiast's machine.

P.P.S. My last para refers to your comments.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "a cryptographic use for such strange domains" - privacy preserving encryption would make sense? $\endgroup$
    – hola
    Apr 1, 2021 at 16:16
  • $\begingroup$ So i need to compute the function Image... You are saying this to be sure the function is also surjective... So if I define the function as sha256prime() : 2^29 -> 2^256 , then this function is not surjective and definetely no inverse exists. And this is why I need to basicaly... brute force a 2^29 codomain. This way the function definitely has an and only one inverse and I can bother reading the algorithm of sha256 to search for compositions etc. $\endgroup$
    – Roman Gherta
    Apr 1, 2021 at 17:56
  • $\begingroup$ Applications... I guess it would be a first to say that you found a function sha256inv defined on a specific domain of hashes(the codomain/image computed above... maybe there is something special about that domain) for which sha256inv(hash)=string . And you can do this analytically without saving all these hashes as a map in some database. $\endgroup$
    – Roman Gherta
    Apr 1, 2021 at 17:56
  • $\begingroup$ Paul, related to your last paragraph: It is perfectly acceptable and practiced to restrict domains to make functions invertible, this is not cheating. But I am probably too lazy to follow though with this and the idea that an inverse exists, is enough for me, unless there is a big fundamental problem with this entire approach. Pre-image resistance problem(crypto term) we remove as discussed by eliminating collisions(I wish) and by making the range so small that it is actually feasible for my laptop to make these computations.... $\endgroup$
    – Roman Gherta
    Apr 2, 2021 at 8:47
0
$\begingroup$

As you know, cryptographic hash functions generally produce a fixed-size output while accepting inputs of much larger size. As such, collisions necessarily exist but finding them is prohibitively difficult.

As for the question of: given a particular set of inputs, is there an easy way to determine if there are two elements that have an identical hash ("easy" here meaning substantially less work than computing all of the hashes). The answer has to be no. If that were an easy question to answer, you could use it in a fast algorithm to easily find a collision. The sketch is: increase the range $0..2^k$ until there is a collision. Now run a binary search from each end to find the smallest range that contains a collision. The values you are looking for are the endpoints. You've now broken the hash with O(n) work, where n is the hash length.

Also, your 5 alphanumeric characters calculation should be $62^5$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ And I'm saying that if you could answer that question, then you have proven that the hash is weak. If you assume a strong hash then you can't answer it faster than hashing your domain and checking. $\endgroup$
    – bmm6o
    Apr 2, 2021 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.