Authentication and Password Security

Authentication is the process by which a system establishes that a claimed identity is genuine, distinct from authorization, which decides what an authenticated identity is allowed to do. Authentication factors are traditionally grouped into three categories: something you know (a password or PIN), something you have (a hardware token or phone), and something you are (a fingerprint or other biometric). Passwords remain the dominant "something you know" mechanism because they require no special hardware and are easy for humans to reason about, even though they are also the weakest link in practice. The central engineering challenge is this: a server must be able to check whether a submitted password matches the one a user originally chose, without ever storing that password in a form that would let an attacker who steals the database immediately recover it. The tool that makes this possible is the cryptographic hash function — a function $H$ that is easy to compute in one direction but computationally infeasible to invert, and that produces wildly different outputs for even slightly different inputs (the avalanche effect). Instead of storing a password $p$, the system stores $H(p)$. To verify a login attempt $p'$, it recomputes $H(p')$ and compares it to the stored value. If the two hashes match, the passwords almost certainly matched too, because a secure hash function makes it infeasible to find two different inputs with the same output (collision resistance). But hashing alone is not enough. If two users choose the same password, they get the same hash — leaking information and enabling precomputed dictionary attacks, where an attacker builds a lookup table of hash values for common passwords once and then reuses it against every stolen database forever. The fix is salting: generating a random string (the salt) per account, storing it alongside the hash, and computing $H(\text{salt} \parallel p)$ instead of $H(p)$. Salting does not make an individual password harder to guess, but it destroys the economy of scale that made precomputed attacks devastating, forcing the attacker to redo the entire computation separately for every account.

A password authentication system has two phases: registration (the user picks a password) and verification (the user logs in later). Both phases interact with a stored credential record consisting of a salt and a hash, never the password itself. ``` // ---------- REGISTRATION ---------- function REGISTER(username, password): salt = GENERATE_RANDOM_BYTES(16) // unique per account hash = SLOW_HASH(password, salt, cost) // e.g., bcrypt/Argon2 STORE(username, salt, hash, cost) // password itself is discarded from memory as soon as possible // ---------- VERIFICATION ---------- function LOGIN(username, submitted_password): record = LOOKUP(username) if record == NOT_FOUND: // still perform a dummy hash to avoid timing leaks SLOW_HASH(submitted_password, DUMMY_SALT, DEFAULT_COST) return REJECT candidate_hash = SLOW_HASH(submitted_password, record.salt, record.cost) if CONSTANT_TIME_EQUAL(candidate_hash, record.hash): return ACCEPT else: return REJECT // ---------- SLOW HASH (conceptual, bcrypt-style) ---------- function SLOW_HASH(password, salt, cost): state = INITIALIZE(password, salt) rounds = 2^cost for i in 1..rounds: state = EXPENSIVE_MIX(state) // CPU- and/or memory-hard step return ENCODE(state) ``` Two details in this pseudocode are load-bearing, not stylistic. First, `CONSTANT_TIME_EQUAL` compares hashes in time independent of where they first differ; a naive byte-by-byte comparison that returns early leaks timing information an attacker could exploit to guess the hash byte by byte (a timing side channel). Second, the dummy hash on a missing user prevents an attacker from distinguishing "no such user" from "wrong password" by measuring response time, which would otherwise let them enumerate valid usernames. The `cost` parameter is the crucial defensive knob. Doubling `cost` roughly doubles the work needed for both the legitimate server and any attacker attempting to guess passwords offline. Because the legitimate server only pays this cost once per login attempt (a rare event, dominated by network latency anyway), while an attacker wants to try billions of guesses, tuning `cost` upward hurts the attacker vastly more than the defender in relative terms.

