133
$\begingroup$

First off, I know hashes are 1 way. There are an infinite number of inputs that can result in the same hash output. Why can't we take a hash and convert it to an equivalent string that can be hashed back to the original hash output?

eg:

string: "Hello World"
hashed: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e 

unhash: "rtjwwm689phrw96kvo48rm64unc8oetb5kmrjiuh7h8huhi6dde5n5"
        (a real string that gives the same hash as "Hello World")
hashed: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e 

...

$\endgroup$
  • 79
    $\begingroup$ The short, but incredibly accurate answer, is that we can't convert hashes back to their input strings because an army of mathematicians has taken great efforts to make it difficult to do so using known means. $\endgroup$ – Cort Ammon Apr 6 '17 at 23:15
  • 73
    $\begingroup$ Why can't we? We can. The algorithm is trivial: try every possible string, ordered by length and then by alphabetical order, until you get one that hashes to the desired value. Making that algorithm run in less than a trillion years is the hard part. There's a very large haystack to search for a very small needle. $\endgroup$ – Eric Lippert Apr 7 '17 at 18:04
  • 1
    $\begingroup$ @EricLippert That's actually incorrect. While finding preimages is possible with sufficient computing power, actually reversing the hashes rarely is due to the pigeonhole princniple. $\endgroup$ – forest Apr 17 at 6:03
  • 1
    $\begingroup$ @EricLippert I agree with forest's comment there. Your comment is wrong. You can not reverse them to the original input as a hash function drops too much of the input information. You'll never know if you've got the correct input... and no computing power in the world can help (unless the hash function is broken/flawed, and even then only in cases where hashInputSize <= hashOutputSize). $\endgroup$ – e-sushi Apr 17 at 6:12
  • 1
    $\begingroup$ Read the question again. $\endgroup$ – Eric Lippert Apr 17 at 13:12
221
$\begingroup$

Take a simple mathematical operation like addition. Addition takes 2 inputs and produces 1 output (the sum of the two inputs). If you know the 2 inputs, the output is easy to calculate - and there's only one answer.

321 + 607 = 928

But if you only know the output, how do you know what the two inputs are?

928 = 119 + 809
928 = 680 + 248
928 = 1 + 927
...

Now you might think that it doesn't matter - if the two inputs sum to the correct value, then they must be correct. But no.

What happens in a real hash function is that hundreds of one-way operations take place sequentially and the results from earlier operations are used in later operations. So when you try to reverse it (and guess the two inputs in a later stage), the only way to tell if the numbers you are guessing are correct is to work all the way back through the hash algorithm.

If you start guessing numbers (in the later stages) wrong, you'll end up with an inconsistency in the earlier stages (like 2 + 2 = 53). And you can't solve it by trial and error, because there are simply too many combinations to guess (more than atoms in the known universe, etc)

In summary, hashing algorithms are specifically designed to perform lots of one-way operations in order to end up with a result that cannot be calculated backwards.

Update

Since this question seems to have attracted some attention, I thought I'd list a few more of the features hashing algorithms use and how they help to make it non-reversible. (As above, these are basic explanations and if you really want to understand, Wikipedia is your friend).

  • Bit dependency: A hash algorithm is designed to ensure that each bit of the output is dependent upon every bit in the input. This prevents anyone from splitting the algorithm up and trying to reverse calculate an input from each bit of the output hash separately. In order to solve just one output bit, you have to know the entire input. In other words, when reversing a hash, it's all or nothing.

  • Avalanching: Related to bit dependency, a change in a single bit in the input (from 0 to 1 or vice-versa) is designed to result in a huge change in the internal state of the algorithm and of the final hash value. Since the output changes so dramatically with each input bit change, this stops people from building up relationships between inputs and outputs (or parts thereof).

  • Non-linearity: Hashing algorithms always contain non-linear operations - this prevents people from using linear algebra techniques to "solve" the input from a given output. Note the addition example I use above is a linear operation; building a hash algorithm using just addition operators is a really bad idea! In reality, hashing algorithms use many combinations of linear and non-linear operations.

All of this adds up to a situation where the easiest way of finding a matching hash is just to guess a different input, hash it and see if it matches.

