Answer posted to: https://security.stackexchange.com/questions/60691/length-of-passwords-that-are-rainbow-table-safe
Moderator deleted it on the basis that my answer focused too much as a response to another, and didn't address the actual question (which it did).
I have since heard back that if I modify the answer to more directly address the question, it'd be considered for undeletion. No time for that at present, sharing this in case it benefits anyone else.
As I lack the reputation to post a comment to Mac's answer; I just wanted to point out that the emphasis on length only applies if a brute force attack was carried out to exhaust the Key Space character by character.
Such an attack at that length was already raised as not feasible by Mac. That does not mean the attacker wouldn't try easier attacks based on heuristics. It's 4 words, all lowercase, uses 3 very common words and in a natural sequence. Uniform randomness wasn't used, and while it cannot be assumed to the attacker, it is low effort/cost to try in this scenario (much lower entropy pattern to attack).
Instead of using single characters as an alphabet, you can use words. There's a variety of lists composed based on statistics like frequency. Here is one with 2,000 words sampled from ~9.4 million words of contemporary fiction. You could additionally iterate through permutations based on the likeliness of a word to follow the previous one, which for passwords lacking randomness would further improve the attack against the lower entropy.
log2(6.3 * 10^24) = ~82.4 vs log2(2000^4) = ~43.86, almost half the bits (2^38.54 delta, about 400 billion times weaker) and lower than the Fail!007 example (log2(6.7*10^15) = ~52.6. In comparison to the <6 hours to exhaust the 252.6 Key Space, at the 350 billion / sec hash rate you would get through 243.86 in less than 46 seconds: 2^43.86 / 350000000000 = ~45.6. Why waste centuries when you have far better alternative attacks to try first for lower hanging fruit?
Your assumed security is far lower than the math trying to justify length over entropy. I felt that was worth bringing up to anyone who might have read the claim and not truly understood why it was misleading. Rather than length, it's the total permutations or Key Space being attacked. As demonstrated, that changes drastically based on assumptions from the attacker, they have a variety of ways to approach an attack and the more they know about what they're attacking the more optimized it can be.
In the given situation, the alternative attack against a wordlist isn't costly to run among many others. What is missed here, is that the linked article about the 6 hour attack at 350 billion hashes per second was against one of the most easiest hash types to compute. You'll note further down the article they change from NTLM hashes to SHA-1 which is much slower, then mention BCrypt as significantly slower still (although they don't mention the work factor, which by default in hashcat benchmarks is 5, thus you should divide the rate by 25 as bcrypt work factor is logarithmic that'll get you the slower speed of work factor 10). Thus you're actually looking at 71000 / 2^5 = ~2220, 350000000000 / 2220 = ~158M (much more difficult!), (45.6 * 158000000) / (60*60*24*365) = ~228 (or (2^43.86 / 2220) / (60*60*24*365) = 228... roughly 228 years, far less practical now.
You could add 1-bit more for a set of passphrases with space and without space, that'd double the amount of hashes to compute. If brute forcing instead of generating a table, you'd have a match on average in half of the Key Space, so that'd also drop 1-bit, that ~244 of permutations could have a match in 243 instead, or if unlucky and you get the delimiter between words wrong (if there is one), it could be 245 or more (perhaps the words are uppercase instead, or use PascalCase).
Meanwhile Fail!007 would go from the 6 hour mark to ~95k years at that adjusted hashing rate. That was back in 2012 with 25 GPUs, meanwhile a company that bought 72 FPGAs in 2019 (over 18 boards, 4 FPGA each) that were products available to purchase in 2011. This FPGA cluster is capable of about 60k bcrypt hash rate at a work factor of 10. A single one of those FPGA chips was 4x as more capable than a modern RTX 2080Ti from NVIDIA (Only 2x since Hashcat v6 CUDA improvement), but costs much less and far less power.
With salts, it'd depend on how they're used and how much more difficulty they add. If we aren't using a slow hash and just append the salt to the password we're going to hash, you might use a randomly generated hexadecimal string of 16 characters (0-9, a-f, 16 values aka 4-bits per character) for a total of 32-bits, 232 (~4 billion) permutations of all the hashes you'd compute without the salt. That ~45 second exhaustive brute-force of this is a fail is now going to take over 6k years (<3k years if you're lucky!).
The salt of 32-bits was added onto our best case of ~244 entropy bits (less in reality due to the natural language sequence adding bias), giving us 276 permutations to calculate (log2(2^44 * 2^32) = 76). Pair that with the slow hash like bcrypt which uses a 128-bit salt, a much much bigger number and rainbow tables aren't going to be a problem.... assuming they're random.
Sometimes, you may see advice of using data related to a user such as the username as the salt. That's not going to be a big random value, making it less intensive to compute. It might even be that a rainbow table of sufficient length includes a salt used without trying, such as passwordjohn. That would also have value against any service where a user "john" has the same password and the service hashes the password with salt in the same way. So a domain name of the service gets added into the salt.
The attacker isn't likely to have a rainbow table already computed in advance for this, it'd be tailored to the service. As stated in Tom's answer, the brute force will be much easier/faster route instead. The salt uniqueness reduces the scope of the hash cracking to each user, so now the attacker must target a specific user or see how lucky they can get trying attacks that aren't too time consuming against the slow hash over each user (eg top 100k or million passwords).
With the rainbow table not being relevant anymore. The 32-bit salt would not make the attack 4 billion times more difficult against single users. The salts are known at this point and if you only have 64 users of interest, that 32-bit salt is equivalent to 6-bits more of work, similar to an extra alphanumeric character in the password for example.
this is a fail is definitely weaker than Fail!007.
- Length alone does not matter much if the entropy is low.
- There's more than one way to attack a hash.
- Slow hashes make the time to compute an exhaustive search very expensive (difficulty increases with more permutations, not necessarily length)
- Password randomness (of the "alphabet", that can include words, not just single characters) maintains higher entropy as opposed to biases which reduces the effectiveness of total permutations.
With a decently large and unique enough salt, the passwords will not be feasible to compute in advance (due to increase in permutations). The salts will be available to the attacker who has the hashed passwords at this point, thus the salts provide little protection against attacking a specific password hash (they're still useful at preventing the same passwords from having the same hashes).