How do hashes really ensure uniqueness?

Question

This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup.

So hashes are said to generate the same thing for any information it sees, and it's only a one-way interaction.

1. As far as I understand, hashes are just long alphanumeric strings. If one computes hashes across all documents, keys, information, files, etc, over and over again- it's simply a matter of time until the same combination comes up again for different information (applying it across all possible contexts)? This might be an impractical test given size and possibility, yes, but is it this that makes hashes powerful, that it's practically impossible to recreate a hash that for any foreseeable endeavor it's fine, or is there some element that I'm missing that reduces even that extremely low probability to zero?

2. Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash? Or is it simply that the design is so complex that it's simply a futile exercise to dream of such a large computer required for this task?

3. What's stopping a hacker or malicious middle man to hack open the software program or library that creates this "hash" and then use that library to create hashes of his/her own or mislabel some target company's hash with his/her own pointing to their version of the file? Especially since many applications, languages, and developers use hashing independently. Whichever is most weakly secured, we can use that to take on the rest?

Any resources are also appreciated.

Answer 1

The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always gives the same answer; random in the sense that the value of the hash is basically unpredictable without actually computing it. And sufficiently unpredictable that, for a good cryptographic hash, we don't know any way of finding a string with a particular hash, except for trial and error.

In particular, cryptographic hash values are close enough to truly random that the birthday paradox applies. That is, if there are $k$ different values the hash can take and they're all equally likely, you have to hash roughly $\sqrt{k}$ documents before the probability of finding two with the same hash is greater than a half. So, if you're using a 256-bit hash, you'd need to look at about $\sqrt{2^{256}}=2^{128}\approx 3\times 10^{38}$ documents to even have a 50/50 chance of finding two with the same hash. For comparison, that's about 200 documents for every nanogram of mass in the Earth.

Answer 2

Firstly, some definitions;

• Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. Consider storing the hashes of passwords on the server. Eg. an attacker will try to find a valid password to your account.

• Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$. Producing a forgery of a given message.

• Collision resistance : if it is hard to find two inputs that hash to the same output $a$ and $b$ such that $H(a)= H(b)$, $a \neq b.$

---

0) How do Hashes really ensure uniqueness?

As David gave his answer, no they don't' ensure uniqueness. To see this consider a simple hash (imitating the only compression);

$$H':\{0,1\}^{20} \rightarrow \{0,1\}^{1}$$ $$x \mapsto x \pmod 2$$

By the definition; all the even numbers have $0$ as a hash value and odd numbers have $1$ as a hash value.

Another way to see this is the pigeonhole principle. The input size is larger than the hash size, Therefore there exist at least one hash value contains more than one message.

So, there is no uniqueness. But finding another one, a collision, must be computationally infeasible.

1. a) As far as I understand, hashes are just long alphanumeric strings.

Hash outputs are bits, just bits. How you represent them or transmit them is up to the developer.

1. b) If one computes hashes across all documents, keys, information, files, etc, over and over again- its simply a matter of time until the same combination comes up again for the different information

What you said is called a hash collision. By definition of hash, it is inevitable but the finding one must be computationally infeasible. But if your hash function is considered as weak or a new attack occurs you must change it as for MD5 or SHA-1.

$$H:\{0,1\}^* \rightarrow \{0,1\}^l$$

As one can see, for $2^l$ possible hash output there are finitely (since we cannot process infinitely) many possible inputs. The SHA3-512 has only $l=512$ output bits. If the message space is just 1024 bits, then for a given hash value $h$ there are $ 2^{1024}/2^{512}$ possible input values that have $h$ as the hash value.

Picking one at random, you will have $1/2^{512}$ probability to match the hash as long as the hash function behaves randomly. There is an interesting random hash collision on MD4 on e-mule.

1. c) This might be an impractical test given size and possibility, yes, but is it this that makes hashes powerful, that its practically impossible to recreate a hash that for any foreseeable endeavor its fine or is there some element that I'm missing that reduces even that extremely low probability to zero

