Why is SHA256/SHA512 not broken for shortish passwords

Question

I don't get why SHA-256/SHA-512 hasn't been broken, at least for shortish (10-12 character) passwords

It is perfectly plausible to pre-compute a password/hash-pair table using numerous very fast computers (thereby significantly increasing the speed at which this is done).

Clearly I am misunderstanding, so I would appreciate some input as to why this would not be considered breaking SHA256/SHA512 especially as most people use passwords shorter than 10-12 characters

Answer 1

SHA-256 and SHA-512 were designed to be very fast. Their primary goal ist to verify the integrity of long messages or files. Long means not 10-12 bytes but some megabytes and greater. It is not a good idea, to use hash function that is fast by design for password hashing. Instead, for password hashing should be used functions that need essentially more resources for brute-forcing, e.g. that require relatively much RAM, prevent or limit essentially parallelization and thus limit optimization of brute-forcing. For instance, Argon2, Lyra2, scrypt.

Compare it to cars. Ferrari is good for the cases when the speed is important. It is not correct to say that Ferrari is weak because it cannot carry big load. If you need to move a big load, you better use huge trucks. It is just a matter of choosing a proper tool for the task.

Answer 2

When we state that "SHA-256/SHA-512" hasn't been broken, what we mean is that the three security properties of hash functions haven't been violated. Those properties are:

• Preimage resistance; given a hash, value, it is hard to find a string that hashes to that value.

• Second preimage resistance; given a message, it is hard to find a second message that hashes to the same value that the first message hashes to

• Collision resistance; it is hard to find two different messages that hash to the same value.

Where "hard" means both "the best known attack are the known generic attack" and "infeasible with the computing resources currently available".

Now, you might say "I can precompute a 10 character password hash; if I see that value in the password file, haven't I violated preimage resistance?" Actually not; that is a generic attack, and would be applicable to any hash function.

What this observation would imply is that unsalted SHA-256 or SHA-512 probably isn't the best choice to storing passwords - as you said, you can precompute things (or even better for the attacker, generate a rainbow table). What you should do is a) add salt (so precomputation attacks and multitarget attacks are not applicable), and b) use a hash function that can't be computed as quickly by the adversary (such as Argon2)

Answer 3

Using SHA-256 or SHA-512 as a substitute for a proper purposefully-slow password-hash is broken for shortish (10-12 character) passwords. Try it with the SHA-256 of test123456 encoded per UTF-8. Even Google finds it! Rainbow tables allow a relatively compact yet efficiently searchable storage of the precomputations.

That way of using a hash is just a bad use of a good tool. That it fails does not match any of the definition of breaking a hash, including these common ones:

1. Breaking collision-resistance: find two distinct inputs that hash to the same value.
2. Breaking second preimage resistance: given an input, find another input that hashes to the same value. Usually, how the input is chosen is unspecified, for that rarely matters; that could be a typical password.
3. Breaking first preimage resistance: given a hash of some unknown input, find that input with much less work (or/and better probability) than brute force (that is hashing the possible inputs from most to least likely and comparing, until the available resources are exhausted). How the input is chosen matters: for a rigorous definition, we could add that it is chosen with known probability in some specified set (perhaps restricted to be much smaller than the set of possible hashes, so that the original input can be found with good probability), with that set chosen randomly, or at least independently of the hash. That set can be the set common passwords.
4. Breaking indistinguishability from a random oracle: exhibit a (probabilistic polynomial-time) algorithm able to distinguish with sizable advantage an oracle implementing a random function, from one implementing a random instance of the family the hash belongs to. In practice: an algorithm which does not use one of the arbitrary constants in the hash (like the fixed input to the first iteration of the round function in a Merkle-Damgård hash as SHA-256 or SHA-512), and is able to distinguish the output of a perfect random number generator from the output of the hash under test, when the input of the later is decided by the algorithm and constrained not to repeat an earlier input. By the way, SHA-256 and SHA-512 fail under that test, due to the length-extension property; SHA256d and SHA-3 are designed to fix that.

Test 3 is the closest to what the question considers, but it includes with less total work than brute force, which is the answer.