Key Derivation Functions: From Passwords to Cryptographic Keys

The average human-chosen password has between 20 and 40 bits of entropy. A strong password – 16 random characters from the full printable ASCII set – reaches approximately 100 bits. An AES-256 encryption key requires 256 bits of uniformly random entropy. The gap between what humans can remember and what cryptography demands is enormous: a factor of 2^156 between a strong password and an AES-256 key, and a factor of 2^216 between a typical password and the same key.

Key derivation functions bridge this gap. They transform low-entropy inputs (passwords, passphrases, shared secrets from Diffie-Hellman exchanges) into high-entropy outputs suitable for use as cryptographic keys. They do this through two distinct mechanisms: key stretching (making brute-force attacks computationally expensive) and key extraction (distilling non-uniform entropy into uniformly distributed key material).

These are not the same operation, and conflating them is a common source of security errors. Password-based KDFs (PBKDF2, bcrypt, scrypt, Argon2) are designed for key stretching: they deliberately waste computational resources to slow down attackers. Extract-and-expand KDFs (HKDF) are designed for key extraction: they efficiently transform high-entropy but non-uniform inputs into uniformly distributed keys. Using HKDF on a password is wrong. Using Argon2 to derive TLS session keys is wasteful.

The Threat Model: Offline Password Attacks

When an attacker obtains a database of password hashes, they perform an offline attack: they hash candidate passwords using the same function and compare outputs. The attacker’s constraint is computational cost per guess. If hashing one password takes 1 microsecond, an attacker with a modern GPU can test approximately 10 billion passwords per second. At that rate:

• A 6-character lowercase password (26^6 = ~300 million possibilities): cracked in 0.03 seconds
• A 8-character mixed-case-plus-digits password (62^8 = ~2 * 10^14): cracked in ~5.5 hours
• A 12-character password from the full printable ASCII set (95^12 = ~5.4 * 10^23): cracked in ~1.7 million years

Key derivation functions shift these numbers by making each hash evaluation deliberately slow. If hashing takes 100 milliseconds instead of 1 microsecond, the attacker’s throughput drops by a factor of 100,000. The 8-character password now takes 63 years instead of 5.5 hours.

PBKDF2 (2000)

PBKDF2 (Password-Based Key Derivation Function 2), specified in RFC 8018 (originally RFC 2898), is the oldest widely deployed password-based KDF. It iterates HMAC:

DK = T_1 || T_2 || ... || T_dklen/hlen
T_i = U_1 XOR U_2 XOR ... XOR U_c
U_1 = HMAC(Password, Salt || i)
U_2 = HMAC(Password, U_1)
...
U_c = HMAC(Password, U_{c-1})

where c is the iteration count. NIST SP 800-132 recommends at least 10,000 iterations for PBKDF2-HMAC-SHA256. OWASP recommends 600,000 iterations as of 2024.

Strengths: Simple, well-analyzed, widely implemented, FIPS approved. Available in every major cryptographic library and hardware security module.

Weaknesses: PBKDF2 is embarrassingly parallelizable. Each HMAC iteration is independent of the others (except the sequential chain), but multiple password candidates can be tested in parallel. GPUs excel at this: a 2024 benchmark showed an RTX 4090 computing 3.2 million PBKDF2-HMAC-SHA256 hashes per second at 600,000 iterations. ASICs (custom hardware designed for specific computations) can achieve even higher throughput at lower energy cost.

The fundamental problem: PBKDF2 uses only computation (CPU cycles) as its cost metric. An attacker willing to spend money on specialized hardware can overcome computational cost with parallelism.

bcrypt (1999)

bcrypt, designed by Niels Provos and David Mazieres, is based on the Blowfish cipher’s expensive key setup phase. It requires 4 KB of memory (the Blowfish S-box state) that must be accessed repeatedly during the derivation.

