Memory-Hard Functions and Password Hashing Costs

A password database is attacked under a different model from a message digest. The attacker has the stored values offline, so there is no rate limit, no lockout, and no interaction with the defender. What limits them is the cost of the work per guess. A general-purpose hash such as SHA-256 is designed for exactly the opposite property, maximum throughput per joule, so using it to store passwords hands the attacker the cheapest possible per-guess cost. A password hashing function is a hash whose cost per evaluation is deliberately inflated, and the design question is what resource to inflate.

Why iteration alone is not enough

The oldest approach is to hash repeatedly: apply SHA-256 a few hundred thousand times to the password and salt, store the result. This multiplies the attacker’s work by the iteration count, and it multiplies the defender’s work by the same factor. The trade is symmetric and therefore weak: any factor the defender can afford, the attacker can afford at the same multiple, and the attacker’s hardware is optimised for this exact operation.

The asymmetry that helps the defender is not time, it is the shape of the hardware. A GPU or an application-specific circuit hashes far more cheaply per unit cost than a general-purpose CPU, because the operation is a small fixed circuit with no large state. An iteration count chosen to make a login take 100 ms on a server CPU may let an attacker test an enormous number of candidates per second on a device built for the task. The ratio between the two is the defender’s actual loss, and the iteration count does not change it.

Two things change the ratio. A salt removes the attacker’s ability to precompute and amortise across users, which is necessary but does not affect per-guess cost. Memory hardness changes per-guess cost in a way that is expensive to replicate in parallel silicon.

Memory hardness as an economic constraint

A memory-hard function requires a large amount of memory per evaluation and accesses it in a pattern that is not predictable in advance. The constraint is economic rather than absolute: circuits can be built for any function, but memory is the most expensive resource per unit area to put on a chip next to compute, and it cannot be time-multiplexed across many parallel evaluations the way a small register file can. An attacker running k concurrent guesses must hold k copies of the working set. That is what turns the defender’s memory parameter into a bound on the attacker’s parallelism.

The distinction between memory-hard and memory-multiplexing-resistant matters. A function that touches a large table but only once per evaluation can be evaluated by many threads sharing one copy of the table, which recovers much of the parallelism. A function that fills its memory with values derived from the password forces each evaluation to have its own copy, because the contents differ per guess.

Sequential memory-hard functions strengthen this further. Percival’s scrypt makes the memory access pattern depend on the data being computed, so an attacker cannot cheaply precompute a time-memory trade-off that recomputes blocks on the fly. Recomputing a block costs about as much as storing it, so the trade is roughly linear, which is the point.

The parameters and what each one buys

Argon2, standardised in RFC 9106, exposes three parameters and two variants. Argon2d indexes memory in a data-dependent order, which maximises resistance to trade-off attacks and is appropriate when side channels are not a concern. Argon2i indexes in a data-independent order, which is appropriate when the attacker may observe memory access patterns but is weaker against trade-off attacks. Argon2id uses data-independent indexing for the first half of the first pass and data-dependent indexing thereafter, and is the recommended default.

The three parameters are:

• Memory m, in kibibytes, which sets the per-evaluation working set.
• Iterations t, the number of passes over the memory, which increases sequential work without increasing peak memory.
• Parallelism p, the number of lanes, which allows an implementation to use multiple threads and changes the structure of the computation.

The parameters are coupled. RFC 9106 imposes structural constraints: the memory must be at least 8p blocks, and the number of blocks per lane is rounded down so the division is exact. An implementation that passes a memory value not divisible by 4p silently rounds, which is a common source of parameter mismatch between a library’s notion of the cost and the specification’s.

/* Parameter choice, expressed as the values a verifier must store
   alongside the digest. RFC 9106's first recommended option is 2 GiB
   with t=1, p=4; the smaller working set here is the
   resource-constrained fallback. */
struct argon2_params {
    uint32_t variant;     /* Argon2d, Argon2i, or Argon2id */
    uint32_t passes;      /* t: 3 */
    uint32_t memory_kib;  /* m: 65536, i.e. 64 MiB */
    uint32_t lanes;       /* p: 4 */
    uint8_t  salt[16];    /* unique per record */
    uint32_t out_len;     /* 32 */
};

Note what the struct does not contain: the digest itself, which lives in the adjacent column of the record. A record that stores only the salt and the digest cannot be verified after a parameter change, and a record that stores the parameters but not the variant cannot distinguish Argon2i from Argon2id at the same cost settings, which are different functions with different security properties. The encoding of the record should be fixed by a specification rather than by the library’s own string format, because a migration between libraries is otherwise a migration between hash formats.

Choosing values under a real budget

The choice is an engineering decision with two constraints: the memory available on the authentication server per concurrent login, and the maximum latency acceptable to the client. Memory is usually the binding constraint, because each concurrent login holds its own working set; 100 concurrent logins at 64 MiB each is 6.4 GiB of transient allocation, which is a different operational proposition from 100 concurrent SHA-256 calls.

The usual procedure is to fix memory at the largest value the server can sustain at peak concurrency, then raise the iteration count until the latency budget is met, then check parallelism against available cores. Raising memory further is generally more valuable per unit of latency than raising iterations, because memory is what constrains the attacker’s hardware advantage. RFC 9106 gives two concrete profiles: a 2 GiB, single-pass, four-lane configuration for environments that can afford it, and a 64 MiB, three-pass, four-lane configuration as the fallback. The gap between them is a factor of 32 in memory and a third of the passes, which is a fair illustration of how much the two constraints can diverge.

Parameter increases need a migration path. The stored record’s parameters allow a rehash on successful login: verify with the stored parameters, then if they are below the current target, rehash the password with the new parameters and replace the record. Without parameters in the record, the migration cannot be done at all.

Splitting the cost between client and server

A password hash evaluated only on the server lets an attacker evaluate candidates offline at whatever rate their hardware allows once the database is stolen. Nothing in the primitive changes that; the attacker has the salt and the parameters and runs the same function. Memory hardness raises the per-guess cost, but the attacker still runs a batch job.

Moving part of the work to the client reduces the value of a stolen database only if the client contributes something the server does not store. In practice the contribution is usually the password itself, which the attacker is guessing, so the client-side work is simply part of the guess. A construction that requires a second secret held elsewhere, such as a hardware token or a separate service, changes the model fundamentally, and no hashing parameter can substitute for that.

Where these functions are the wrong tool

Memory-hard password hashing is not a general key derivation function for high-volume use. A service that derives a key per request from a per-request secret, rather than from a user password, should use a cheap KDF such as HKDF; paying a memory-hard cost per request turns an authentication service into a memory-exhaustion target.

It is also not a defence against a weak password. The cost multiplication applies uniformly to every guess, including the correct one, so a password drawn from a small space remains recoverable at a cost proportional to the space size. The parameters raise the constant, and the space size determines whether the constant matters.

The related question of what to do once a digest of a secret is derived and has to be fed into a MAC or a signature is a different design problem, taken up in prefix-free encodings. And the security margins these functions claim are stated against classical batch hardware; the quadratic speedup of quantum search applies to the password space rather than to the memory-hard core, which is a distinction that matters when estimating long-lived records.