Key Derivation

How do we derive many keys from one key?

This comes up all the time in practice. Typical scenario: A single source key (SK) is sampled from - hardward RNG, a key exchange protocol.

We need many keys to secure a session - unidirectional keys - multiple keys for nonce based CBC.

So we want to generate many keys from this one source key.

We do so using a key derivation function (KDF).

When the source key is uniform we can do this as follows:

Define a PRF with key space \(K\) and outputs \(\{0,1\}^n\).

The Key derivation function will be:

\[KDF(SK,CTX,L) := F \left( SK, (CTX || 0) \right) || F \left( SK, (CTX || 1) \right) || \dots || F \left( SK, (CTX || L) \right)\]

Where \(CTX\) is a context, and \(L\) is the length of the key string you want at the end.

The \(CTX\) is a unique string that identifies the application.

But the source key is often not uniform. Key exchange protocol may be uniform only in some subset of \(K\). Hardware RNG may be biased.

So we use the extract-then-expand paradigm. Here we extract a pseudo random key from source key SK.

We want a distribution that is indistinguishable from random.

The standard way of doing this is called HKDF a KDF from HMAC

We extract using \(k \leftarrow HMAC(salt, SK)\)

Then expand using HMAC as a PRF with key \(k\).

Password-Based KDF (PBKDF)

How do we derive keys from passwords?

Passwords have low entropy, estimated avg. 20 bits of entropy.

As a result we can’t generate using HKDF. Derived keys will be vulnerable to dictionary attacks.

PBKDF defenses: salt and a slow hash function.

Standard approach: PKCS#5 (PBKDF1) - implemented in most crypto libraries. Don’t implement yourself!

\[H^{( c)}(pwd||salt)\]

IE concat password to salt and iterate hash function c times. c could be 1000, or a million…

Makes the guessing problem as hard as possible.

This won’t too much time for the user on modern processors (like a tenth of a second).

Attacker can try dictionary passwords, but now each attempt takes a while, so we slow the dictionary attack.