Correctness argument. The verification procedure is correct if and only if two properties of the hash function hold: (1) determinism — $H(s \parallel p)$ always produces the same output for the same salt and password, so a legitimate user's re-entered password always reproduces the stored hash; and (2) second-preimage resistance — given $s$ and $H(s \parallel p)$, it is computationally infeasible to find any $p' \neq p$ with $H(s \parallel p') = H(s \parallel p)$. Property (1) guarantees no false rejections of genuine users (up to negligible hash-collision probability). Property (2) guarantees that an attacker cannot forge a matching hash without knowing the original password, other than by guessing it directly. The salt does not change these two properties; it only affects the cost of exhaustive search, discussed below.

Time complexity of legitimate use. A single login costs $O(2^{c})$ applications of the internal mixing step, where $c$ is the cost/work-factor parameter — this is by design, since `SLOW_HASH` runs a fixed loop of $2^{c}$ rounds. For the legitimate server, this is a small constant (typically tuned to 100–500 milliseconds), negligible compared to network round-trip time. Space complexity is $O(1)$ per stored credential for classical bcrypt (fixed-size internal state) but can be tuned to $O(m)$ memory for memory-hard schemes like Argon2, where $m$ is a configurable memory parameter.

Time complexity of attack. Consider an attacker who has stolen a database of $N$ salted hashes and wants to test a candidate password $p$ against a specific account. Because each account has an independent salt, checking $p$ against all $N$ accounts costs $N$ separate hash evaluations, each $O(2^c)$ — there is no way to amortize the work across accounts, unlike the unsalted case where one hash of $p$ reveals every account using that same password instantly (an $O(1)$-amortized lookup once the table is built). Formally, let $D$ be the size of a dictionary of candidate passwords the attacker tries. Cracking one specific salted account costs:

while cracking the same password shared unsalted across $N$ accounts, using one precomputed table, costs only:

This is the precise sense in which salting multiplies the attacker's total work by a factor of $N$ when facing many accounts — the attacker can no longer reuse a single table.

Correctness of the security claim (not just an assertion). Suppose, for contradiction, that an efficient algorithm $\mathcal{A}$ could recover a random password $p$ from $(s, H(s \parallel p))$ significantly faster than exhaustive search over the password space, for a hash function $H$ modeled as a random oracle. Then $\mathcal{A}$ would violate the one-wayness (preimage resistance) assumption that defines a secure cryptographic hash — the same assumption underlying Cryptographic Hash Functions used elsewhere in security (digital signatures, integrity checks). Since no such efficient inversion algorithm is known for standard hash constructions (SHA-256, etc.), the best known generic attack remains brute-force search over the password space, whose cost we can bound explicitly (see Worked Example below). This is why password strength — the entropy of the password itself — ultimately bounds security no matter how good the hash function is; hashing cannot manufacture entropy that was never in the password.

Honest tradeoffs. Raising the cost factor $c$ slows attackers but also slows every legitimate login and increases server CPU/memory load at scale (millions of logins per day). Memory-hard functions (scrypt, Argon2) further defend against attackers using cheap, massively parallel GPU or ASIC hardware, because memory bandwidth is harder to parallelize cheaply than raw arithmetic — but they also increase legitimate server memory pressure. There is no free lunch: password security is fundamentally about shifting cost onto attackers at a real, nonzero cost to defenders.

Suppose an attacker steals a database from a breached website. The `users` table row for Alice contains:

The attacker has no plaintext password, only this record, plus a common dictionary of the 10 million most popular leaked passwords (a realistic real-world list size), plus knowledge that Alice's employer requires passwords of at least 8 characters.

Step 1 — rule out precomputation. Because the salt `f3a9...` is unique to Alice's account, any rainbow table the attacker built in advance (mapping common-password → hash, without a salt) is useless: those precomputed hashes were computed without this salt and will never match.

Step 2 — dictionary attack, one guess at a time. The attacker must, for each candidate password $p_i$ in the 10-million-entry dictionary, compute:

Each bcrypt evaluation at cost 12 takes roughly 250 ms on ordinary server hardware (bcrypt is deliberately not GPU-friendly, so this number does not shrink much on consumer GPUs, unlike a fast hash like an unsalted single MD5).

Step 3 — total time estimate.

With a cluster of 1,000 cores working in parallel, this drops to about 41 minutes — still nontrivial, and this is per account, since Alice's neighbor Bob has a different salt and must be attacked separately from scratch.

Contrast with an unsalted, fast MD5 hash (a real historical mistake made by many early systems): MD5 computes in roughly 1 microsecond, and without a salt the attacker precomputes the dictionary's hashes exactly once, then checks them against every stolen row via a simple hash-table lookup — an $O(1)$ check per account after the one-time $O(D)$ precomputation. For a breach of $N = 1{,}000{,}000$ accounts, the attacker's total marginal cost per additional cracked account is essentially zero once the table exists. This comparison — 29 CPU-days-per-account versus microseconds-for-all-accounts — is the entire point of salting and slow hashing, made concrete.

Step 4 — what if Alice's password wasn't in the dictionary? Suppose Alice actually chose a random 10-character password drawn from a 62-character alphabet (upper, lower, digits). Its entropy is:

Exhaustive search over this space at bcrypt cost 12 (250 ms/guess, 1,000 cores) requires:

This dramatic gap between "in a 10-million-word dictionary" (29 days) and "random 10 characters" (millions of years) illustrates precisely why password entropy, not just hashing scheme, ultimately determines real-world security — the hash function only sets the per-guess cost, while the password itself sets the size of the space that must be searched.

Password-based login dates to the earliest time-sharing systems, where multiple users shared one machine and needed a way to separate accounts. The core cryptographic ideas that made secure storage possible — one-way functions, salting, and formal notions of computational hardness — trace back to foundational work in cryptography and computer science more broadly.

Password hashing schemes are embedded in nearly every authentication system in production use. Operating systems (Linux's `/etc/shadow`, Windows credential stores), web frameworks (Django, Rails, and most authentication libraries default to bcrypt or Argon2), and password managers (which must securely derive an encryption key from a master password using the same slow-hashing principles) all rely on these ideas directly. Standards bodies such as NIST and OWASP publish explicit guidance recommending Argon2id or bcrypt with tuned cost parameters, and mandate salts of sufficient length and randomness. Beyond raw password storage, the same conceptual toolkit — controlled computational cost as a defensive mechanism — appears in proof-of-work systems, key-derivation functions (PBKDF2 for disk encryption), and CAPTCHA-adjacent anti-abuse systems. Understanding password authentication is also the natural entry point into broader identity and access questions: once a system can verify who someone is, it must still decide what they can do, which is the domain of Access Control Models. And because the overwhelming majority of real-world password breaches stem from human behavior — reuse, weak choices, phishing — rather than cryptographic failure, this topic connects directly to the study of Security Engineering and the Human Factor.

Ask the tutor: How would you design a login rate-limiter that resists both brute-force attacks and denial-of-service lockout abuse against legitimate users?