In the designs of hash functions is it required that finding a pre,second-image and collision must be computationally infeasible. But there is always a negligible chance of the attacker to find one, as in the MD4 case.

2. Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash? Or is it simply that the design is so complex that its simply a futile exercise to dream of such a large computer required for this task?

Hash functions are by design are not invertible functions as permutations. They achive this by2

• Bit dependency: each bit of the output is dependent of the every bit of input.
• Avalanching : a single bit change in the input must change $\approx$ half of the bits randomly.
• Non-linearity: prevent from attacking linear systems solving techniques.

The attacker must find either a preimage or secondary-preimage. A powerful entity can search all possible inputs to match the given hash. These examples rainbow table,hashcat may be not as powerful as you imagine but they are on the edge of computing.

If somehow you find an image that works for the hash value, there is no way to determine that this is the original one, the pre-image.

If your powerful entity is Quantum Computer, don't worry. D. J. Bernstein;

Anyone afraid of quantum hash collision algorithms already has much more to fear from non-quantum hash-collision algorithms.

The quantum computers reduced the complexity of hash collision from $2^{b/2}$ to $2^{b/3}$. The non-quantum computers already achieved $2^{b/3}$ with smaller time, The Rho Machine.^1,2

3. Whats stopping a hacker or malicious middle man to hack open the software program or library that creates this "hash" and then use that library to create hashes of his own or mislabel some target company's hash with his own pointing to their version of the file? Especially since many applications, languages, and developers use hashing independently. Whichever is most weakly secured, we can use that to take on the rest?

Nothing except the hardness of finding a collision. If somehow an attacker is able to find a collision they can execute it. As recently, an identical-prefix collision attack for SHA-1 performed in PDF files to create malicious valid PDFs.

Answer 3

... its practically impossible to recreate a hash that for any foreseeable endeavor its fine or is there some element that I'm missing that reduces even that extremely low probability to zero?

The input space of a practical hash function such as SHA-256 is often limited. SHA-256 has a ridiculously large input message size ($2^{64} - 1$ bits). This is mainly due to the algorithm including the encoding of the amount of bits that are hashed. This will lead to an average of $$2^{2^{64} - 1} \over 2^{256}$$ collisions for each output value of SHA-256. Other hash functions such as SHA-3 don't have this limitation and do allow an infinite message space. In that case it is very likely that there are infinite amount of messages that have the same hash value for that specific hash function.

It should however be computationally infeasible to find a collision: two messages that hash to the same output. This is often the first property to fall if the hash function is broken: collisions have been found of both MD5 and SHA-1, for instance. Finding another input message for an existing hash is much harder, this is known as a pre-image attack.

Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash? Or is it simply that the design is so complex that its simply a futile exercise to dream of such a large computer required for this task?

Yes, cryptographic hash functions are one-way functions by definition and by design. By various techniques the input data is mixed in such a way that the calculation is hard to inverse, but that every bit of output still depends on every bit of input equally.

Whats stopping a hacker or malicious middle man to hack open the software program or library that creates this "hash" and then use that library to create hashes of his own or mislabel some target company's hash with his own pointing to their version of the file? Especially since many applications, languages, and developers use hashing independently. Whichever is most weakly secured, we can use that to take on the rest?

You would expect that such a change to the hash and tests performed on the hash will be found. If you can change the code that verifies the hash then yes, you could probably fool an application. Just like you can change code to completely skip the hash comparison or signature verification.

Answer 4

Your questions are good. The other answers cover them well, but I wanted to provide an answer which addresses your concerns in a less formal way.

As far as I understand, hashes are just long alphanumeric strings. If one computes hashes across all documents, keys, information, files, etc, over and over again- its simply a matter of time until the same combination comes up again for different information (applying it across all possible contexts)?

Techincally, yes, it's possible. But when you start to consider real-world limitations, we see that their uniqueness is reasonable. If you have a 256 bit hash output, that means there are $2^{256}$ possible hash outputs. Technically that means that there could be a collision. However, given that there are an estimated $2^{260}$ atoms in the universe, it would call for a remarkable number of hashes before a collision occurred by happenstance.