Lastly, if you really want to know how hard reversing a hash is, there's no better substitute than just trying it out for yourself. All good hashing algorithms are openly published and you can find plenty of code samples. Take one and try to code a version that reverses each step; you'll quickly discover why it's so hard.

$\endgroup$
  • 16
    $\begingroup$ I like this answer because it actually points at the properties of hashes which are used to make the "one way," which is what I think the OP was trying to get at. $\endgroup$ – Cort Ammon Apr 6 '17 at 23:16
  • 9
    $\begingroup$ I think the question aims at "why can't we create a collision for a given hash" - regardless if we guess the right one or not (that might be the equivalent string - where the equivalence relation would be "has the same hash") $\endgroup$ – tylo Apr 7 '17 at 8:05
  • 16
    $\begingroup$ "you can't solve it by trial and error" -> "you can't realistically solve it by trial and error", "cannot be guessed backwards" -> "cannot realistically be guessed backwards", both of these given current technology. It's not that it's theoretically impossible to guess backwards (I mean, if you try every input, you will find a collision, period, even if it takes you 48 bazillion years to do it), it's that it's realistically impossible at the current time and, ideally, well into the future. $\endgroup$ – Jason C Apr 7 '17 at 8:22
  • 20
    $\begingroup$ @JasonC Given the level of the question, I was trying to explain the concept using plain English and a simple example - there's really no need to spell out the pedantic difference between theoretical and realistic outcomes. $\endgroup$ – adelphus Apr 7 '17 at 8:56
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Apr 8 '17 at 10:04
33
$\begingroup$

Cryptographically secure hashes were specifically build to (among other things) make what you're asking hard!

Now, you could try to create an appropriate dictionary of all hashes, hoping to find appropriate pairs... but it would take more storage space than the total storage space that's currently available on our planet and more computing power than you'll be able to get access to in this universe (at least, at the time of writing this) — which is why we call it "infeasable".

In your theoretical example, the collision would be the strings "Hello World" and "rtjwwm689phrw96kvo48rm64..." both producing the same hash a591a6d40bf420404a011733...

For SHA-2 and SHA-3, such pairs are not known up until today. If, such a (once cryptographically secure) hash would have to be considered as broken due to collisions.

$\endgroup$
  • 8
    $\begingroup$ I do not thing that fact of known collision would make SHA-2 or SHA-3 obsolete. If such collision happens "accidentally" it would mean nothing. But if someone could intentionally generate such pair, then yes, it would be broken. $\endgroup$ – Hauleth Apr 6 '17 at 22:46
  • 8
    $\begingroup$ @ŁukaszNiemier I didn't state it "obsoletes" a hash. I wrote would have to be considered as broken (as in "theoretical break"). See, if you happen to stumble over such a collision, it's called a "theoretical break" and if you can intentionally produce such pairs, it's called a " practical break". The first is a warning sign and what I pointed at in my answer, the later is practically a dead sentence. (Even when practically broken, it should be noted there are limited situations and very specific ways you could still use such a hash... but its initial functionality is rendered insecure.) $\endgroup$ – e-sushi Apr 6 '17 at 22:58
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Apr 13 '17 at 1:28
23
$\begingroup$

Strictly speaking, you can, and it stands to reason that you can.

A SHA-1 hash has $2^{160}$ possible values. If we just consider $100$ byte binary plaintexts, well, there are $2^{800}$ possible ones of those. So it stands to reason that for any SHA-1 hash, there are likely to be around $2^{640}$ $100$ byte binary plaintexts that would match it.*

When two inputs have the same hash, it's called a hash collision. For non-secure hashes, it's not particularly difficult to find a collision. It's not even a design goal. For example, Java classes often have a hashCode() method, which generates a hash used to facilitate data structures like a HashMap. But these use algorithms designed to be cheap to run, which produce few accidental collisions. If you want to deliberately craft two objects with the same hashcode, it's usually easy.

Cryptographic hashes are designed, not to make collisions impossible, but to make them extremely difficult to find. That is, if your goal is to find an input that generates a given hash, there should be no way to do it that's faster than brute force -- trying every input in turn until one works.