EksBlowfishSetup(cost, salt, password)
  state = InitState()
  state = ExpandKey(state, salt, password)
  repeat (2^cost) times:
    state = ExpandKey(state, 0, password)
    state = ExpandKey(state, 0, salt)
  return state

The cost parameter controls the number of iterations exponentially: cost=12 means 2^12 = 4,096 iterations. Each iteration modifies the 4 KB S-box state in a data-dependent pattern, creating a sequence of memory accesses that is difficult to parallelize on GPUs.

Strengths: Memory-dependent computation (4 KB) makes GPU attacks harder. The 2024 RTX 4090 benchmark showed 184,000 bcrypt hashes per second at cost=12 – about 17x slower than PBKDF2 at equivalent wall-clock time. Well-tested, widely deployed in web frameworks (Django, Rails, Node.js).

Weaknesses: The 4 KB memory requirement was adequate in 1999 but is trivial for modern hardware. GPUs have gigabytes of fast memory and can process many bcrypt instances in parallel, each with its own 4 KB working set. bcrypt is also limited to 72 bytes of password input (a Blowfish limitation).

scrypt (2009)

Colin Percival designed scrypt specifically to be memory-hard: the algorithm requires a large amount of memory (configurable, typically 16 MB to 1 GB) and the memory access pattern depends on the input, preventing time-memory tradeoffs.

The core construction is the ROMix function:

1. Generate a large array V of pseudorandom blocks by iteratively applying a mixing function (Salsa20/8 core).
2. Access V in a data-dependent pattern: at each step, the index into V is derived from the current state.
3. Mix the accessed block into the current state.

The memory-hardness argument: if the attacker reduces memory usage (storing only a fraction of V and recomputing blocks as needed), the computation time increases proportionally. A device with half the memory takes twice as long. A device with 1/N the memory takes N times as long. This “sequential memory-hardness” means the cost of the attack is proportional to the product of memory and time, regardless of how the attacker allocates resources.

Strengths: The first practical memory-hard KDF. Used by Litecoin, Dogecoin, and several other cryptocurrencies for proof-of-work. Effective against GPU and ASIC attacks: a 2024 analysis estimated that scrypt with N=2^20 (1 GB memory) reduces ASIC advantage to less than 10x over general-purpose hardware, compared to 1000x+ for PBKDF2.

Weaknesses: scrypt’s memory-hardness relies on the Salsa20/8 mixing function, which has not received as much cryptanalytic attention as SHA-256 or AES. The parameter space (N, r, p) is confusing for implementers – incorrect parameter choices (such as very high p with low N) can reduce memory-hardness. scrypt provides no built-in resistance to side-channel attacks (cache-timing attacks can leak the memory access pattern).

Argon2 (2015)

Argon2, designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich, won the Password Hashing Competition (PHC) in 2015, beating 23 other submissions. It comes in three variants:

Argon2d (data-dependent): Memory access pattern depends on the data being processed. Provides maximum resistance to GPU and ASIC attacks but is vulnerable to side-channel attacks (an attacker who can observe memory access patterns can recover information about the password).

Argon2i (data-independent): Memory access pattern is independent of the password. Resistant to side-channel attacks but provides weaker memory-hardness guarantees (a 2016 analysis by Alwen and Blocki showed that Argon2i could be computed with significantly less memory than intended, though this was addressed in later versions).

Argon2id (hybrid): Uses data-independent addressing for the first pass (protecting against side-channel attacks during initialization) and data-dependent addressing for subsequent passes (maximizing memory-hardness). This is the recommended variant for most applications.

The Algorithm

1. Initialize: Allocate a memory array of m KiB, organized as q columns (where q = m / (4 * p), with p parallel lanes).
2. Fill: Populate the memory array using the Blake2b hash function, with each block depending on two previously computed blocks.
3. Iterate: Repeat the filling process t times (the iteration count).
4. Finalize: Extract the output by hashing the last column of the memory array.

The memory access pattern in Argon2d selects the reference block based on the content of the current block, creating data-dependent addressing that prevents precomputation. The parallel lanes (p parameter) allow multi-core utilization without reducing security.

