Salt and Password Storage

All the measurements in the previous lesson rested on a single assumption: inputs were generated by a counter, and every attempt was equally likely. When it comes to passwords, this assumption falls apart. Strings that people choose are not evenly distributed across the possible input space; a candidate list of a few hundred million covers a computable portion of the space. In that case, the 2^256 preimage bound carries no weight at all, because the search is not done over the whole space but inside the list.

What this lesson measures is how that list gets made expensive. There are two separate factors, and the two multiply different things. All the calculations below are on our own model; running trials against a real password set, without written authorization and a defined scope, is both illegal and unprofessional.

What Multiplies What

CF8: the key derivation function’s work factor grows a single attempt’s unit cost linearly. The defender pays this cost once per login; the attacker pays it once per candidate. The asymmetry is right there.

CF9: a rainbow table fits all records at once that share the same salt. If the salt is generated separately per record, the same table fits only one record.

The two sit at different points of the factor. The work factor grows the cost per attempt, salt grows the number of attempt sets that have to be repeated. Neither substitutes for the other; when used together, the total work is their product. This distinction requires the two defenses to be measured separately: if the work factor is raised and salt is skipped, the total work gets divided by the record count; if salt is added but the factor is left low, the unit cost stays too small to matter.

The Trial Cost Curve

The unit below measures the work factor’s effect on cost. The measurement pattern is special: raw duration is never printed anywhere. The expected multiplier is derived from the input — that is, from the ratio of the chosen N values; the measured value is only run through a band check, and the result is printed as yes or no. The reason is that absolute duration depends on the machine and the runtime; what is meant to be measured is the ratio, which is independent of the machine.

// password/factor.mjs — the work factor's cost curve on trial cost. Duration is not printed raw: the
// expected multiplier is derived from the input (the ratio of N values); the measured value is only
// run through a band check and printed as yes/no. A fictional field crew password is used.
import { scryptSync } from "node:crypto";

// CF8: the key derivation function's work factor grows a single attempt's unit cost
//      linearly; the defender pays this cost once, the attacker pays it once per
//      candidate.

const PASSWORD = "fictional-field-crew-login";
const SALT = Buffer.alloc(16, 3);                // fictional, fixed
const BASE_EXP = 12;
const config = (exp) => ({ N: 2 ** exp, r: 8, p: 1, maxmem: 512 * 1024 * 1024 });
const measure = (exp, times) => {
  scryptSync(PASSWORD, SALT, 32, config(exp));                 // warm-up
  const t0 = process.hrtime.bigint();
  for (let i = 0; i < times; i++) scryptSync(PASSWORD, SALT, 32, config(exp));
  return Number(process.hrtime.bigint() - t0) / times;
};
const baseline = measure(BASE_EXP, 8);
const CANDIDATES = 1_000_000;                    // fictional candidate list size
const printRow = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));
const G = [8, 9, 11, 13, 24];
console.log(`baseline work factor N=2^${BASE_EXP}; unit = one trial at the baseline factor`);
printRow(G, "N", "memory", "expected", "in band", "candidate list (units)");
for (const exp of [12, 13, 14, 15, 16]) {
  const expected = 2 ** (exp - BASE_EXP);                      // derived from the input
  const ratio = measure(exp, exp > 14 ? 1 : 3) / baseline;      // band check only
  const inBand = ratio >= expected * 0.55 && ratio <= expected * 1.8 ? "yes" : "no";
  printRow(G, "2^" + exp, (128 * 8 * 2 ** exp / 2 ** 20) + " MiB", expected + "x", inBand,
      (CANDIDATES * expected).toLocaleString("en-US"));
}

baseline work factor N=2^12; unit = one trial at the baseline factor
       N   memory   expected      in band  candidate list (units)
    2^12    4 MiB         1x          yes               1,000,000
    2^13    8 MiB         2x          yes               2,000,000
    2^14   16 MiB         4x          yes               4,000,000
    2^15   32 MiB         8x          yes               8,000,000
    2^16   64 MiB        16x          yes              16,000,000

In all five rows, the measured ratio stayed within the expected multiplier’s band. The curve is linear: when N doubles, both the unit cost and the memory consumption double. The last column is this cost’s counterpart on the attacking side — the entire candidate list of a million takes one million units at the baseline factor, sixteen million units at the N=2^16 factor.

The asymmetry does not show up in this table, but it is the only way to read the table. When the defender raises the factor sixteen-fold, they pay sixteen times more per login, and that is a delay the user does not notice. The attacker pays the same decision’s cost per candidate. On one side there are a few thousand logins a day, on the other a million candidates; the same factor adds up to very different totals on the two sides.

