I have read that SHA-2 is currently unbroken due to the amount of resources and time it would take to crack the hashing, but if we have the step by step algorithm, why can we not just do the steps backwards?
In: Technology
Hash functions are designed to be hard to invert. If you try to invert without knowledge of the password, there are many many unknown variables and relations that need to be solved for.
These simplified responses are nice, in that they show why a hash can’t go backwards.
But when you put a password into the website, they compare the hash of your password, to the hash of what you typed. They don’t even need to keep your password saved, they could just keep your hash.
So, the result of the hash isn’t going to be something simple like 42, or something like that, like the one guy explained. If that were true, lots of passwords, would have that same hash. A hash usually results in some crazy 32 or more character random string of letters and numbers which is even more unique than the password you actually entered.
>if we have the step by step algorithm, why can we not just do the steps backwards?
Let me give you an over-simplified example. Here’s my hashing algorithm:
1. Take the password, and replace each letter with a number representing its place in the alphabet. So A=1, B=2, C=3, . . . Z=26.
2. Jam all the numbers together into one long number.
3. If there are not an even number of digits, prepend a zero to the beginning. So 126 would become 0126
4. Group the list into a series of two-digit numbers.
5. Add all the two-digit numbers together.
6. If the resulting number is more than two digits long, go back to step 3. Otherwise, continue.
7. The result is your hash
So if your password is “password”:
1. P=16, A=1, S=19, S=19, W=23, O=15, R=18, D=4
2. 16119192315184
3. *already an even number of digits*
4. 16 + 11 + 91 + 92 + 31 + 51 + 84
5. 376
6. *number is too long, go back to step 3*
3. 0376
4. 03 + 76
5. 79
6. *number is short enough, go to step 7*
7. Your hash is `79`
Now that you’ve seen how this works, your assignment is to take `42` as a hash and reverse the above steps to find out what the original password was. I’ll wait.
.
.
.
Can’t do it, can you? That’s because the above algorithm is a one-way function. It cannot be performed in reverse, because it throws away information. The only way to find out what password results in a hash of `42` is to *try to hash every single possible password* until you find one that gets the results you want.
Because in a hash function, information is lost when you run it. That’s why it is called a hash…it’s like running meat through a grinder. You can’t put it back together again. Except a cryptographic hash is semi-unique.
Keep in mind that you can run a 2000 page document through a hash and get a result that’s 16 bits long.
“*Once bread becomes toast, it can’t go back.*” – Ajax
Because it is a one way function. This means that it is – at least – practically infeasible to invert it. Optimally it would be a function that doesn’t even have an inverse.
There is one operation called “modulo” where one basically divides a number x by y and receives the remainder.
So for example 7 mod 2 would be 1 because it is 3 with remainder 1.
This means I can have an infinite amount of numbers mapping to the same output, but you can’t reverse it.
If I give you 7 mod 2 you can easily see it’s 1.
But if I said “I received 1 when doing modulo 2” you can’t know it’s 7, it could as well be 9, 11 or literally any odd number there is.
So even though you know the “algorithm” to get from 7 to 1 by using modulo 2, you simply can’t reverse the process.
This is the main principle hashing functions use, thus you can’t just invert them.
Think of sudoku. What is easier? To solve a puzzle, or to check if a solution is correct?
Sudoku and this hashing alghorithm have something in common: They are NP problems.
What are NP problems? In computation we have sort problems by how complex they are to solve. For example: Ordering a list of names is less complex than evaluating the best move in a game of chess. There’s a set of problems that can “easily” be verified, but we have no idea if there’s a solution that isn’t “more complex” than checking if a solution is true, those are the NP problems (also one of the biggest questions of math. It is known as “NP = P?”)
>why can we not just do the steps backwards?
We don’t know if we can’t. But in the case we can, we don’t know how to do it.
Latest Answers