But what if that was your goal? What if you made a machine to try hashes until you find a collision? Well, there's interesting physical limits you run into there. By Landauer's Principle, each bit-flip you execute during this process has a minimum amount of energy burned. I did the calculations once, assuming you could do calculations at the background radiation temperature of 2.7K. If you just had a counter, which counted from $1$ to $2^{256}$, at those temperatures, you would have to consume something like 3/4 of the known energy in our galaxy!

So you can't brute force it. What if you're smarter? That leads to your next question

Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash?

Hashing algorithms are designed to be extremely difficult to back-calculate in this way. That property is a major design goal of cryptographic hashes. It isn't perfect. We can only account for algorithms that we are aware of, but we do reasonably well. Consider MD5, which lasted about a decade before we found attacks which rendered it valueless in security applications.

You do find that applications which care about security relevant hashing must keep up with the times, and update to new hashing algorithms which do not have known attacks against them. It's not a perfect approach, but practically speaking its effective.

Whats stopping a hacker or malicious middle man to hack open the software program or library that creates this "hash" and then use that library to create hashes of his own or mislabel some target company's hash with his own pointing to their version of the file?

Nothing. Nothing prevents this at all. This is a completely different sort of problem to solve.

In the practical world, you can often pass a short hash through secure channels more easily than you can pass whole pieces of software.

Typically hashes are not used in that way on their own. Hashes are used in concert with other tools to provide the useful functionality. For example, in digital signing, signing a large database is very computationally expensive, but hashing it and then signing the hash turns out to be a much more efficient process.

Answer 5

1. If one computes hashes across all documents, keys, information, files, etc, over and over again- it's simply a matter of time until the same combination comes up again for different information (applying it across all possible contexts)?

Yes, a good hashing function would give you a random (well, "random") hash for different documents, but once you hash as many different documents as there are possible hashes, you will surely come with the same hash twice.

Is there some element that I'm missing that reduces even that extremely low probability to zero?

Not to zero, but as close to zero as you could possibly need to be. The main factor is that there is simply so many different hashes and that you have no better way to break (recreate) a hash other than to guess randomly.

2. Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash?

Yes, many operations in the hash are not back-traceable. For example, if a+b mod 100 = 65, you have 100 possible pairs of values (a,b) between 0 and 99 that would add up to 64. Now imagine the same, but with powering and much higher modulo value, that makes it very hard to even list the possible values, and even then you don't know which value it was, and if you guess wrongly, some other computation elsewhere will not add up, it all becomes an exponentionally large tree.

3. What's stopping a hacker or malicious middle man to hack open the software program ...

You don't need a hacker, most hashing algorithms are open source, everyone knows how the hashes are generated (that's the point).

... or mislabel some target company's hash with his own pointing to their version of the file

This is indeed a potentional problem. Private/public keys are used a solution, the company encodes the hash of the document with their private key and releases the result (a so called signature), and then everyone can verify the signature against the document's hash with the company's public key. The only weakness is that the attacker can send you theirs public key disguised as the company's public key and then sign a counterfit document with their private key, and you would be none the wiser. Unless you use a verification authority and require a valid licence for the public key, which your browser does right now if you see https:// at the start of the URL address.

Also note that hashing, symetrical encription and private/public keys are 3 separate things that work differently, however all 3 of them are used together in modern cryptography.

Answer 6

Besides the perfectly fine answers already given, I'll try to provide a bit more-or-less of an ELI5* answer that's not too short nor too long and doesn't go too deep into the specific details.