To turn the asymmetry into a number, it is enough to write out both sides’ totals. The fictional network has 340 field accounts, and each account logs in an average of three times a day; that is 1,020 verifications a day. At the N=2^16 factor, the defender’s daily total is 16,320 units. The attacker, though, has to go through the list from scratch for every record because of the salt: 340 × 16,000,000, or 5.44×10^9 units. The ratio between the two totals is over three hundred thousand. Raising the factor costs the defender a daily, fixed amount; it costs the attacker an amount multiplied by the number of records.

The memory column is a second, separate lever. At N=2^16, each attempt takes 64 MiB. This amount is negligible for a server doing a single verification; it is decisive for a party that wants to run many attempts in parallel, because parallelism is now bounded not by the number of processing units but by the amount of memory. The work factor slows the computation down; the memory coefficient makes the computation undistributable to cheap hardware.

At How Many Items Does the Table Become Useless

There is a path the work factor does not close. If the candidate list’s hashes are computed once and stored, the work needed for a leaked record drops to a single lookup; the computation is already done. Salt’s measured effect is exactly here, and its effect is written in item counts.

// password/salt.mjs — at how many items a rainbow table becomes useless against salt, and what
// determines salt length (model). The fictional regional measurement network has 340 field crew
// accounts. No randomness; every run gives the same numbers.

// CF9: a rainbow table fits all records at once that share the same salt; if the
//      salt is generated separately per record, the same table fits only one record.
// CF10: what determines salt length is not table size, but the salts not colliding with
//       each other; the criterion is the birthday bound measured in the second lesson.

const CANDIDATES = 1_000_000;                      // fictional candidate list
const RECORDS = 340;                               // fictional field crew account count
const pairs = (n) => (n * (n - 1)) / 2;
const printRow = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));
const format = (x) => x === 0 ? "0" : x >= 1e6 ? x.toExponential(2)
  : x >= 1 ? x.toLocaleString("en-US", { maximumFractionDigits: 2 })
  : x >= 1e-3 ? x.toFixed(3) : x.toExponential(1);

console.log(`candidate list ${format(CANDIDATES)}, records ${RECORDS}, record pairs ${format(pairs(RECORDS))}`);
const G = [9, 15, 14, 14, 20];
printRow(G, "salt bits", "distinct salt", "table items", "records fit", "expected collision");
for (const bit of [0, 8, 16, 32, 64, 128]) {
  const space = 2 ** bit;
  const distinct = Math.min(space, RECORDS);       // distinct salts in use
  printRow(G, bit, format(distinct), format(CANDIDATES * distinct),   // table items covering all
      format(Math.max(1, Math.round(RECORDS / space))), format(pairs(RECORDS) / space));
}
const threshold = Math.ceil(Math.log2(RECORDS));
console.log(`\nthe moment the salt space exceeds ${RECORDS} records (${threshold} bits), table items become ` +
  `${format(CANDIDATES * RECORDS)}: the same as doing the work from scratch per record.`);

console.log("\nthe collision criterion is stricter: expected salt collision should drop below 1");
const H = [12, 16, 12, 22];
printRow(H, "records", "record pairs", "min bits", "collision at 128 bit");
for (const n of [340, 12_400, 1e6, 1e9])
  printRow(H, format(n), format(pairs(n)), Math.ceil(Math.log2(pairs(n))), format(pairs(n) / 2 ** 128));

candidate list 1.00e+6, records 340, record pairs 57,630
salt bits  distinct salt   table items   records fit  expected collision
        0              1       1.00e+6           340              57,630
        8            256       2.56e+8             1              225.12
       16            340       3.40e+8             1               0.879
       32            340       3.40e+8             1              1.3e-5
       64            340       3.40e+8             1             3.1e-15
      128            340       3.40e+8             1             1.7e-34

the moment the salt space exceeds 340 records (9 bits), table items become 3.40e+8: the same as doing the work from scratch per record.

the collision criterion is stricter: expected salt collision should drop below 1
     records    record pairs    min bits  collision at 128 bit
         340          57,630          16               1.7e-34
      12,400         7.69e+7          27               2.3e-31
     1.00e+6        5.00e+11          39               1.5e-27
     1.00e+9        5.00e+17          59               1.5e-21

The first row is the unsalted setup, and the critical number is right there: a single table of a million items fits all 340 records. The work is done once and divided across the number of records.

In the following rows, the records fit column drops to 1 and never rises again. Even at eight bits of salt, a table now fits an average of just one record. This shows that salt’s real effect does not come from its length but from being separate per record.

