阅读中文版本

Rainbow Tables and Lookup Attacks

Rainbow tables trade storage and computation to reverse unsalted hashes, which is why password storage needs a per-user random salt.

Definition

A rainbow table is a precomputed structure that maps hash values back to likely plaintexts, allowing an attacker with a stolen hash to recover short or common passwords quickly.

It is the reason unsalted, fast hashes are unfit for password storage and why a unique salt per user is mandatory. Compared to simpler alternatives, this concept fits best when the trade-off it represents is the one the system actually cares about.

When to use it

A common use case is applying it at the boundary where the cost of getting it wrong is highest, and the scenario usually involves a concrete guarantee the system must uphold. Unlike an ad hoc approach, it makes that guarantee explicit, reviewable, and testable.

How it works

The table encodes many candidate inputs and their hashes with a time-memory trade-off, so reversing a hash becomes a lookup rather than a brute-force search.

A unique random salt per password makes the same plaintext hash differently for every user, which invalidates any single precomputed table across the dataset.

Trade-offs and alternatives

Salt defeats precomputation but not guessing, so it is paired with a deliberately slow, memory-hard algorithm that raises the cost of each attempt. The main drawback is the extra complexity it introduces, so the benefit should clearly outweigh that cost before a team adopts it.

Common misconceptions

A persistent misconception is that rainbow tables work against any hash regardless of salt. Another is that a longer password always defeats a rainbow table attack. For example, an engineer who assumes otherwise may design around a guarantee that does not actually exist, which only becomes obvious under load or failure.

Anti-patterns to avoid

Two recurring anti-patterns are to storing plain hashes of passwords in a single shared column and to assuming a fast general-purpose hash is adequate for credentials. Both tend to surface as hard-to-debug production issues rather than obvious test failures. Related concepts include Password Salting, Authenticated Encryption (AEAD), Forward Secrecy.