Key Derivation Functions

Every time you log into a website, two very different things collide: the password you typed — short, human-memorable, perhaps reused — and the cryptographic machinery underneath, which wants a 256-bit random key with every bit equally likely.

A key derivation function (KDF) is the bridge. It takes your weak, low-entropy secret and stretches it into something that looks to a computer like it came from a truly random source. But the stretch is not free. KDFs are deliberately slow and memory-hungry — not by accident or poor engineering, but because that cost is the security. Your login check costs a millisecond; an attacker trying a billion password guesses pays the same cost a billion times over.

This article traces the design of modern KDFs — from the naive one-shot hash to Argon2, the 2015 Password Hashing Competition winner — and shows why the best defense against a GPU cracking farm is simply making each guess expensive enough to matter.

The core insight of KDFs is the cost asymmetry: verification costs a fixed, small amount of work; brute-force cracking must pay that same cost for every guess.

<div class="kdf-app">
  <div class="row">
    <label>{{lbl_password}} <input id="pw" type="text" value="hunter2" maxlength="32" autocomplete="off"></label>
  </div>
  <div class="row">
    <label>{{lbl_cost}}
      <select id="cost">
        <option value="1">{{opt_1x}}</option>
        <option value="3" selected>{{opt_3x}}</option>
        <option value="10">{{opt_10x}}</option>
        <option value="30">{{opt_30x}}</option>
      </select>
    </label>
  </div>
  <button id="run" type="button">{{btn_run}}</button>

  <div class="results" id="results" style="display:none">
    <div class="card fast">
      <div class="card-title">MD5 (fast hash)</div>
      <div class="card-value" id="md5-time">—</div>
      <div class="card-label">{{lbl_md5_card}}</div>
      <div class="card-rate" id="md5-rate"></div>
      <div class="card-attack" id="md5-attack"></div>
    </div>
    <div class="card slow">
      <div class="card-title">Argon2id (KDF)</div>
      <div class="card-value" id="kdf-time">—</div>
      <div class="card-label">{{lbl_kdf_card}}</div>
      <div class="card-rate" id="kdf-rate"></div>
      <div class="card-attack" id="kdf-attack"></div>
    </div>
  </div>

  <div class="timeline" id="timeline" style="display:none">
    <div class="tl-title">{{tl_title}}</div>
    <div class="bars" id="bars"></div>
    <div class="legend">{{legend}}</div>
  </div>
