i get that SHA256 isn’t considered “encryption”, it’s something to do with hashing. so, if i encrypt “hello” into a random string of characters, why is it said to be impossible to decrypt it back to “hello”? if you had a maths equation like P = (k * 10 / G) / (4x * 5gl), it’s possible to work backwards to find the value of k or g eventually. why not with SHA256? is it something to do with random numbers?
In: Mathematics
There’s no proof that it’s impossible to reverse SHA256. There’s a good chance it will go the way of SHA1 and other hashes so that, given a hash, it will be possible to generate a file that has that hash in a practical amount of time. Currently such attacks on SHA256 aren’t publicly known but it’s possible that agencies like the NSA have them secretly.
Hashing algorithms throw away information, meaning the initial data can’t be reconstructed uniquely.
Imagine that I tell you “My (rather poor) hashing algorithm works by multiplying together two numbers: and the result is 162”.
There are a lot of numbers that can be multiplied together to form 162. It can be 6×27, or 2×81, or 18×9, and so on. Any one of these could be the correct answer, but you can’t tell for sure because I threw away important information.
Hashing algorithms do the same thing. They take what you give them, and while they are generating their final result they will use methods (like multiplication or xor) that easy to do one way, but can be impossible to go the other direction without knowing what the original data was.
Once you’ve gotten the final answer you don’t really have any good way to find the original data except by guessing, and there are a *lot* of possible options to guess before you get a matching answer.
SHA is a Hashing function, SHA stands for Secure Hashing Algorithm.
Hashing functions are by definition a repeatable 1-way mathematical algorithm that creates an output of a set length.
The formulas are designed in such a way that you cannot reverse the process to run the output back into the input.
Meaning that a specific input into the function will always give the same answer (repeatable) and also for any given input a HASH function will always result in an output of the same number of characters or numbers in length.
This is important in cryptography because it allows you so store information like hashed passwords in a way that doesn’t allow the hacker to determine what the original password was. A database of hashed passwords will be a long list of seemingly random strings of digits and characters that are all the same length. So you can’t determine anything about the original password such as it’s length or what characters were in it.
BUT when you do a password lookup, you can take a password inputed, run it through the algorithm, and then compare the resulting hash to what’s stored in the database.
What this means is that to break a hash the only thing you can do is run different inputs into the hash and see what outputs they give until you find the correct answer. This is called Brute Forcing which is a long and convoluted process making it impractical.
This is also why hashing algorithms keep getting more complex. As computing power increases the ability for hackers to Brute Force passwords gets easier and easier, so by making the hashing algorithm take longer you are making it harder to Brute Force.
The actually maths behind a hashing algorithm are pretty complex and outside the scope of what I want to type. So if you want to learn more I suggest you watch numberfile:
>is it something to do with random numbers?
Not really. Hash algorithms have to give the same answer for a given set of data every time they run. If they used random numbers, that would not be possible. It has more to do with the XOR operation. Most hash algorithms work by XOR-ing the data with various strings of binary numbers.
The binary operation XOR takes in two digits (each either 0 or 1) and produces a 1 if exactly one of those digits is a 0 and the other is a 1. Its possible output look like this:
* 1 & 0 = 1
* 0 & 1 = 1
* 1 & 1 = 0
* 0 & 0 = 0
If you use XOR to combine a string of data with some other string of bits, you will get the same answer each time, because the operation is consistent. But it is not easy to reverse: if tell you the answer is 0, does that mean my input bits were both 0 or both 1? You have no way of knowing.
This is why hash algorithms are (relatively) easy to run, but very difficult to reverse.
It isn’t impossible from a mathematical standpoint. To “solve” the problem is a problem of factorization. The simplest explanation is that given a large number the problem to solve (ie to decode it without a key) is to find the correct factors. Although there are methods to reduce the problem size, the only way to figure this out is to repeatedly test different numbers.
A good encoding scheme makes it infeasible, not impossible to crack, because even using the fastest supercomputers today, it would take months to break a SINGLE message. A “normal” computer would be expected to take many years (centuries) to do this.
Therefore, in a practical sense, the code is considered unbreakable.
I want to try to add to the other answers, and hopefully give a bit clearer (if more handwave-y) explanation for your specific question.
So, you are correct that (at its core) you can boil down SHA256 to “just a math equation”. However, I want you to consider a (relatively) simple math equation: the roots of a quintic polynomial ax^(5) + bx^(4) +cx^(3) +dx^(2)+ex+f = 0. Assuming you are given a-f, you only have to find x: and yet, it turns out that there does not exist a general formula you can just plug a-f into and pop out x [(source)](http://mathworld.wolfram.com/QuinticEquation.html). To be completely honest, I do not know the proof of this, I just know that there is a proof nobody has found fault with as of yet (and given that this was known back in the 1800s, its a pretty safe bet that the proof is correct).
That being said, what does this have to do with SHA256? Well, if its impossible to come up with a generic equation to solve something with only 4 exponentiations, 5 multiplications, and 6 additions, imagine how unlikely it is that we have a solution to a mathematical formula so complex that it is written in pseudocode rather than as an equation.
Now, to be clear, this is more an analogy than anything mathematically rigorous. SHA256 doesn’t use exponentiation (in fact, it tends to use boolean operations like AND and bitshifting rather than numerical operations). Also, nobody has *proven* that a formula for reverse-engineering SHA256 doesn’t exist: mostly we are just relying on the fact that its complicated and nobody has (publicly) found a solution so far.
Additionally to all the other good answers, an important property of hashing functions is their impredicability.
If I know `hash(“hello”)` it doesn’t give me any information to what the result of `hash(“hellp”)` is going to be.
I could even have a list of inputs that maps onto the whole space of outputs, it is still not providing any information on what the output of `hash(“hellp”)` is going to be.
This is usefull protection since it means that the search for a valid input given a specific output is only possible through bruteforce.
Let’s take a little closer look at the kinds of math you want to reverse. 371 * 921 is pretty easy to compute, 341,691 / 921 is a little harder, even though it is the reverse operation. 4.247^(11) is also a straight forward calculation, but ^(11)√ 8,118,340.5071 is quite a bit harder. Reversible doesn’t mean reversible with the same amount of effort.
Secure hashes like SHA-256 rely on operations that deliberately make the effort going in one direction as disparate as possible from going in the opposite direction. If done well, reversing the hashing operation boils down to guessing numbers until you find a match.
There are two ways to design secure hash functions.
One of them is to pick a mathematical problem that is difficult, like factoring two integers. Then you design an operation where reversing the hash function is equivalent to reversing the mathematical operation.
This is almost never done, because the hash functions are incredibly slow.
Instead, what we have done is identify a bunch of properties of hash functions we think they should have. These have been based on a hundred years of attack on various forms of cryptography – we know that certain properties are resistant to entire swathes of attacks. We then design hash functions that have these properties.
This is how the whole SHA family was designed.
Latest Answers