Fortunately, there's a very simple mechanism we can employ to mitigate lookup table/rainbow table attacks, by making the password very long.

The number of possible hashes scales exponentially with the following:

1. The length of the password
2. The range of possible characters for each character in the password

Let's suppose our passwords can contain lowercase letters, uppercase letters, and numbers; this gives us 62 unique possibilities for each character. If we have a one-character password, that means we only have to generate a rainbow table with 62 (62¹) entries to be guaranteed a match. If we have a password that has a maximum of two characters, there are now 3,906 (62¹ + 62²) possible combinations. If we allow passwords up to 10 characters, that's 853,058,371,866,181,866, or 853 quadrillion combinations (62¹ + 62² + 62³ + 62⁴ + 62⁵ + 62⁶ + 62⁷ + 62⁸ + 62⁹ + 62¹⁰). Although that sounds like an unimaginably large number, there are machines that can calculate hundreds of billions of hashes per second. Therefore, it'll take about a month to go through all those combinations—still not very secure.

However, if the maximum length of the password becomes 20 characters, then it'll take 715, 971, 350, 555, 965, 203, 672, 729, 121, 413, 359, 850, or 715 decillion, iterations to generate all passwords of 20 characters. Those extra 10 characters mean it's now 839 quadrillion times harder to generate all password combinations.

Therefore, by implementing a reasonable password policy, it will deter hackers from even attempting to brute-force attack you. A reasonable policy may read as follows:

• Password must be at least 12 characters long
• Password must include at least one special character (!£$^&()+-=[]}{:@;<>.,)

With our list of 21 special characters, our character range is now increased to 83. Therefore, a hacker would have to calculate 108193544418400894220040, or 108 sextillion, hashes in order to guarantee a match on the password.

Alternatively, you may encourage the user to use a passphrase, which is a few unrelated words chained together; for example, correct horse battery staple (a reference to this XKCD comic: xkcd.com/936). This ensures that the password is long enough that the lack of character range doesn't matter. The attacker would have to try a huge number of combinations before it arrives at your passphrase.