Salted Password Hashing and the Cost of a Verification

A stored password record is not a password. It is the output of a function whose inputs are the password, a random salt, and a set of cost parameters. Everything about password storage follows from one economic question, which is the price of a single guess to the attacker against the price of a single verification to the defender. The two numbers are not the same, and the entire design space of password hashing exists to widen the gap between them.

The salt prevents amortisation, not decryption

A hash of a password with no salt can be attacked with a precomputed table. An attacker hashes every entry of a dictionary once and stores the results; every subsequent record is then looked up in constant time. The table is expensive to build once and free to reuse across millions of records and, if the corpus of common passwords is the target, across many breaches. A salt removes that reuse. Each record carries a distinct random value mixed into the input, so a table built for one record is useless for the next. The attacker’s marginal cost per record becomes the full cost of hashing the dictionary again.

This is also why salt reuse is a real defect rather than a stylistic one. Two records that share a salt can be attacked with one table, and the amortisation that salts are supposed to prevent returns. The same applies to a single application-wide salt, a salt derived from the user identifier alone, or a salt generated from a counter or timestamp: a predictable salt lets an attacker precompute against a specific deployment before it is breached, because the salt values are known in advance.

The salt is not secret. It is stored beside the digest, and no security depends on hiding it. What it must be is unique and unpredictable, which means drawn from a cryptographically secure random source. Sixteen bytes is the common floor, and the collision probability across a corpus of even a billion records is negligible at that width. Wider salts cost almost nothing, since the record grows by a few dozen bytes at most.

A pepper is a different device: a secret key, stored outside the database, mixed into the input before hashing. It helps only in the case where the database is stolen but the application configuration is not, which is a narrower threat than a full server compromise. Its cost is operational. Rotating a pepper invalidates every record unless the record identifies which pepper was used, so a versioned key identifier has to travel with the digest, and a rotation becomes a background rehash rather than a configuration change.

Cost parameters and the parallel-attack model

The second input under defender control is the work factor. Its purpose is not to make a single guess infeasible; it is to make a billion guesses expensive in aggregate.

PBKDF2, defined in RFC 8018 and profiled for password use by NIST SP 800-132, iterates a pseudorandom function such as HMAC-SHA-256 a chosen number of times. Its cost is purely computational: attacker throughput scales with the number of hash cores that can be bought. Because SHA-256 compresses data with a small, regular circuit, the ratio between an ASIC and a general-purpose CPU core is large, and a GPU can run many chains in parallel with modest memory. An iteration count that costs a defender a hundred milliseconds costs an attacker far less per guess on dedicated silicon.

bcrypt, from the 1999 Provos–Mazieres design, re-keys the Blowfish cipher repeatedly, with a cost parameter that doubles the number of rounds. Its working set is a few kilobytes of table, small enough to sit in L1 cache, so it resists some parallelism but remains friendly to specialised hardware. It also has two interface quirks that matter later: the input is truncated at 72 bytes, and some implementations stop at a NUL byte.

Memory-hard functions change the cost axis. scrypt (RFC 7914) allocates roughly $128 \cdot N \cdot r$ bytes and reads them in a data-dependent order, so an attacker must buy memory bandwidth and capacity rather than raw arithmetic. With $N = 2^{14}$ and $r = 8$ the allocation is 16 MiB per concurrent guess. Argon2 (RFC 9106) generalises the idea with an explicit memory cost in kibibytes, a time cost, and a degree of parallelism, and its hybrid variant Argon2id fills memory in a way that resists both cache-timing attacks and the time-memory trade-offs that weaken purely data-independent designs. RFC 9106 suggests, for a setting where the defender can spare the resources, parameters on the order of 2 GiB of memory with a single pass, or 64 MiB with three passes; deployed systems usually choose smaller because every concurrent login allocates its own working set.

That last point is the trade the defender actually faces. Verification latency is paid once per login and is easy to budget. Peak memory is paid once per concurrent login. Sixty-four mebibytes multiplied by two hundred simultaneous authentications is roughly 12.8 GiB, which will exhaust most application servers before the attacker is inconvenienced. The parameter choice is therefore a joint decision about latency, memory, and admission control, and the honest way to make it is to fix a target latency on the actual deployment hardware and derive the cost from measurement rather than copying a number from a recommendation written for a different machine.