1. Yes, for each given hashfunction there's a finite number of outputs**; there are inputs (actually, an infinite number of inputs) that result in the same output. This is what we call a "collision". However, because a hash usually results in a 128 bit (or even waaay larger) output and because the algorithms are designed to be hard / impossible to reverse it is hard to force a specific output. It's not impossible but (good) hashes in use currently today are infeasible to brute force (given the current state of technology; in 10, 20 or maybe 50 years things may be very different but by then we'll have newer / better hashes too (probably)). The chance of a collision is, for a given hash, about 1 in ... a lot. But because of the finite number of outputs the number of possible collisions is, by definition infinite. You just have to search a HUGE space of inputs to find the exact input you need. For some weak(er) hashes there may be shortcuts, besides brute forcing. you can take to find a collision.

2. I talked about this in point 1 a little. The design of a hash may or may not be complex but in all cases the algorithms are out in the open. No secrets there. Any algorithm that relies on keeping the actual algorithm secret will eventually (and usually sooner than later) fail. See Kerckhoffs's principle: "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge" or Shannon's maxim. A lot of hashes, at some point or another, rely on a modulo operation. Here's an intro to one-way hash functions for some more in-depth detail than this post will provide (archived version here, just in case).

3. The algorithm, software program or library is (or should be) already in the open. There are hashes that were fine in the past but turned out to be flawed (MD5 for example, is considered 'broken'). Besides 'hackers' there's a bunch of people called Cryptanalysist who's job it is (or who enjoy) looking for weaknesses or flaws in cryptographic algorithms. It's safe to assume that, over time, more algorithms will follow MD5. How many, and at which rate, is another matter. A lot of algorithms are, currently, widely regarded as perfectly safe / good to use (as long as it's used as intended). There's a lot of (widely) known and even lesser known hashes. You can read more about attacks here.

_{* In case you're unfamiliar with the term: Explain Like I'm 5 (years old).
** There are perfect hash functions but those only work for a 'fixed size' input.}

Answer 7

Hashes ensure uniqueness, when they are secure and wide-enough. That's much more certain than closing a tap ensures the water does not run, when the tap is not broken and of the appropriate model.

That's because then we know no feasible method to find two distinct inputs that yield the same hash; even though we know, by the pigeonhole principle, that there are such inputs.

The practitioner applies that, using a 256-bit hash (giving 128-bit security) like SHA-256 to guard against current attacks; or a 512-bit hash (giving 256-bit security) like SHA-512 to guard against any foreseeable progress, including hypothetical quantum computer. In such setups, collision do not happen. We should rather fear penetration of the computer, global warming, and comet impact.

---

Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash?

