Password Storage

## The attack is guessing, not inversion A cryptographic hash maps input to a fixed-size digest and is designed so that, given a digest, finding *any* input that produces it is infeasible. That guarantee is about the space of all possible inputs. Passwords occupy a tiny, heavily skewed corner of that space: real users choose from a distribution dominated by common words, names, dates, keyboard patterns and predictable mutations. An attacker holding a stolen digest therefore never attempts inversion. They generate candidates — from leaked password corpora, from dictionaries with mutation rules, from targeted personal data — hash each one and compare. The mathematics of preimage resistance is untouched and irrelevant. This reframes the entire problem. The only defensive lever is the **cost of testing one candidate**, multiplied by the number of candidates the attacker must test. You cannot raise the second term much — users choose the passwords they choose — so you raise the first. ## Speed is a feature everywhere else and a defect here General-purpose hashes are engineered for throughput: they are used to checksum files, build Merkle trees and sign large documents, so implementers optimise them hard, and hardware vendors add dedicated instructions. The result is that a single commodity graphics card evaluates a fast hash on the order of billions of candidates per second, and rented fleets multiply that. Against that rate, an entire realistic dictionary of human passwords is exhausted in a time measured in minutes to hours. A password function inverts the design goal. It is built so that one evaluation costs a configurable amount of work — typically tuned so the defender spends on the order of a tenth of a second per login. The defender pays that cost once per authentication; the attacker pays it once per guess, and the attacker makes billions of guesses. The asymmetry is the whole design. ## Why the salt is not optional and not a secret A **salt** is a unique, random value generated per password and stored alongside the digest. It is not secret; assume the attacker has it the moment they have the digest. It defeats two things. *Precomputation.* Without a salt, an attacker can compute a table of digests for a candidate list once — in the general case a time/memory trade-off structure such as a rainbow table — and then reverse any number of stolen digests by lookup. Salting means the table would have to be recomputed per salt, which destroys the economics of precomputation entirely. *Amortisation across users.* Without a salt, one hash evaluation of the candidate "summer2024" tests it against every user in the dump simultaneously, so cracking ten million accounts costs the same as cracking one. With unique salts, each user must be attacked separately, restoring a linear relationship between accounts and attacker cost. It also stops the trivially observable fact that two users share a password, which is itself a leak. The salt must be **random and unique per password**, from a cryptographically secure generator, and long enough that collisions do not occur in practice. Deriving it from the username or the user id is a classic mistake: usernames repeat across sites, so cross-site precomputation returns, and a rename changes the salt. ## The work factor and why it must be adjustable Hardware gets faster; a fixed cost silently erodes. A password function therefore exposes a **cost parameter** — iteration count, or a cost exponent, or explicit time, memory and parallelism settings — and stores it in the record next to the salt. That single design choice enables two things: the parameters can be raised over time, and each stored value carries the parameters it was created with, so old and new records verify correctly side by side and can be upgraded opportunistically when the user next authenticates. ## What the stored record looks like conceptually A password record is not just a digest. It carries an algorithm identifier, the parameters used, the salt, and the derived output — commonly encoded as a single self-describing string. That structure is what makes migration and parameter increases possible at all; a bare digest column has thrown away the information needed to evolve. ## The two boundary claims First, a password function protects only the *offline* attack that follows a database compromise. It does nothing about guessing against your live login endpoint, which is a rate-limiting and detection problem, nor about credential reuse from other breaches, which needs breached-password screening and a second factor. Second, adding iterations to a fast hash by hand — hashing repeatedly in a loop — is not equivalent to using a purpose-built function. It raises cost linearly while leaving the operation entirely parallel-friendly and cheap in memory, which is exactly the property that modern password functions target. Home-rolled schemes also routinely lose the salt handling and the parameter encoding along the way.