Q56 — Why is storing passwords as hashes not enough — what is a rainbow table attack?

Why you can't store passwords in plaintext

The first instinct when storing passwords: save what the user typed. You need to verify it later — compare what they type at login against what's stored. Simple.

The reason this is catastrophically wrong: databases get breached. It happens to large companies, small companies, and everything in between. A breach of a database that stores plaintext passwords means every user's password is immediately exposed — and because most people reuse passwords across multiple sites, the attacker now has credentials they can try on Gmail, bank accounts, and anything else the user might have.

So you hash passwords before storing them.

What does hashing give you?

A cryptographic hash function takes an input (the password) and produces a fixed-length output (the hash) with three properties:

Deterministic: the same input always produces the same output. "hunter2" always hashes to the same digest, so you can verify a login attempt by hashing the input and comparing to the stored hash.

One-way: given the hash, you cannot derive the original input. There is no "reverse" operation. An attacker with the hash cannot simply compute the password.

Avalanche effect: a tiny change in input produces a completely different output. "hunter2" and "hunter3" hash to completely different digests, so you can't find similar passwords by looking for similar hashes.

If you hash passwords with a function like SHA-256 and store the hashes, an attacker who breaches your database gets a list of hashes but (supposedly) cannot recover the original passwords. Verification still works: take the login attempt, hash it, compare to the stored hash.

Why plain hashing is not enough — the offline attack

Here's the attack model the database breach opens up: an attacker now has a list of (username, hash) pairs. They can attack these offline — without ever touching your server, without triggering any rate limits or lockout policies, at whatever speed their hardware allows.

Modern GPUs can compute billions of SHA-256 hashes per second. An attacker with a $300 GPU can try every word in a dictionary, every common password, every password with common substitutions (a→@, e→3, s→$) at billions of attempts per second — completely offline. This is a brute-force attack against the hash list.

For short, common passwords, this takes seconds. "password1" hashed with SHA-256 will be found in under a second on any modern GPU.

What is a rainbow table attack?

Brute-force is expensive per hash — you have to hash each guess for each target hash. What if you precomputed the hashes for millions of common passwords and stored them in a lookup table? Then, instead of computing, you just look up the hash in the table and read off the password.

A rainbow table is a time-space trade-off that takes this further: it precomputes chains of hash-reduction operations to encode an enormous search space in a relatively compact table. The details of the chain structure are clever, but the key point is: given enough precomputed storage, an attacker can look up common passwords by their hash in near-constant time.

An attacker with a rainbow table for SHA-256 can, for any common or short password, find it in milliseconds — no computation needed at attack time. The work was done once (building the table) and can be applied to any number of breached databases.

This attack works because without any per-user randomization, two users with the same password have the same hash. Once you've found one hash, you've found all users with that password simultaneously.

What is a salt and why does it defeat rainbow tables?

A salt is a random, unique value generated per user and stored alongside the hash. When hashing a password, you don't hash the password alone — you hash the concatenation of the salt and the password:

stored_hash = hash(salt + password)

At login:

input_hash = hash(stored_salt + login_attempt)
verify: input_hash == stored_hash

The salt doesn't need to be secret — it's stored in plaintext in the database alongside the hash. Its purpose is not secrecy but uniqueness.

Why does this defeat rainbow tables? A rainbow table is precomputed for a specific input space. If your salt is a random 16-byte value, the effective input to the hash function is <16 random bytes> + <password>. The attacker would need a separate rainbow table for every possible salt value — 2^128 different tables. This is computationally and storage-wise impossible to precompute.

Why does salt defeat hash list attacks across users? Two users with the same password "hunter2" now have different salts: user A has hash(abc123 + hunter2), user B has hash(xyz789 + hunter2). The hashes are different. Cracking user A's hash tells you nothing about user B's. The attacker must brute-force each hash independently.

Why fast hash functions are still the wrong choice even with salting

