Couldn't we create a string that produces the same hash as another string in SHA-256?

Question

Let's say we have a separate hashing algorithm called s2 and it would convert Hello into dug84nd8.

If we could take the algorithm and just reverse engineer it to generate a string like 8GN492MD that would also output dug84nd8, wouldn't it say that (s2("Hello") = s2("8GN492MD")) == true), and let a hacker in?

I feel like that I am missing something, but I don't know what it is.

Answer 1

Your premise has a flaw. You say you want to 'reverse engineer' the hash function. There's no need to reverse engineer it - its implementation is public.

What you can't do is invert it (perhaps that's what you meant), because it's not invertible. You can easily tell it's not an invertible function because the size of the domain (possible number of inputs) is greater than the size of the range (possible number of outputs). The range is 2^256 (possible output states) and the size of the input space is infinite (technically 2^(2^64) apparently, but much larger than 2^256). And that's precisely what permits the collisions (by the pigeon hole principle, there must be more than one possible input for each output - at least for one of the inputs).

The hash function's whole design makes it computationally hard to find those collisions. There are three properties of hashes (first pre-image resistance, second pre-image resistance and collision resistance) which describe that property more exactly.

So the answer to your question is that the design of the function makes it purposely hard to achieve that even if you know exactly how the function works.

For details (in a slightly different context) of how functions can perform surprisingly (why for instance it is impossible to "step backwards through them" to invert them), see the answers here.

Answer 2

You are mixing the attacks on the hash functions. The formal definition of generic attacks on cryptographic hash functions can be found at Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton. Simply can be given as;

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

• The Second Pre-image attack (also called weak-collision): given a message m1, find another message m2 such that m1≠m2 and Hash(m1)=Hash(m2). An example is producing a forgery of a given message.

• The Collision attack (also called strong-collision): Find two inputs that hash to the same output: a and b such that H(a)=H(b), a≠b.

SHA-256 is not broken for any of these generic attacks, yet. See: What makes SHA-256 secure? on crypto.stackexchange.

if we could take the algorithm and just reverse engineer it to generate a string like 8GN492MD that would also output dug84nd8

• If we only consider this it is pre-image attack and the cost is O(2^256) for SHA-256. Note that the aim of the pre-image attack is not finding the original input, it is rather finding an input that has the same hash value. If there is no external test for the input, one cannot decide that the found pre-image is the pre-image. And, the actual search space for the pre-image can be much larger than the pre-image attack handles.

  There is a variant of pre-image attack, that occurs when the message space is short, like hashing the phone numbers. In this case, it may very easy to find the pre-image.

If we could take the algorithm and just reverse engineer it to generate a string like 8GN492MD that would also output dug84nd8, wouldn't it say that (s2("Hello") = s2("8GN492MD")) == true), and let a hacker in?

• If we consider above in more simple terms; given Hello and dug84nd8=SHA256(Hello) and find another message with the same hash value as you requested then this is the Second Pre-image attack and the cost is O(2^256) for SHA256.

The Second Pre-image is what you are looking for. That is infeasible and not only SHA-256 but also none of the cryptographic hash functions are broken in this way.

• The collision attack cost of SHA-256 is O(2^128) due to the birthday-attack with a 50% probability. In the collision attack, the attackers are free two choose the a and b. This is not your case since you start with a fixed message.

The conclusion, any of these attacks are not feasible for SHA-256 as of 2020.

---

The errors in the topmost answer

The range is 2^256 (possible output states) and the size of the input space is infinite (technically 2^(2^64) apparently, but much larger than 2^256). And that's precisely what permits the collisions (by the pigeon hole principle, there must be more than one possible input for each output - at least for one of the inputs).

SHA256 input space is limited due to the padding standard of NIST. One can hash at most 2^64 bits therefore there are at most 2^(2^64) different messages since the size of the message is encoded at the end of the padding in 64 bits.

The pigeonhole principle only says that there is at least one pigeonhole that has more than one pigeon. It doesn't talk about others that can be empty or not. With this, we can say that at least there must be one collision. Interestingly, we don't know that a SHA256 restricted to 64 bits attains all 64-bit values. What we expect from SHA256 is it is indistinguishable from uniformly random.

You can easily tell it's not an invertible function because the size of the domain (possible number of inputs) is greater than the size of the range (possible number of outputs).

That is not correct, too. Take modulo 2^256 as hash then it is non-invertible. One, however, given a hash value can calculate a pre-images easily, given x, a;; x+k 2^265 are pre-images. In other words, we inverted the map. The correct definition is a function which is computationally infeasible to invert

Answer 3

and let a hacker in?

Sure. But the thing is that we actually don't know how to find another string that produces the same hash in an efficient way. At least for SHA-256 and other widely used hashing algorithms. Note that these algorithms are public, no reverse engineering is needed, which doesn't change anything. This is simply too hard, and in fact those algorithms are deliberately designed in such a way.

