cryptography - How long to brute force a salted SHA-512 hash? (salt provided) -

here algorithm in java:

public string gethash(string password, string salt) throws exception {     string input = password + salt;     messagedigest md = messagedigest.getinstance(sha-512);     byte[] out = md.digest(input.getbytes());     return hexencoder.tohex(out); } 

assume salt known. want know time brute force when password dictionary word , when not dictionary word.

in case, breaking hash algorithm equivalent finding collision in hash algorithm. means don't need find password (which preimage attack), need find output of hash function equal hash of valid password (thus "collision"). finding collision using birthday attack takes o(2^n/2) time, n output length of hash function in bits.

sha-2 has output size of 512 bits, finding collision take o(2^256) time. given there no clever attacks on algorithm (currently none known sha-2 hash family) takes break algorithm.

to feeling 2^256 means: believed number of atoms in (entire!!!) universe 10^80 2^266. assuming 32 byte input (which reasonable case - 20 bytes salt + 12 bytes password) machine takes ~0,22s (~2^-2s) 65536 (=2^16) computations. 2^256 computations done in 2^240 * 2^16 computations take

2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years 

even calling millions of years ridiculous. , doesn't better fastest hardware on planet computing thousands of hashes in parallel. no human technology able crunch number acceptable.

so forget brute-forcing sha-256 here. next question dictionary words. retrieve such weak passwords rainbow tables used traditionally. rainbow table table of precomputed hash values, idea if able precompute , store every possible hash along input, take o(1) given hash , retrieve valid preimage it. of course not possible in practice since there's no storage device store such enormous amounts of data. dilemma known memory-time tradeoff. able store many values typical rainbow tables include form of hash chaining intermediary reduction functions (this explained in detail in wikipedia article) save on space giving bit of savings in time.

salts countermeasure make such rainbow tables infeasible. discourage attackers precomputing table specific salt recommended apply per-user salt values. however, since users not use secure, random passwords, still surprising how successful can if salt known , iterate on large dictionary of common passwords in simple trial , error scheme. relationship between natural language , randomness expressed entropy. typical password choices of low entropy, whereas random values contain maximum of entropy.

the low entropy of typical passwords makes possible there relatively high chance of 1 of users using password relatively small database of common passwords. if google them, end finding torrent links such password databases, in gigabyte size category. being successful such tool in range of minutes days if attacker not restricted in way.

that's why hashing , salting alone not enough, need install other safety mechanisms well. should use artificially slowed down entropy-enducing method such pbkdf2 described in pkcs#5 , should enforce waiting period given user before may retry entering password. scheme start 0.5s , doubling time each failed attempt. in cases users don't notice , don't fail more 3 times on average. slow down malicious outsider trying attack application.