The record must describe its own function

Because parameters change over time, and because records written years ago must still verify, the stored record has to be self-describing. The PHC string format does this with a delimited layout:

$argon2id$v=19$m=65536,t=3,p=4$c2FsdHlzYWx0eXNhbHR5c2$0p8mF3k...

The leading field names the function, then its version, then the parameters, the salt in unpadded base64, and the digest. bcrypt uses a similar modular crypt form, $2b$12$ followed by 22 characters of encoded salt and 31 characters of digest. The exact grammar matters less than the property it guarantees: a verifier can parse a record written by an older configuration, verify against it correctly, and then re-derive with current parameters and overwrite the record on a successful login. That rehash-on-login path migrates a population without a flag day, a downtime window, or a forced password reset, and it is the main operational reason to keep parameters in-band rather than in application configuration.

Column sizing should account for the format. A record holding a function name, four parameters, a 16-byte salt, and a 32-byte digest encodes to roughly a hundred bytes, and records using longer salts or the 64-byte output of some configurations are larger still.

Verification, in the small

The verification routine is short, and most of its correctness lives in what it refuses to do: it refuses to compare digests with a short-circuiting equality operator, and it refuses to trust parameters from outside the record.

import base64, hashlib, hmac, secrets

CURRENT_ITERATIONS = 600_000

def make_record(password: bytes, iterations: int = CURRENT_ITERATIONS) -> str:
    salt = secrets.token_bytes(16)
    dk = hashlib.pbkdf2_hmac("sha256", password, salt, iterations, dklen=32)
    return "pbkdf2-sha256${}${}${}".format(
        iterations,
        base64.b64encode(salt).decode(),
        base64.b64encode(dk).decode(),
    )

def verify(password: bytes, record: str) -> tuple[bool, bool]:
    algo, iters, salt_b64, dk_b64 = record.split("$")
    if algo != "pbkdf2-sha256":
        raise ValueError("unknown record format")
    iterations = int(iters)                 # parameter comes from the record, not the request
    salt = base64.b64decode(salt_b64)
    expected = base64.b64decode(dk_b64)
    candidate = hashlib.pbkdf2_hmac("sha256", password, salt, iterations, dklen=len(expected))
    ok = hmac.compare_digest(candidate, expected)
    return ok, ok and iterations < CURRENT_ITERATIONS

The second return value drives the upgrade. It is computed only after a successful verification, because rehashing on a failed attempt would let an unauthenticated request trigger the most expensive operation in the system.

Where the construction breaks

The failure modes cluster around inputs that do not survive the pipeline intact. bcrypt’s 72-byte limit means that a long passphrase is silently truncated; the standard remedy is to pre-hash the password with SHA-256 and encode the digest, which keeps the input to a fixed 44 characters and avoids both the length limit and the NUL-byte hazard. Unicode raises a subtler version of the same problem. If passwords are normalised to a canonical form, the normalisation must be identical at enrolment and at verification, must be documented, and cannot be changed later without invalidating every record; if they are not normalised, the same visual password typed on two keyboards may be two different byte strings. Neither choice is wrong, but the choice has to be made once and held.

Cost parameters decay. A record written with a thousand PBKDF2 iterations was defensible when written and is nearly free to attack now, which is why the parameter must be read from the record and compared against a current floor rather than assumed. Salt reuse, copied rows, and test fixtures promoted into production data produce the same effect as a missing salt.

Finally, the digest comparison itself is a channel. A byte-by-byte comparison that returns at the first mismatch leaks how many leading bytes were correct, and the same class of bug appears in the lookup that finds the record. Constant-time comparison covers the mechanics and, more importantly, the limits of what removing that channel can buy.

Hashing raises the cost of a guess, but it does not change the number of guesses a weak password requires. A dictionary entry that ranks in the first few thousand of a common-password list falls in seconds against any affordable parameter set. The complement to a strong KDF is refusing to accept passwords that appear in breach corpora, and bounding how many online attempts a single account can absorb, both of which belong to the economics described in online guessing bounds. Password hashing is the last line that holds when the database is already gone; it is not the first.