PBKDF2 Key Stretching: Beyond the Basics

Key stretching is the process of deliberately slowing down password-based key derivation to make brute-force attacks prohibitively expensive.

Here’s a demonstration of how a password gets turned into a cryptographic key using PBKDF2, a common key stretching algorithm.

Imagine you have a password: SuperSecretPassword123. You want to use this to generate a cryptographic key for, say, AES encryption. A direct hash of the password (like SHA-256) would be too fast for an attacker to try many variations. Key stretching adds computational work.

PBKDF2, or "Password-Based Key Derivation Function 2," works by repeatedly applying a pseudorandom function (PRF), typically HMAC-SHA256, to the password. It takes several inputs:

• Password: The secret string (SuperSecretPassword123).
• Salt: A random value unique to each password, preventing pre-computation attacks (rainbow tables). Let’s use a 16-byte salt: a1b2c3d4e5f67890.
• Iteration Count: A large number specifying how many times the PRF is applied. This is the core of the "stretching." Let’s use 100000.
• Desired Key Length: The length of the final cryptographic key. Let’s aim for a 32-byte key for AES-256.

The process involves deriving multiple blocks of the final key. For our 32-byte key, we’ll need two 16-byte blocks.

Block 1 Calculation:

1. Initial Hashing: The first step is to compute HMAC-SHA256(salt, password). This produces a 32-byte output.
   • U_1 = HMAC-SHA256(a1b2c3d4e5f67890, SuperSecretPassword123)
2. Subsequent Iterations: Then, for i from 2 up to the iteration count (100000), we compute:
   • U_i = HMAC-SHA256(U_{i-1}, password)
3. XORing: Finally, all the U_i values are XORed together to produce the first block of the derived key.
   • DK_1 = U_1 XOR U_2 XOR U_3 XOR ... XOR U_100000

Block 2 Calculation:

This follows the same logic, but with an added element to ensure the blocks are different. A " 1" is appended to the salt for the first block, " 2" for the second, and so on.

1. Initial Hashing:
   • U_1 = HMAC-SHA256(a1b2c3d4e5f67890 || 0x00000001, SuperSecretPassword123) (Note the appended 0x00000001 to the salt).
2. Subsequent Iterations:
   • U_i = HMAC-SHA256(U_{i-1}, password)
3. XORing:
   • DK_2 = U_1 XOR U_2 XOR U_3 XOR ... XOR U_100000

The final derived key is the concatenation of DK_1 and DK_2.

The magic here is the iteration count. Each iteration involves a cryptographic hash operation. By performing 100,000 (or more) of these, even on a fast CPU, it takes a significant amount of time to derive a single key. An attacker trying to brute-force a password would have to repeat this entire 100,000-iteration process for every single password guess. This makes offline attacks, where the attacker has a copy of the hashed passwords, infeasible for reasonably strong passwords and high iteration counts.

The salt is critical. Without it, if two users had the same password, they would derive the same key, and an attacker could pre-compute hashes for common passwords and quickly find matches. The salt ensures that even identical passwords result in unique derived keys.

The true power of key stretching, and PBKDF2 in particular, is that it turns a computationally cheap operation (a single hash) into a computationally expensive one, directly proportional to the iteration count. This cost is borne by the server performing the derivation and, more importantly, by any attacker attempting to crack it. The "slow" nature is precisely the security feature.

The next step in secure password handling is understanding how to choose appropriate iteration counts and salts, and how to store these derived keys securely.