SHA-256 was designed for speed — used in TLS, checksums, digital signatures, where you need to hash gigabytes of data quickly. At 1 billion hashes per second per GPU, even with salting, an attacker with a list of hashes can brute-force most 8-character passwords in minutes.

The right answer for password hashing is a deliberately slow hash function — one designed so that computing a single hash takes a meaningful amount of time (e.g., 100ms on the server), making brute-force attacks computationally prohibitive at scale.

bcrypt: designed in 1999 specifically for password hashing. Takes a "cost factor" parameter that controls how many rounds of computation are performed. At cost=12, one hash takes ~250ms on a modern CPU core. Each +1 to the cost doubles the work, so you raise it as hardware gets faster. bcrypt keeps a small (~4 KB) internal table that it reads and rewrites constantly, which GPUs handle poorly: a high-end GPU manages on the order of a thousand or two cost-12 guesses per second, versus billions of SHA-256 guesses. 1 billion guesses against one bcrypt hash therefore takes a GPU about a week or two instead of one second — and because every user has a different salt, the attacker pays that again for every account. bcrypt is slow, but not memory-hard: 4 KB is tiny, so specialised hardware (FPGAs/ASICs) can still pack many bcrypt cores. Two practical gotchas: bcrypt only uses the first 72 bytes of the password, and you should use the library's verify function (constant-time comparison) rather than comparing hash strings yourself.

Argon2: the winner of the Password Hashing Competition (2015), now the recommended standard. Configurable in three dimensions: time cost (CPU rounds), memory cost (RAM required per hash), and parallelism. The memory cost is the key advantage: an attacker wanting to run many parallel hash computations needs proportionally more RAM. A high memory cost (e.g., 64MB per hash) makes GPU attacks expensive — GPUs have fast compute but limited per-thread memory.

scrypt: similar to Argon2, also memory-hard. Still widely used.

The principle: password hashing must be expensive enough to be acceptable on the server (one hash per login, 100–300ms is fine) but prohibitive for an attacker trying billions of passwords offline. Fast hash functions like SHA-256 or MD5 are completely inappropriate for passwords regardless of salting.

The complete picture

Layer 1 — Store a hash (not plaintext):
  One-way function → attacker with hash cannot reverse to password
  Breaks: offline brute force on fast hashes (GPUs: 1B SHA-256/sec)

Layer 2 — Add a unique random salt per user:
  hash = hash(salt + password); store (salt, hash)
  Breaks: rainbow tables (need unique table per salt — impossible)
           cross-user attacks (same password → different hashes per user)
  Doesn't fix: brute force if hash function is fast

Layer 3 — Use a deliberately slow hash function (bcrypt; better: memory-hard Argon2id):
  bcrypt cost=12: ~250ms per hash on a CPU; ~1–2k guesses/s on a high-end GPU
    → 1B guesses ≈ 1–2 weeks per GPU, per user (vs ~1 second for SHA-256)
  Argon2id memory-hard: each guess needs MBs of RAM → GPU/ASIC parallelism limited
  Makes offline brute force computationally prohibitive

Together:
  Store: (username, salt, slow_hash(salt + password))
  Login: library verify(input, stored_hash) — constant-time compare, never a plain string ==
  Breach: attacker gets (salt, hash) pairs
          Cannot reverse (one-way)
          Cannot precompute (salt makes rainbow tables impossible)
          Cannot brute-force quickly (bcrypt/Argon2 too slow per attempt)

Additional layers (defense in depth):
  Pepper: a secret value stored outside the DB (in app config), added to hash
    hash(pepper + salt + password)
    Even with DB breach, attacker needs pepper to crack hashes
  Breach detection: alert when bulk login failures spike
  Credential stuffing protection: rate limit + 2FA

Password storage is not a single decision — it's a sequence of defenses that make each successive attack prohibitively expensive. Every layer addresses a specific attack vector. Omitting any one layer — storing plaintext, no salt, fast hash function — degrades the entire stack to that layer's weakness.