Assuming a secure and wide-enough hash as above, the only known strategy to find the original data is to try possible values of that original data, hashing them, until finding one which hash matches. It is then practically certain that the original data was found (proof: if it was not, knowledge of the original data would allow to exhibit two different values with the same hash, and we can't!).

Thus a design constraint that can prevents a very powerful computer to back-calculate the original data from a hash is that so much information is missing to the attacker about the original data that s/he can't compute the hash of enough candidates for the original data.

For example, given the SHA-256 hash of a 16-digit Credit Card number, it is possible to find that number with at most 10¹⁵ hashes (the last digit is a Luhn check digit). That's <2⁵⁰ hashes, a non-trivial but perfectly feasible amount of SHA-256 hashes (at time of writing, bitcoin reportedly performs >2⁶⁷ hashes per second, thus we are talking more than a hundred times what they collectively perform in a thousands of a second).

If on the other hand what's hashed is a 16-digit Credit Card number followed by 256 bits (or 43 base-64 characters) uniformly random and unknown to the attacker, her or his tasks is hopeless.

Answer 8

I'll focus on this part of the question:

Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash? Or is it simply that the design is so complex that it's simply a futile exercise to dream of such a large computer required for this task?

No, you cannot back-calculate the original data from a hash, for the very simple reason that there's an infinity of inputs that can have the same hash. So what you could do is find some input that has the same hash output (a collision).

As others have explained, doing this by brute force is quite hard, and in the end, you may end up with an input that has no relationship whatsoever with the "original" input.

For instance, if the original input was "James Kumar agrees to pay $100" and the hash was 1f262e0cdd8af3928ed8933b0a2cb2bacf6be1d168130dc11af0fa61f952c8cf, you may find an hypothetical other input "AJIUZEBGIUZEBGIZNOIBZIUFBIB" with the same hash (not the case here, of course). But that input is meaningless.

So even though you found a collision (which, again, is quite difficult), that collision is quite useless.

Finding another input which has the same hash and makes sense and provides an advantage to the attacker is quite a lot more difficult. Unless there is a flaw in the hash function, of course.

Answer 9

There are some excellent answers here to the OP's actual questions so I wont go over old ground, but there is one aspect about hashes that has not really been touched on that might improve the OPs understanding of hashes and what they are good for.

By definition, a hash function maps data of arbitrary size to data of fixed size. In other words, the hash value tells you practically nothing about the input value used to generate it, not even its length, making reverse engineering effectively impossible. Yes it is possible to produce input data that produces the same hash value, but it is not possible to take a hash value and work out what the input data that produced it was, which makes hashes very attractive to cryptographers.

An example of an extremely simple but very commonly used hash is the parity bit; this is set true (1) or false (0) to indicate whether the number of bits set in the input is even or odd. Change one bit in the input and you get a different parity - extremely useful for a quick corruption check! It doesn't matter if the input is the complete works of Shakespeare or a number between one and ten. Of course, if you change an even number of bits, then the parity doesn't change (you have a collision!), but you have still managed to detect 50% of all possible tamperings with a very simple check and only a single bit. Each bit in your hash gives you $2^n$ possible results and reduces the number of potential collisions by ${1}/{2^n}$ so even quite small hashes produce very useful results very quickly. For example, a 16 bit hash can detect $1 - 1/{2^{16}} = 99.998\%$ of all possible tamperings. Another way of saying the same thing is that a $n$bit hash can catagorize arbitrary input data into $2^n$ distinct pigeonholes making it extremely useful for efficiently indexing, accessing and organising data.

Answer 10

A 32 byte digest (like bitcoin's) can only have 256^32 possible values. If hashing 1K byte blocks, there are necessarily going to be 256^1024/256^32 (a very large number of) collisions. But still, good luck finding one.

Answer 11

Hashes, as you have observed, are not guaranteed to be unique for every input - they can't be, as they are of finite size, with potentially infinite inputs. They only "group" inputs into outputs (in the context of using hashes in data structures, this is sometimes referred to as a bucket). This is still useful.

By way of example, a very simple hashing function might be "given a non-empty, single-byte-character string input, use the first byte as the hash". Consider the properties of such a function:

• Works for infinitely many arbitrary inputs (a string of any length).
• There are at most 256 different output hashes (aka. buckets).
• It is impossible to reconstruct the input, from only looking at the output. No matter how powerful your computer, it simply can't be done!

Even a very simple hashing function like this might be useful for some purposes (very simple dictionary data structures perhaps) - a comparison between two inputs can check their hashes, and trivially reject the possibility that they are the same 255 times out of 256. This could make a data structure using it quite a lot faster. But, if two inputs resulted in the same hash (known as a "collision"), the whole of each input would need to be compared, to see whether they are really the same or not.

Of course, such a simple hash function would be useless for hashing something like a password (and pretty poor for data structures too). A good hash function would have additional properties:

• Sufficiently many output buckets for the task at hand. (For a data structure or file system hash, where collisions slow things down a little bit but are otherwise harmless, this might be 2^32 or much less. For a password, where collisions could breach security, this might be more like 2^512 or more!).
• Even distribution between buckets. (Taking the first byte would probably put almost all strings in the same few dozen buckets - "A", "B", etc. - leaving 200 or so buckets empty).
• The whole of the input should contribute to the hash. (Not just the first byte!)
• On average, changing a single bit in the input changes half the bits in the output.

And depending on the purpose to which the hash will be put, there will be other considerations too:

• Execution speed; slow fixed-time hashing functions can help defeat timing attacks in secure applications, but fast hashing functions are more performant if the hash is being used in a data structure for example.
• Secure applications may want to add a random "salt" to the input before calculating the hash, to prevent looking up the input from a list of known outputs; that's somewhat out of scope for this question though.

The important thing to understand is that a hash does not guarantee uniqueness - it only assigns a confidence level to whether inputs are the same or not. This could be fairly weak (for file systems or data structures with a 32-bit hash) or very strong indeed (for passwords with a cryptographically secure 512-bit hash).