Integrity: Pseudorandom Functions & Key Derivation

Pseudorandom Generators (PRG)

Definition: A PRG is a deterministic function that expands a short uniform random seed k ∈ {0,1}^λ into a longer pseudorandom output PRG(k) ∈ {0,1}^ℓ.

• Used in stream ciphers to generate keystreams.
• Security: output must be computationally indistinguishable from uniform random strings.

Pseudorandom Functions (PRF)

Definition: A PRF is a deterministic function F(k, x) that maps a key and input label x ∈ {0,1}^∗ to output F : {0,1}^λ × {0,1}^∗ → {0,1}^ℓ which is indistinguishable from random to adversaries without knowing k.

• Security: adversary cannot distinguish PRF from a truly random function, even after querying multiple inputs.
• Example usage: derive separate keys: k_enc = PRF(k, "enc"), k_mac = PRF(k, "mac")

Key Derivation Functions (KDF)

Definition: A KDF is similar to a PRF but allows non-uniform keys as long as they have high entropy: KDF(k, x) should still output pseudorandom-looking bits.

• Secure even when k comes from non-uniform but high entropy sources (e.g., elliptic curve secrets).
• Use case: derive usable keys from shared secrets (e.g., Diffie-Hellman outputs).

HMAC as PRG, PRF, and KDF

• PRG: HMACk(1) || HMACk(2) || ...
• PRF: HMACk(label)
• KDF: HMAClabel(k)
• HKDF: standardized construct that performs entropy extraction and expansion.

Password-Based Key Derivation (PBKDF2)

Definition: k = PBKDF2(F, p, s, c, ℓ)

• F: keyed hash (e.g., HMAC)
• p: password, s: salt
• c: iterations (slow down brute-force)
• ℓ: output length

Each output block Ti = Ui,1 ⊕ Ui,2 ⊕ ... ⊕ Ui,c with:

Ui,1 = F(p, s || i)
Ui,2 = F(p, Ui,1)
...
Ui,c = F(p, Ui,c−1)

PBKDF2 is used in WPA2, iOS, and password managers like LastPass.

Modern alternatives: bcrypt, scrypt, Argon2 (preferred for password hashing)

Things to Remember

• Goal of PRFs: Without the secret key, output must look random.
• PRGs: Expand short key into long pseudorandom output (stream ciphers)
• KDFs: Extract usable keys from high-entropy secrets
• HMAC: Serves as PRG/PRF/KDF foundation (HKDF improves it)
• Password hashing: Use PBKDF2, bcrypt, scrypt, or Argon2 with random salts and many iterations