Recommended Parameters (OWASP 2024)

At 47 MiB memory and 1 iteration, Argon2id takes approximately 50-100ms on a modern server – fast enough for login flows, slow enough to make brute-force attacks expensive.

HKDF: Extract-and-Expand for High-Entropy Inputs

HKDF (HMAC-based Key Derivation Function), specified in RFC 5869, serves a completely different purpose than the password-based KDFs above. It is designed for inputs that already have high entropy but may not be uniformly distributed – such as Diffie-Hellman shared secrets, which are elements of an algebraic group and have structure that makes them unsuitable for direct use as symmetric keys.

HKDF operates in two phases:

Extract: HKDF-Extract(salt, input_key_material) = HMAC(salt, IKM)

This produces a pseudorandom key (PRK) of fixed length, uniformly distributed if the IKM has sufficient entropy.

Expand: HKDF-Expand(PRK, info, length)

This uses HMAC in a counter-mode construction to expand the PRK into multiple derived keys of arbitrary length.

HKDF is the key derivation function used in TLS 1.3 (deriving handshake and application keys from the ECDHE shared secret), in the Signal Protocol (deriving chain keys and message keys from the root key), and in numerous other protocols.

HKDF is fast – a single HMAC computation. It provides no protection against low-entropy inputs. Using HKDF on a password is equivalent to hashing the password once – trivially brute-forceable.

Choosing the Right KDF

The decision tree is straightforward: if the input might be guessed by an attacker (passwords, PINs), use a memory-hard password KDF. If the input is cryptographically strong (random keys, DH outputs), use HKDF.

Real-World Failures

LinkedIn (2012). 6.5 million password hashes leaked. The passwords were hashed with unsalted SHA-1 – not even a KDF, just a single hash. Cracked in hours.

Ashley Madison (2015). 36 million bcrypt hashes leaked. Despite bcrypt at cost=12, researchers cracked 11 million passwords within days – not by attacking bcrypt, but by discovering that the system also stored MD5-based hashes of the same passwords in an older database. The strongest KDF is irrelevant if a weaker hash of the same password exists elsewhere.

LastPass (2022). Encrypted password vaults were stolen. The master password was protected by PBKDF2-HMAC-SHA256 with 100,100 iterations. Researchers estimated that a well-resourced attacker with GPU clusters could crack weak master passwords (8 characters, common patterns) within weeks to months. OWASP’s 2024 recommendation of 600,000 iterations for PBKDF2 reflects this assessment.

These incidents illustrate a consistent pattern: the KDF must be strong, the implementation must be correct, and no weaker parallel path to the same secret can exist.

The Stealth Cloud Perspective

Stealth Cloud’s zero-knowledge architecture does not use password-based authentication – sessions are authenticated via wallet signatures (SIWE), and encryption keys are generated from the Web Crypto API’s cryptographic random number generator, not derived from passwords. This eliminates the password-based KDF question entirely for the primary authentication and encryption flows.

However, HKDF plays a central role in the key hierarchy. Session keys derived from the ECDH exchange during wallet authentication pass through HKDF to produce the AES-256-GCM keys used for message encryption. The extract phase distills the ECDH shared secret into uniformly random material. The expand phase derives separate keys for encryption, authentication, and key confirmation – ensuring that compromise of one derived key does not affect others.

The key management design follows a principle that the KDF landscape makes clear: use the right tool for the right input. Passwords get memory-hard functions. Cryptographic secrets get HKDF. Mixing these up – stretching what does not need stretching, or failing to stretch what does – is how systems fail.

Stealth Cloud’s decision to use wallet-based authentication rather than passwords is itself a KDF decision: by requiring a 256-bit cryptographic secret (the wallet’s private key) instead of a human-memorable password, the system avoids the entire category of brute-force attacks that password KDFs exist to mitigate. The strongest key derivation function is the one you do not need, because the input already has full entropy.