Rainbow tables

In short: Rainbow tables are precomputed lookup tables used to quickly recover a password from its hash. Salt makes them useless.

In more detail: Instead of trying all passwords every time, they trade memory for compute time: chains of hash and reduction steps are computed in advance and only the start and end are stored.

In Depth

• Idea: A chain password → hash → password' → hash → … is stored as (start, end). When cracking, the chain is rebuilt from the target hash until an endpoint matches, then reconstructed from the start.
• Counter-measure salt: A random extra value per user turns equal passwords into different hashes. Tables would have to be recomputed for every salt. See storing passwords securely.
• Slow methods: Argon2, bcrypt and scrypt make every guess expensive.
• Today: They still work against unsalted legacy hashes (MD5, SHA-1, see MD5 and SHA-1). For strong passwords, GPU dictionary attacks are more practical.
• Lesson: Never store passwords with a fast, unsalted hash.

See also: Hashing