Basis Lab

Answers · Keeping it safe

Why does storing a random salt with each hash stop rainbow tables?

In shortBecause the salt is different for every account, a table built once from common passwords matches at most one row, so the work has to be redone account by account.

The salt makes each stored value depend on two things rather than one, the password and a random value unique to that account, so a table computed from passwords alone no longer answers the question your rows pose. Rainbow tables work by amortising: one expensive build serves every breach forever. A per-account input destroys the amortisation while leaving the computation itself untouched.

vi=H(si ∥ pi)v_i = H(s_i \,\|\, p_i)

Put numbers on the amortisation first. A published table covering a billion candidate passwords holds 10910^9 entries. At roughly 32 bytes each, password plus its stored value, that is 109×32=3.2×101010^9 \times 32 = 3.2 \times 10^{10} bytes, or about 32 GB, and it cost a billion hash computations to build once. After that it is a lookup service: hand it any row produced by that hash from an unsalted scheme and it returns a password in milliseconds. The billion computations never appear again, no matter how many databases are stolen.

109×32 bytes=3.2×1010 bytes≈32 GB10^9 \times 32\ \text{bytes} = 3.2 \times 10^{10}\ \text{bytes} \approx 32\ \text{GB}

Now salt it. With bb bytes of salt there are 28b2^{8b} possible values, and a table that covers the same billion passwords for every one of them needs 109×28b10^9 \times 2^{8b} entries. The growth is brutal because both factors multiply, and 32 bytes per entry multiplies again.

FIG 1
salt lengthdistinct saltsentries neededstorage at 32 bytes
0 bytes110^932 GB
1 byte2562.56 x 10^118.2 TB
2 bytes65,5366.6 x 10^132.1 PB
4 bytes4,294,967,2964.3 x 10^18137 EB
16 bytes3.4 x 10^383.4 x 10^471.1 x 10^49 bytes

Two bytes already costs 2.1 petabytes, four bytes costs 137 exabytes, and sixteen bytes leaves a number of bytes with forty-nine digits in it. Nothing in that column is buildable, so the table is not built. The attacker is pushed back to computing candidates for a specific account instead of looking them up, and that is the whole effect: work that was shareable has become work that is not.

Why the salt is printed in the row

The natural guess is that the salt must be kept secret, because otherwise the attacker can simply mix it in themselves and the protection evaporates. It does not, and the salt is stored in plain text in the same row for a reason that has nothing to do with secrecy: at login you are given a typed password and must recompute the stored value to compare, which means you must read back the exact salt that went in. A salt you cannot read is a salt that makes the row unverifiable and the account unloggable.

Publishing it costs nothing because secrecy was never the mechanism. Suppose the attacker holds every salt in your table and knows them all. To use the 32 GB table above they would still have to pair each of the billion passwords with each account's salt, and that is a billion fresh computations per account, not a lookup. For forty thousand accounts that is 109×40,000=4×101310^9 \times 40{,}000 = 4 \times 10^{13} hash computations.

c=u⋅g=40,000×109=4×1013 computationsc = u \cdot g = 40{,}000 \times 10^9 = 4 \times 10^{13}\ \text{computations}

Where the salt runs out

That 4×10134 \times 10^{13} is the limit of what a salt can do, and it is worth seeing how small it can be. On hardware doing 10910^9 hashes per second, which is ordinary for a fast hash on one graphics card, the sum takes 4×1013/109=40,0004 \times 10^{13} / 10^9 = 40{,}000 seconds, about eleven hours for a whole forty-thousand-row table. The salt bought a factor of forty thousand; it bought no slowness at all, and eleven hours is not a defence. Making each of those computations expensive is a separate mechanism, and it only starts to matter once the sharing is gone, because multiplying the cost per guess by a large factor is pointless if one guess still opens six hundred accounts.

Three ways to lose the benefit: reusing one salt across accounts, which restores exactly the shared work the salt was meant to remove; deriving the salt from the account name or an email address, which is not random and can be precomputed for a named target; and making it too short, so that a determined builder covers the whole salt space anyway. Sixteen random bytes generated afresh at each password change avoids all three. A salt also does nothing against a duplicate group inside your own table if it is reused, and it does not hide how many accounts exist, only which of them share a password.

Worth keeping

  • A salt does not need to be secret: an attacker who knows every salt still has to redo the work for every account, which is precisely the cost the salt imposes.
  • A rainbow table is a one-off cost amortised over every future breach, so any per-account input that forces one table per account makes the build uneconomic.
  • The salt makes the attacker's work unshareable but not slow; the cost parameter of the hash is what makes each share expensive.

Where this goes next

This question is one step of How a Password Is Stored, a course that works through its subject from the beginning. The page that teaches this part of it is Two People, One Hash, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. Why isn't encrypting the password enough to keep it safe if the database leaks?Because encryption can be undone by your own login code, so the key that lets you check a password usually sits near the database, and anyone who copies both can read every password.
  2. How do I pick the iteration count or cost factor for password hashing?Pick a time budget for one login, measure what setting meets it on your own hardware under load, and store that setting in each stored record.
  3. How fast can an attacker guess passwords after stealing a hash database?About ten thousand million guesses a second on one rented graphics card against a fast hash, so most of a stolen table falls in under a second.
  4. How does text I saved in a comment end up running as JavaScript in someone else's browser?The comment stayed text in storage; a page that later pasted it into its own markup made the browser read it as code.
  5. Why does escaping the quotes in user input not stop SQL injection?Escaping quotes only cleans one context; SQL injection stops only when query text and values travel separately, so the value is never parsed as code.
  6. How do I stop one service from reading another service's password?Give every service its own identity, grant only the credentials it uses, and test that it cannot read another service's password.

Read alongside