The maths behind this are well documented -- find a book if you want to; this is not the place to explain it (nor would I be able to).

... and not every collision is useful. Consider a signed email message. There might be a lot of chunks of data that yield the same hash. But only a tiny subset of those look like text. And only a tiny subset of those look like English text. And probably only one of those looks like English text that the purported sender could plausibly have written.

So, you can find collisions using brute force, but brute force necessarily takes a long time, and that's what gives you security. The best cryptographic security is designed such that brute forcing would take longer than the age of the planet (possibly universe!), on our fastest computers.

For example, since there are $2^{256}$ possible SHA256 hashes, you would have a $1/2$ probability of finding one collision if you tried $2^{255}$ different inputs. At a microsecond per attempt, this would take in the order of $10^{63}$ years.

(There are various ways you can improve these odds, for example you could double your chances by searching for two target hashes at the same time -- but the numbers are still huge, and as computer power increases we just move on to longer hashes).

A cryptographic hash is considered to be theoretically broken if anyone finds a way to find a hash collision that's more efficient than brute force.

But even weaker algorithms provide security -- if someone gets hold of my password hash, then spends 5 years finding a collision, well, never mind, I have changed my password by then.


* - I chose SHA-1 for this first example because the is shorter than more current algorithms and we get some easy-to-understand numbers out of it. Note though, that the shortness of the hashcode isn't the only thing wrong with SHA-1; it has flaws such that brute-force isn't the only way to find collisions.

$\endgroup$
  • 6
    $\begingroup$ If you don't hash (and sign) plain text, but e.g. a PDF file, there is enough space in there to hide the "random noise" which a collision gives you. So there will be many "plausibly looking" PDF files with the same hash, not just one. (Of course, it is still difficult to find more than one, except if the hash is broken.) $\endgroup$ – Paŭlo Ebermann Apr 8 '17 at 8:59
  • $\begingroup$ @PaŭloEbermann, actually, it's difficult to find even one, unless the hash is broken. $\endgroup$ – Wildcard Oct 23 '18 at 19:52
  • $\begingroup$ @Wildcard I meant it was difficult to find more than one with the same hash (as each other). Of course each file has the same hash as itself. $\endgroup$ – Paŭlo Ebermann Oct 23 '18 at 20:05
  • $\begingroup$ I'll note that SHA-1 is sufficiently broken that it is possible to generate pairs of "plausible-looking" PDF files with identical hashes but different content. CWI+Google proved this by actually generating a pair of PDF files with identical SHA-1 hashes but different content. They changed the color of the documents, but they could have just as easily changed the text. $\endgroup$ – Brian Apr 17 at 17:06
18
$\begingroup$

I'm taking a guess at where your confusion stems from.

The one-way-ness of hash functions does not relate to the mathematical property of being a not injective function.

A function $f$ that is injective will have different values $f(x), f(y)$ for all $x \neq y$. And indeed hash functions are usually non-injective (this can easily be derived from the fact that their domain is bigger than their codomain). But that is not the meaning of one-way.

Instead saying that a hash function is one-way specifically precludes the thing you want to do, which is to find a value $x$ such that $H(x) = y$ if you already have $y$. In other words given $x$ you can calculate $H(x)$ but going backwards is impossible. Hence, "one-way".

Of course the simple answer, as already given by e-sushi is: Because they are constructed so that it's impossible. :)

$\endgroup$
  • $\begingroup$ Nicely put. This is a good explanation for why modular division (%) isn't really a hash function. If you know that x % 3 is 0, it's trivial to come up with infinitely many values which will hash the same way as x. $\endgroup$ – Alexander Jun 3 at 23:15
6
$\begingroup$

We don't actually know if we cannot reverse hashes. There is no mathematical proof that reversing hashes is hard. Reversing hashes is in FNP, therefore any such proof would be a strong result about hardness of NP (hardness of FNP and NP is trivially linked).

The practical impossibility of reversing hashes (the cryptographically strong ones) stems from the algorithms being designed to remove known (and hypothetical) weaknesses that would make it easy to reverse them.