</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #1a2634; font-size: 14px; padding: 4px; }
.kdf-app { display: flex; flex-direction: column; gap: 10px; }
.row { display: flex; align-items: center; gap: 8px; }
label { font-weight: 600; font-size: 13px; display: flex; align-items: center; gap: 6px; flex-wrap: wrap; }
input[type=text] { font-size: 14px; padding: 5px 8px; border: 1px solid #b0bec5; border-radius: 6px; width: 160px; }
select { font-size: 13px; padding: 5px 8px; border: 1px solid #b0bec5; border-radius: 6px; }
button { font: 600 13px system-ui; padding: 7px 16px; background: #1d3557; color: #fff;
         border: none; border-radius: 8px; cursor: pointer; }
button:hover { background: #2a4a77; }
.results { display: grid; grid-template-columns: 1fr 1fr; gap: 10px; }
.card { border-radius: 10px; padding: 12px; }
.card.fast { background: #fff3cd; border: 1px solid #ffc107; }
.card.slow { background: #d4edda; border: 1px solid #28a745; }
.card-title { font-weight: 700; font-size: 13px; margin-bottom: 4px; }
.card-value { font-size: 22px; font-weight: 800; font-variant-numeric: tabular-nums; }
.card.fast .card-value { color: #c55a00; }
.card.slow .card-value { color: #145a23; }
.card-label { font-size: 11px; color: #555; margin: 2px 0 6px; }
.card-rate { font-size: 12px; font-weight: 600; margin-bottom: 4px; }
.card-attack { font-size: 11px; color: #444; line-height: 1.4; }
.timeline { background: #f0f4f8; border-radius: 10px; padding: 12px; }
.tl-title { font-weight: 700; font-size: 12px; margin-bottom: 8px; }
.bars { display: flex; flex-direction: column; gap: 6px; }
.bar-row { display: flex; align-items: center; gap: 8px; }
.bar-label { font-size: 11px; font-weight: 600; width: 90px; flex-shrink: 0; }
.bar-track { flex: 1; background: #dde5ed; border-radius: 4px; height: 18px; overflow: hidden; position: relative; }
.bar-fill { height: 100%; border-radius: 4px; transition: width .4s; }
.bar-fill.fast { background: #e63946; }
.bar-fill.slow { background: #2a9d8f; }
.bar-time { font-size: 11px; font-weight: 700; margin-left: 6px; min-width: 70px; }
.legend { font-size: 10px; color: #666; margin-top: 6px; }

// Code not found

Notice how changing the cost factor shifts the attacker's timeline from hours to centuries. A fast hash like MD5 lets a modern GPU try billions of passwords per second; a properly tuned Argon2 configuration caps that at a few thousand per second — and each iteration also requires hundreds of megabytes of RAM that GPUs share across cores, killing parallelism.

What separates a toy password hasher from a real KDF?

The naive approach — hashing once. SHA-256 of a password runs in nanoseconds. A GPU cluster can try tens of billions of candidates per second. An eight-character password falls in minutes.

Key stretching (PBKDF2, 2000). RFC 2898 defines PBKDF2: apply HMAC-SHA-1 (or SHA-256) c times in a chain, where c is a configurable iteration count. With c = 600,000 (the current NIST recommendation), the attacker must do 600k hash evaluations per guess. This buys time, but iterations are cheap on a GPU — the function is still CPU-parallelizable.

Memory-hard functions (bcrypt, scrypt, Argon2). The key innovation is forcing the algorithm to allocate and use a large block of RAM during computation. GPUs have fast cores but limited per-core memory bandwidth. By requiring, say, 64 MB that must be read in a random-access pattern, the function becomes memory-bound — not compute-bound. Parallelizing across thousands of GPU cores does not help because each core needs its own 64 MB, and the GPU simply runs out of memory.

• bcrypt (1999, Niels Provos & David Mazières): the first widely deployed memory-hard password hash; still sound for passwords, but its 4 KB memory requirement is trivially small for modern hardware.
• scrypt (2009, Colin Percival): tunable memory and CPU cost; influenced Argon2.
• Argon2 (2015, Alex Biryukov et al.): winner of the Password Hashing Competition. Three variants: Argon2d (GPU-resistant), Argon2i (side-channel-resistant), Argon2id (hybrid, recommended). Parameters: memory m (in KB), time t (iterations), parallelism p. Security is proven under the random oracle model and the Ideal Cipher Model.

HKDF (HMAC-based Extract-and-Expand, RFC 5869) solves a different problem: deriving multiple independent keys from one high-entropy secret (e.g., a Diffie–Hellman shared secret). It is fast by design and not suitable for password storage — it has no cost parameter.

Status: well-established engineering, not an open mathematical question. The security of these constructions reduces to the collision resistance of the underlying hash and the assumed hardness of inverting pseudorandom functions. No practical breaks of Argon2id are known. The design space is active but the core primitives are standardized and widely deployed. Compare with the much deeper uncertainty in P vs NP or factoring — KDF security is a matter of engineering tuning, not unsolved mathematics.

Key derivation functions are the unglamorous workhorse of practical cryptography:

• Password storage: websites store Argon2id(password, salt, params) instead of the password itself. A breach leaks hashes that cost real money to crack. LinkedIn's 2012 breach used unsalted SHA-1 — 90% of hashes cracked in days. A properly configured Argon2id database would have taken centuries.
• TLS and Signal's Double Ratchet: HKDF derives independent encryption and MAC keys from a shared Diffie–Hellman secret after a handshake. Without key separation, a single key compromise could unravel the whole session.
• Disk encryption (LUKS, FileVault, BitLocker): the passphrase you type is never the AES key. PBKDF2 or Argon2 stretches it, so someone who steals your laptop cannot mount a fast offline attack.
• WPA2/WPA3 Wi-Fi: PBKDF2-HMAC-SHA1 with 4096 iterations derives the PMK from the Wi-Fi passphrase. WPA3 switches to SAE (Dragonfly), which integrates memory-hard elements.
• Cryptocurrency wallets: BIP-39 uses PBKDF2 to turn a 12- or 24-word seed phrase into a 512-bit master key for HD wallet derivation.
• SSH key passphrases: OpenSSH uses bcrypt KDF to protect private key files at rest.

The common thread: whenever a human-memorable secret must bootstrap cryptographic-grade key material, a KDF stands in the middle — slowing the attacker down just enough to make brute-force uneconomical. See also discrete logarithm and lattice-based cryptography for the hardness assumptions that protect the keys once derived.

A key derivation function encodes a simple but powerful idea: you cannot stop attackers from guessing passwords, but you can make each guess cost them dearly.

The evolution from a single SHA-256 to Argon2id tells the story of an arms race — hash once, then iterate, then add memory, then make the memory access pattern unpredictable — each step closing a loophole that faster hardware had opened.

The result is a function that verifies your login in 200 ms on a phone but turns an attacker's GPU farm into a multi-year project for a modestly complex password. That gap is not magic. It is careful parameter tuning, the physics of memory bandwidth, and the economics of electricity — all in service of one goal: making the cost of brute force exceed what any attacker is willing to pay.

If you want to explore the deeper assumptions behind the keys that KDFs produce, start with factoring and discrete logarithm — the hardness problems that asymmetric cryptography ultimately rests on.