7

I am not a computer scientist, but would like to understand hashes such as SHA-256 more. Am I right in believing that a hash is simply a statement that a file produced a specific output (the hash), and that it does not contain the original file’s data in any way? Therefore, if someone had the hash of a file, the only way that they could recreate the original file, even with all the computing power in the world, would be to recreate files themselves randomly until they had one with the same hash?

Or more simply:

A hash is a unique serial number for a unique computer file. The serial number contains nothing about the file. The only way to know anything about the file is to recreate it independently through trial and error, where the hash offers nothing but confirmation that the created file matches the original.

  • 3
    The wiki on the topic should cover your questions: en.wikipedia.org/wiki/Cryptographic_hash_function – schroeder Jul 22 '18 at 18:47
  • For the most commonly used hash functions, at least, e.g. MD5, SHA-1 and SHA-2 (SHA-256, SHA-512, etc.), you are essentially correct. Obviously, one cannot answer your question with a short yes/no answer for all hash functions in general, because you could construct any hash function that either does or doesn’t do what you describe. – caw Jul 23 '18 at 22:11
4

May contain, or may not. For example, taking the first letter of a message as a hash is possible. It may be a good hash algorithm for a particular purpose, but definitely it is not a good cryptographic hash.

So I will suppose that your question is about the cryptographic hash.

Ideal cryptographic hash algorithm have (beside other) these properties:

  • It is infeasible to generate a message from its hash value except by trying all possible messages.
  • A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value.
  • It is infeasible to find two different messages with the same hash value.

(In real world, replace the word "infeasible" with "highly improbably".)

So, just the first of these properties shows that you are almost correct in your statement

The only way to know anything about the file is to recreate it independently through trial and error, where the hash offers nothing but confirmation that the created file matches the original.

as there are some issues with it:

  • The set of all messages is infinite, so there is no possibility to perform an exhaustive search.

  • In the context of the blind searching the hash don't offer confirmation that the created file matches the original as there are inherently many and many collisions (same hashes for different messages).

  • It is highly improbable that you find even 1 file (message) with the given hash, so the "trial and error" method will give you nothing but errors.

| improve this answer | |
3

A hash is a mapping from arbitrary-length input to a fixed length output. A common misconception is that hash functions should not have collisions (instances where two inputs get the same hash). This is wrong. There must be an infinite number of collisions by the pigeonhole principle, since the mapping goes from an infinitely large input to a fixed-length output. However, a good hash function should make it very hard to find collisions.

A bad hash could be constructed by having a single value map to 0 and any other value map to 1. From this, it would be trivial to determine that a hash of 0 means the file's original data was a. Here's an implementation:

def bad_hash(x):
    if x == 'a':
        return 0
    return 1

Good hashes are designed to ensure that it is computationally difficult to perform any reverse mapping (to go from a hash to an input that would generate the hash), and to ensure that a hash could be reversed into an infinite amount of input data (so even if you find a value that hashes to the target, other input values would also hash to that same target).

Therefore, for a good hash function (and sha-256 is certainly considered good), revealing the hash does not reveal what the original data was.

For sha-256, there is no known way to find the input data other than by exhaustive search, and even when you've found it, you cannot be sure that that was the particular input data.

| improve this answer | |
2

Here is a short answer for the non-tech-savvy.

Asking if a good hash

MD5("StackExchange") = f25cb1c6953bb0c62c639f3d7a242ec4

contains any of the original data is a bit like asking, if the result of the modulo operation contains any hint of the original quotient and divisor.

1337 % 2 = 1

In theory - if given only 1 - an adversary could guess after a reeeeeally long time that you used 1337 and 2 as the original quotient and divisor to get to 1. If you think about this in the context of files and massive amounts of data, the guesswork becomes insurmountable. It's like shooting into the air with a shotgun and trying to hit a specific air molecule. Possible, but really hard.

In this case it would be really easy to find another quotient and divisor that give the same result. But that is not the case for a normal hash function.

When you find an input that creates the same hash as a second one, that is called a collision. For instance 1337 % 2 = 1 and 1339 % 2 = 1 would be just that. When a good hash function is used, it is near impossible to find collisions. If it is not, it is considered cryptographically insecure. That is a rather complex topic that is broadly discussed on this site and Cryptography StackExchange. A typical end user does not need to worry about this.[citation needed]

| improve this answer | |
1

You cannot derive the original data from a hash.

It's like trying to re-create an object given some stacks of various atoms with no other information whatsoever.

Further, the same hash can be obtained from different data (even if the occurrence is extremely rare and hard to obtain intentionally - paper here) which is called a SHA collision (in the case of SHA) which renders a proof-related to a hash not 100% valid.

| improve this answer | |
0

and that it does not contain the original file’s data in any way?

A hash is essentially a function of f(I) -> O so there's always a relationship between I -> O. If you're given O you can compute a set of values that produce O when given to the hash. For a cryptographically strong hash function... this is equal to brute-force but consider this scenario. Let's say you tell your boss that he/she's an b0d7afc8ffd4ec4150ce9bba29f20969 then it wouldn't take long for them to figure out what you were trying to say.

The serial number contains nothing about the file. The only way to know anything about the file is to recreate it independently through trial and error, where the hash offers nothing but confirmation that the created file matches the original.

A cryptographically strong hash contains nothing about the data it was derived from... except for the fact that it was derived from some input and the only way to know what was in the file is to create all possible files and see if their hashes match.

| improve this answer | |

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.