$\endgroup$
  • $\begingroup$ Although the pigeon hole principle will trump the NP problem in many cases, as typically we hash something wider that it's block width. Thus information is irretrievably lost. $\endgroup$ – Paul Uszak Apr 16 at 10:55
  • $\begingroup$ @PaulUszak This is true. Still, the question specifically asks for any string that hashes to the same value. $\endgroup$ – Rafał Dowgird Apr 17 at 13:26
-6
$\begingroup$
  1. Clarification: The question has a flawed assumption. I mistakenly though in addressing the details of that flaw my answer was making that obvious. Just to make it really clear:

    YOU CAN REVERSE SOME HASHES!!! BEING ONE-WAY IS NOT A REQUIREMENT OR CONCERN OF HASH FUNCTIONS!!! AND EVEN FOR THE SUBSET OF CRYPTOGRAPHIC HASHES IT ISN'T 100% GUARANTEED IRREVERSIBLE!

    You mileage will vary depending on circumstances, but given the right circumstances you can reverse any hash with relative ease (the key in cryptography is denying the person trying to reverse your hashes sufficient information to do so).

  2. Clarification - The question possibly was talking about cryptographic hashes, but did not say so. Just like all dogs are animals, but not all animals are dogs, cryptographic hashes are a subset of hashes, and there are many hashes in general use that are not appropriate to use as cryptographic hashes.

    I can think in my head of a number of ways of making a useful hash function that would not be hard to reverse. You could also use the private/public ssh key pairs to make a hash that is reversible if you have the other key, but not otherwise.

The original answer goes on to explain what "hash function" really means (and being one way / irreversible is not a requirement for a hash function):

Hash in computer science was originally used for "Hash" tables and was concerned with distributing a non uniformly spread input set across a limited output set for efficient indexing. They are generally simplistic for fast execution, and are typically not cryptographically strong.

(A moderately dumb hash function can be as simple as taking the input as a number and getting the modulus of it using a prime number - this means all of the input bits affect the output result, but one possible input value is simply the hash as a bit string with zero padding on the left out to a byte boundary).

wikipedia has a useful short article: https://en.wikipedia.org/wiki/Cryptographic_hash_function

A cryptographic hash function is a special class of hash function that has certain properties which make it suitable for use in cryptography.

Useful reading - it goes into more detail of the reversibility of hash functions intended to be hard to reverse. (Nothing is irreversible given sufficient time and processing power - you could just iterate through all possibilities - you just try and make the effort harder then its worth doing)

see also https://security.stackexchange.com/questions/63052/reversible-hash-function "Is there any reversible hash function?"

$\endgroup$
  • 2
    $\begingroup$ The question isn't asking what a cryptographic hash function is. It is asking what it is that makes cryptographic hash functions irreversible, and you are not answering that question. $\endgroup$ – kasperd Apr 9 '17 at 12:32
  • $\begingroup$ Hopefully its now clear I am addressing the obvious flaws in the question and the expanded details. $\endgroup$ – iheggie Apr 10 '17 at 17:41
  • 9
    $\begingroup$ "The question possibly was talking about cryptographic hashes, but did not say so" the question doesn't need to say so, it's right there in the title of this site. $\endgroup$ – CodesInChaos Apr 10 '17 at 18:46
  • 1
    $\begingroup$ the key in cryptography is denying the person trying to reverse your hashes sufficient information to do so – is incorrect. Fact is, cryptographic hashes obey Kerckhoffs's principle in the same way cryptographically secure ciphers do. As an practical example: everyone knows the internals and workings of SHA-3. Nothing is hidden. Yet no one is able to reverse a hash result back to its input as that's simply infeasable to do so, even though the algo is publically known. $\endgroup$ – e-sushi Jun 19 '17 at 19:08
  • 1
    $\begingroup$ "You could also use the private/public ssh key pairs to make a hash that is reversible if you have the other key, but not otherwise." That's called "encryption" and it's an entirely different action from hashing. I don't want to pile onto this answer, but it is really incorrect, not just slightly incorrect, and yet it sounds plausible enough to utterly confuse any person just beginning in cryptography. So, a -1 from me. $\endgroup$ – Wildcard Oct 23 '18 at 19:56

protected by Maarten Bodewes Apr 10 '17 at 17:38

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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