The whole problem boils down to solving f(x)=y equation for some function f and some y. One possibility is to scan all x, assuming the domain is enumerable. But that's inefficient and works only if we already know that a solution exists (which I'm not sure whether all values of SHA are attained multiple times). Other possibilities are often not known.

Perhaps this is an educational issue. In school we are often told to solve equations. Linear, polynomial, logarithmic, sine, etc. What they don't tell you is that they choose these equations in such a way that they are solvable and in a relatively easy way. But in fact even now the most briliant minds don't know how to solve majority of equations out there. And here you've stumbled upon one such (extremely important) example.

Note that the situation may (and already did for other hash functions) change in the future.

Answer 4

I believe @kelalaka's answer is the most accurate, but I wanted to add an example that may hopefully shed some light on the issue.

First off, you are completely accurate that you could follow back all the logic in the circuit and eventually get a collision. However, one of the characteristics of a good cryptographic hash function is that this exercise is substantially as difficult as just randomly guessing.

Consider the following circuit. M1-M3 are the bits of the message. Given a message 101 and a seed of 1, we get an output of 1.

Now, let's try to find a different message that collides with 101 by tracing back the circuit. From the output, we know that M3 could be 1 or 0. Let's pick 0; that means the other leg must be 1 (1 XOR 0 is 1). Now we come to M2. We'll also pick 0 again. Now we look at M1. We'll pick 1 for M1. But, uh-oh. The seed would now have to be 0. 100 only works as a message if the seed is 0.

Obviously, in this very simplistic example, we could have just trivially assigned M1 to be 0, and then our seed would have been 1 as we expected. But the point of this example is to highlight the feedback and chaining elements that make this simple "just retrace the circuit" approach much more complicated in a real cryptographic hashing algorithm. The "circuit" required to implement these algorithms is extremely complicated, because it consists of multiplication, exponentiation, modular arithmetic, etc. And the recursive nature of some of these calculations make tracing the circuit backwards a massive branching exercise. Again, it's not impossible; rather it's just as hard as randomly guessing.

Answer 5

"Trying randomly until you find any input that produces the correct hash." Yes, but it is still a brute force attack. This is the premise of a rainbow table attack. Pre-compute values so that you have one input for every possible output. Then instead of trying all possible inputs, you can only try a subset of inputs that produce unique hashes. It doesn't matter if you get the exact input that was the original password because the system can't tell the difference.

Here are the problems:

1. You have to find the input for each hash. As other answers have said this is "quite slow" with modern hashing functions since it is just brute force. (Unless you have a quantum computer sitting around.) The main benefit of a rainbow table is that for functions where you CAN calculate this then you can calculate all of them once and reuse the results over and over without recalculating (trading the space of storing all those values for the time savings of not having to recalculate them).
2. You don't get the actual password out. In many cases, people are attacking less secure systems not because they want to break into those systems but to take advantage of people who reuse passwords/logins on other, more interesting systems.
3. If the attacker doesn't know the target hash and has to check against the target system, then it can be blocked by restricting the number of incorrect attempts. (The attacker knowing the target hash can be blocked by other basic security practices.)
4. Salt. Adding another string that is unique to the user to the password before hashing it. Just for example, say we add the username to the end of the password before hashing it. Now we have to find a string that, when the username is added to the end, computes to some hash. Since the username is unique to each user, we can't precompute this in bulk, we are back to doing it one by one...very inefficient, aka takes impossibly long.

Answer 6

You probably mix "reverse engineering" and finding an "inverse function". These are different concepts.

Reverse engineering is deducing the algorithm from its (closed) implementation. SHA-256 algorithm is public and you can skip the reverse-engineering part altogether. Just look in Wikipedia, or the source code of some open source crypto library.

In order to break the crypto (in your case, to find a "hashing collision"), you need to find an an "inverse function" - in the same math sense that the square root is inverse function of the square.

Hashing algorithms that are used for cryptography are specifically designed to resist finding collisions and inverse functions. If someone finds an easy way of finding collisions, the corresponding hash function is considered compromised and people stop using it. That's what happened to MD5 or SHA-1 functions.

There are other hashing functions (e.g. made for use in the database hash tables) that are NOT made to be that much resistant against collisions, but are computationaly cheaper and/or have other advantages. They still called hashes, but are used in their respective fields and not in cryptography.

Answer 7

Destroying information

When computing a hash function, information is destroyed at certain stages of the algorithm. This is the key to why you can't "run the algorithm in reverse."

If you start with the hash ccb92793f8a87a695fa3f2e805779da8, working backwards, there may be billions of possibilities of how the previous stage got you to that value. No problem—pick one and go through the next stage; same deal. After several stages you reach a point where you get stuck and can't go further; you have reached an impossible intermediate state. So you have to go back and make a different choice and your billions start multiplying. If there are enough stages, this becomes harder than brute forcing the inputs, so you might as well just do that instead.

Answer 8