This distinction also measures the most common flaw in setup. Using a single salt across the whole application, even if the salt is 128 bits long, falls into the zero-bit row of the table: the number of distinct salts is one, the table has a million items, and it fits all 340 records. Lengthening the salt does not change this row at all; the only thing that changes it is generating the salt separately per record. In the same way, a salt derived from a user code or a record timestamp also brings the table back, because the table can precompute that derivation too.

The threshold is read in the table items column. The moment the salt space exceeds the number of records — nine bits here — fitting the table to all records needs 3.4×10^8 items, and that is the same as doing the work from scratch for every record. Past nine bits, the column stays fixed; a longer salt does not make the table any more useless, because it is already completely useless. The rainbow table loses its advantage against salt at 9 bits.

What Determines Salt Length

CF10: what determines salt length is not table size, but the salts not colliding with each other; the criterion is the birthday bound measured in the previous lesson.

If nine bits is enough, why is the standard choice sixteen bytes? The second table gives the answer, and the criterion comes from the previous lesson. Salt has to be separate per record; two records landing on the same salt brings back the single-table advantage between those two records. The probability of landing on the same salt, though, is subject to the birthday bound.

The table turns this into a number. For the expected collision at 340 records to drop below one, at least sixteen bits are needed — not nine. When the record count rises to 12,400, the threshold goes to twenty-seven; to a million, thirty-nine; to a billion, fifty-nine. The threshold moves together with the record count, and how many records a setup will have is not known while it is being written.

A sixteen-byte salt is the choice that removes this uncertainty. At 128 bits, the expected collision is 1.5×10^-21 even at a billion records; whatever order of magnitude the record count reaches, the criterion holds. The rationale for the choice is not “longer is better,” but that it removes the need to compute the threshold. Since the salt is not secret and is stored alongside the hash, lengthening it costs nothing either: sixteen bytes each for 340 records is 5,440 bytes total, and that is too small to measure next to the rest of a single record. In all four rows of the last column, the collision probability stays at a magnitude that rounds to zero; choosing the parameter generously once is cheaper than recomputing it for every setup.

The Root the Two Factors Cannot Fix

This lesson’s third number is where the first two are not enough. The work factor multiplies unit cost, salt multiplies the number of sets that need repeating; neither touches the candidate list itself.

The trust root is right here, and its name is this: the password not being in the candidate list. If the root holds, the search is done not in the list but across the entire space, and the previous lesson’s 2^n bound applies. When the root breaks — that is, when the password is in the list — the one item that breaks is that account’s record, but the cost of breaking it is proportional to its position in the list. A candidate near the front of a million-entry list is found in a handful of units at the N=2^16 factor; a sixteen-fold work factor does not change that.

The item count is asymmetric because of this. Salt and the work factor protect all 340 records from falling at once: breaking happens record by record, not in bulk. The unpredictability root, though, is separate per record, and one record breaking does not affect the other 339. The three defenses each do a separate thing, and none of them replaces the other.

The cost of renewal is three separate numbers across the three defenses. Raising the work factor is zero items by hand: the record is regenerated with the new factor on the user’s next successful login, and nobody does anything. Renewing the salt is also zero items, because the salt is already renewed on every password change. In the case of leaked records, though, renewal is 340 items by hand — every account’s password has to be reset, and that takes individual human action, one by one. The legitimate work sitting in the leak window counts too: until the passwords are renewed, field crew logins either stay closed or stay open with a record considered broken. This course’s third column is read the same way in every lesson — not the size of the break, but the number of items touched by hand after the break.

Summary

• The work factor grows unit cost per attempt linearly: when N goes from 2^12 to 2^16, all five measurements stay within the expected multiplier’s band, and a list of a million goes from 1 million units to 16 million units.
• The same decision adds up to different totals on the two sides: the defender pays per login, the attacker pays per candidate; the memory coefficient additionally bounds parallelism by memory.
• In an unsalted setup, a single table of a million items fits all 340 records; when salt is separate per record, the same table fits only one record.
• The rainbow table loses its advantage against salt at 9 bits; beyond that, nothing makes it any more useless.
• The criterion determining salt length is not table size but collision: at 340 records the threshold is 16 bits, at a billion it is 59 bits; 128 bits makes computing the threshold unnecessary.

Next Step

The three lessons so far have revolved around one-way operations: hashing did not reverse, and not reversing was the whole point. The fictional measurement network’s actual traffic, though, has to reverse — a reading coming in from the field is opened at the center and turned into a bill. The first lesson tied this operation to two items: the key and an uncorrupted ciphertext. The next lesson takes up that first item together with its real problem. If both sides need to know the same key, how did that key get there? How many separate keys are kept between six branches and the center, how many items get added when a new branch joins the network, and how many connections have to be renewed when a single key leaks — all of it is countable.