Is it possible to break SHA-256 with hash tables?

Question

If x is the value you're hashing, $t(x)$ is the hash of that value, and $t(x+s)$ is that value with salt, then hashed. You could create a hash table where the key is $t(x+s)$, the value is $x+s$, and compute then store all of the possible strings with a length less than $n$ characters.

If you cracked 2 hashes by guessing then the salt would be a suffix of the shared suffix between the $x+s$ of the 2 cracked hash values. You could then search your table for all values that have that salt suffix and recognize that any hash that matched that suffix is a possible solution for that table.

Answer 1

TLDR: no, it's not possible to break SHA-256 with hash tables.

First, the amount of memory necessary in the "create a hash table" step makes the method impracticable for large n. E.g. if $n=8$ (for length of $x\mathbin\|s$) and there are $64$ possible "character" values, we need $256\times64^8$ bits that is $8192\,$TByte of memory, more storage than RAM in most supercomputers.

The attack seem to try to find $x$ given the SHA-256 hash of $x\mathbin\|s$ (and perhaps $s$). If there is a single instance of this problem, or multiple instances all given at once, then the table brings only one thing compared to brute force hashing all possible values and comparing to the hash(s): it's possible to start the attack before being handed the problem(s).

On the other hand, if $x\mathbin\|s$ is short enough that the table can be stored, and there are several problems to solve iteratively (next problem is given only after the previous one is solved), then the table-based approach can reduce the attack computational effort.

None of this is a "break of SHA-256" in a standard sense, like finding collision or preimage with effort better than brute force.

Answer 2

If you're talking about cracking salted passwords with this table (known as a rainbow table), usually you would have access to the salts along with the hashed passwords as they are usually stored in the same database table that would have been compromised. Salts should be unique for each user to mitigate a rainbow table attack.

I think what you are considering is a common salt amongst all users. This is sometimes known as a pepper. It can be stored outside of the database to avoid being discovered if the database is compromised. Even then you could brute force it, as you suggested, if it was short enough but using 128 bits for the pepper would mitigate this risk.

For even stronger security you can use unique salts per user plus a pepper.

Note: what can be cracked are weak passwords by using a dictionary of common or short passwords. Long random passwords will not be able to be cracked.