All the other answers are all correct and cover certain aspects, nevertheless I want to show another approach.

What you - more or less accidentially - found out is the inevitable connection between hash functions and the pigeonhole principle.

If you look at the definitions, it is quite obvious:

• A hash function is a mapping from a domain containing data of arbitrary size onto data (a bit array) of fixed size.
• The pigeonhole principle says: If there are more pigeons than holes, then there has to be at least one hole with at least two pigeons within.

For the input domain, you may have longer passwords and of varying length, and the symbol set is typically larger (small and capital letters, digits, some symbols). These are the pigeons.

The number of possible hash values is easy to calculate: If the length is n out of b symbols, then there are b^n possible hashes (you may set b=2 to count bits). These are the pigeon holes.

So, you have more pigeons (possible input data) than holes (possible hash values), and so there has to be at least one pigeon (possible input data) placed into (mapped onto) a hole (a hash value).

Of course, in this case the function is never injective, and hence not bijective, and hence not invertible.

Answer 9

It's too much for a comment, so I'll add it as a answer:

A small trick that might help: Say you algorithm is $a * $b, if you have 3 and 4, you get 3 * 4 = 12. You now have the outcome which you can not reverse (was it 1&12, 2&6, 3&4, 4&3, 6&2 or 12&1?), but it has multiple collisions. In this case 6 different inputs would result in the same result, so we have 6 collisions.

One 'trick' to minimize that chance (which will never be zero if you have a finite of charaters of the resulting hash) is adding more bits. That means that the outcome will be eg 1862534 for 3&4 as input, and 2&6 could become 6793439.

Answer 10

Let's say we have a separate hashing algorithm called s2 and it would convert Hello into dug84nd8.

.. a string like 8GN492MD that would also output dug84nd8 ...

What you describe is a "hash collision".

And yes: In this case both Hello and 8GN492MD would be accepted as valid passwords.

I feel like that I am missing something, but I don't know what it is.

First:

You didn't write that the attacker knows the hash value (dug84nd8). However, it seems to be obvious that you wanted to write it.

Second:

Hypothetically it would always be possible to find some string like 8GN492MD that has dug84nd8 as output if you had enough computation power (maybe a large quantum computer).

However, the functions that are used to calculate the string 8GN492MD from the string dug84nd8 are so-called "one-way functions".

These are functions that can be calculated quite easily on a "normal" computer; however, it is not known if it is possible at all to calculate the reverse function (finding the string 8GN492MD when the string dug84nd8 is known) within a realistic time (for example less than 10 years).

And of course it is also not known how this can be done if it should be possible.

Indeed, it sometimes happens that some mathematician finds a way how to find a collision. This means that the mathematician finds a way how to find the string Hello or 8GN492MD when the string dug84nd8 is given.

If this happens, you cannot use the hash function (the function calculating the value dug84nd8 from the value Hello) any longer and you have to replace the hash function by another one. Otherwise you'll have a security problem.

Answer 11

Others mentioned the use of the terms "reverse engineering" and "attacking" etc., so I won't respond to this. But for your question:

Consider hash(a) = x;

Now you know x. Let's say you have access to immense computation power, like a botnet, or maybe a giant server farm. Now, in theory, you could start producing hashes, i.e. hash(b) = y; hash(c) = z and so forth. With enough time, you could probably find a function hash(something) = x. So, you would kind of compare the outputs against each other until you found a matching pair.

I personally don't know how much time this would take, but I think it would be possible. But, I guess there are better ways to steal a password, like a social engineering attempt, or breaking in on the client's machine rather than on the server.

Answer 12

There are many great technical answers. I'll try to provide something more approchable: an example.

Imagine, my secret algorithm is this:

• I take an input number,
• add all the digits,
• multiply the sum with each digit,
• then repeat the process.

So 234 would come down to (2+3+4)+2*3*4 = 216. (2+1+6)*2*1*6 = 108. That 108 is the hash. With your understanding of my algorithm, can you calculate a number that ends up being 108? If you can't, you have to guess. That looks easy here, but imagine these numbers being thousands of digits long...

Disclaimer: I suck at math, you probably can actually crack that one. SHA is another beast.

Answer 13

Most hashing algorithms are one-way because if you reverse the operation of the hashing algorithms it will also act as a hashing algorithm (maybe not a good one).

Say for example you have an algorithm called SHA256(). And you then implement a function with exactly the reverse operation of it called REVERSE_SHA256().

What will happen is that the output of REVERSE_SHA256(SHA256(INPUT)) will not match the INPUT:

INPUT = "some string"
HASH = SHA256(INPUT);
OUTPUT = REVERSE_SHA256(HASH);

OUTPUT != INPUT

Not only that, but for a cryptographically secure hashing function the OUTPUT cannot be rehashable to the same value:

HASH2 = SHA256(OUTPUT);

HASH2 != HASH

That such an algorithm can exist is why cryptographic hashing functions exist.