16
$\begingroup$

I have seen numerous references on the internet of people describing SHA-256 as generating an "almost unique" hash.

Exhibit A. there are more.

Is there some mathematical basis to the almost uniqueness? I would have thought that as SHA-256 is an evenly-distibuted (?) hash algorithm which can accept any message (infinitely many) as an input and produces a fixed length (finite) hash - then there will in fact be an infinite number of each possible output - which I would think hardly qualifies as "almost unique".

Is there a basis for this statement?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ No. $\:$ Yes; there's no publicly known method that seems likely to find a collision in $\hspace{1.46 in}$ SHA-256 with significantly less than $2^{128}$ work. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Oct 6, 2015 at 11:20

2 Answers 2

Reset to default
28
$\begingroup$

Theoretically, since the domain of SHA-256 contains $2^{2^{64}-1}$ different messages and the value set only contains $2^{256}$ different message digests, there must exist at least one possible output that has more than one possible pre-image.

Another important point is that SHA-256 is a deterministic function. This means that if you hash the same message twice, you will get the same digest both times. Hence, "almost unique" should be understood as meaning that SHA-256 will likely produce a different hash for each different input message. This might be false in an abstract mathematical sense, but it is probably true in a more practical sense:

In practice, uniqueness is not determined by the abstract theoretical non-existence of collisions, but by the practical non-existence of collisions. In order to find a collision in SHA-256, you would probably have to execute the algorithm some $2^{128}$ times. It is unlikely that this will happen anytime soon, even if you count the total number of times SHA-256 will ever be executed by anyone in the entire universe combined.

Does a message "exist" if it belongs to a well defined abstract set, or does it "exist" because it has actually been produced and has been represented by someone or something in the physical reality?

Improve this answer
$\endgroup$
0
1
$\begingroup$

If it were unique, it would be a compression algorithm.

Let me elaborate so you don't attack my thinking.

Since it produces only 2256 numbers simply if you try more than so many inputs that produce a different result you will certainly get the same SHA256. This makes it non unique. If it were truly unique you would be able to reverse it even by trial and error. This would make it a compression algorithm. The first answer therefore covers me.

In practical terms it is almost unique and helpful.

Excuse me but my name is SimpleCoder. I am an electronic engineer not a cryptographer so perhaps I am stating the obvious.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Assuming random input of some length, almost all of them can not be compressed, which is related to the Kolmigorov complexity. So that function should be named "Compression-in-rare-cases-only". $\endgroup$
    – tylo
    Commented Jul 21, 2019 at 16:58
  • 1
    $\begingroup$ Welcome to crypto.stackexchange - Please consider using the "edit" link beneath your answer to add detail and an explanation for your conclusion. $\endgroup$
    – Ella Rose
    Commented Jul 22, 2019 at 0:53
  • $\begingroup$ @SimpleCoder I hope you can elaborate on this thought-provoking response. $\endgroup$
    – Patriot
    Commented Jul 22, 2019 at 1:29
  • 1
    $\begingroup$ This isn't true. A CRC is absolutely immune to certain classes of collisions relating to its size and choice of polynomial, but CRC is not a compression function. A trivial example is the parity bit, which can be thought of as a 1-bit CRC with polynomial $x+1$. It produces a unique checksum with 100% certainty for any two messages differing in an odd number of bits. Would you consider parity bit to be a compression function? $\endgroup$
    – forest
    Commented Jul 22, 2019 at 7:59
  • 1
    $\begingroup$ If it were unique and reversible it would almost be a compression algorithm. However it would need to generate a shorter or same-length output for every given input. $\endgroup$
    – El Ronnoco
    Commented Jul 22, 2019 at 16:29

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.