Read the original article here.

---

Okay, here is the detailed educational resource on Key Stretching, structured and enhanced for the "The Forbidden Code: Underground Programming Techniques They Won’t Teach You in School" context.

---

Key Stretching: Fortifying Weak Secrets Against the Brute Force

In the shadowy world of digital security, where attackers tirelessly probe for weaknesses, one fundamental vulnerability persists: humans are terrible at picking secrets. Passwords and passphrases, the digital keys to our kingdoms, are often short, predictable, or easily guessed. Standard programming courses might touch upon hashing passwords, but they often gloss over a critical technique used in the trenches to make even weak secrets significantly more resilient: Key Stretching.

This isn't just academic theory; it's a vital defensive programming technique. When you build systems that rely on user-provided secrets, simply hashing them once and storing the hash is a rookie mistake. The real battle begins when an attacker gets hold of those hashes. Key stretching is your first line of defense in making their life miserable.

What is Key Stretching?

At its core, key stretching is a process designed to take a relatively weak input (like a human-chosen password or passphrase) and computationally transform it into a much stronger, but still deterministic, output key. The critical element isn't changing the inherent randomness of the original password (you can't add entropy that wasn't there), but dramatically increasing the computational cost required to test a single candidate password.

Brute-Force Attack: An attack method that involves systematically trying every possible password or key until the correct one is found. For a weak or short password, this can be surprisingly fast if the attacker has sufficient computing power.

Imagine an attacker with a list of common passwords (a dictionary attack) or simply trying combinations sequentially. Without key stretching, checking if a guessed password is correct might involve a single, fast cryptographic operation (like one hash). Key stretching forces the attacker to perform a vastly larger number of operations for each and every guess they make.

Why is Key Stretching Necessary?

Standard hashing (like a single SHA-256 hash) is designed to be fast. This is usually desirable for data integrity checks or verifying file downloads. However, speed is the enemy when hashing passwords. A fast hash allows an attacker to check billions or trillions of potential passwords per second using specialized hardware like GPUs or FPGAs.

Key stretching deliberately introduces a significant delay – typically hundreds of milliseconds or even a second – into the process of verifying a password or deriving a key from it. This delay is acceptable for a legitimate user who only logs in occasionally, but it imposes a massive, potentially prohibitive, workload on an attacker trying millions or billions of guesses.

The Core Process: How it Works

Key stretching algorithms operate by taking the input secret (password) and feeding it into a computationally intensive process, often involving repeated application of a cryptographic function like a hash or cipher. This process generates an enhanced key or derived key.

The key principle is that the process must have no known shortcut. The only way to get the enhanced key from the original password is to perform the entire stretching algorithm. This compels any attacker trying to guess the original password to also perform the full stretching algorithm for each guess.

Here's a simplified view:

1. Input: A relatively weak secret (the password/passphrase).
2. Algorithm: A predefined, public algorithm (e.g., PBKDF2, scrypt, Argon2).
3. Iteration/Work Factor: A configurable parameter determining how much work the algorithm does (e.g., the number of hash rounds). This is the "stretching" part.
4. Output: The enhanced key or derived key, which is used for subsequent operations (like verifying the password against a stored value or deriving an encryption key).

Enhanced Key (Derived Key): The output of a key stretching process. This key is derived deterministically from the input password and is designed to be computationally expensive to generate for a given input, thereby hindering brute-force attacks on the original password.

The attacker is left with two main attack vectors:

1. Attack the Enhanced Key Space: Try to guess the enhanced key directly. This is typically infeasible because the enhanced key is designed to be long and appear random (mimicking a much longer, unpredictable key space), provided the stretching algorithm is cryptographically sound.
2. Attack the Original Password Space: Guess common or likely passwords and run each guess through the key stretching algorithm to see if the resulting enhanced key matches the target. This is the primary target thwarted by key stretching, as the cost per guess is dramatically increased.

The genius of key stretching is the asymmetry of cost. A legitimate user computes the stretched key once during login. An attacker trying a million passwords must compute the stretched key a million times. If the stretching takes 1 second, the attacker is limited to 1 guess per second per core, a far cry from billions of hashes per second.

Key Stretching and Entropy: A Critical Distinction

It's vital to understand that key stretching does not magically add entropy to your weak password.

Entropy: In cryptography, entropy refers to the measure of unpredictability or randomness in a data source or secret. Higher entropy means a secret is harder to guess randomly. It's often measured in bits (e.g., a 128-bit key from a truly random source has 128 bits of entropy).

If your password is "password123" (which has very low entropy), running it through key stretching will always produce the same enhanced key with the same number of possible input values (the small set of likely/simple passwords). The enhanced key is deterministic. Key stretching simply makes the process of finding that low-entropy password (and its corresponding enhanced key) much, much harder for an attacker trying to guess. It increases the work factor but not the information content or fundamental randomness of the original secret.

Methods and Algorithms

There are several ways to implement key stretching, typically falling into two categories:

1. Iterated Hashing/Ciphering: Repeatedly applying a standard cryptographic hash function or block cipher.

   • Example: Applying SHA-256 function to the output of the previous hash, 10,000 times.
   • Prominent Example: PBKDF2 (Password-Based Key Derivation Function 2). This algorithm is widely used and often involves applying a pseudorandom function (commonly HMAC with a cryptographic hash like SHA-256) repeatedly.
   • Benefit: Relatively simple to implement using standard cryptographic primitives.
   • Vulnerability: Highly susceptible to hardware acceleration (GPUs, FPGAs) which excel at parallelizing simple, repetitive computations like hashing.

2. Memory-Hard Functions: Cryptographic functions designed to require significant amounts of memory and access that memory in patterns that defeat caching.

   • Why Memory-Hard? While compute power (CPU cycles) has become incredibly cheap and parallelizable (GPUs), large amounts of low-latency memory remain relatively expensive. By making the stretching process memory-intensive, attackers are forced to invest heavily in expensive memory systems rather than just throwing cheap, fast computational cores at the problem. This disproportionately increases their cost compared to a standard user's system.
   • Prominent Examples:
     • scrypt: One of the early memory-hard algorithms, designed explicitly to resist hardware attacks by requiring large amounts of RAM.
     • Argon2: The winner of the 2015 Password Hashing Competition, designed to be resistant to both CPU and GPU attacks, with various modes offering trade-offs between CPU intensity, memory intensity, and parallelism.

Choosing the right algorithm and work factor (iteration count, memory cost) is a critical decision in system design, balancing security against acceptable performance for legitimate users.

Strength and Performance Considerations

The strength added by key stretching is directly related to the computational work required per guess. If an attacker can perform X hashes per second without stretching, and your stretching algorithm requires N hashes per guess, the attacker is limited to X/N guesses per second.

For example, if a system uses 10,000 iterations of a hash function, and an attacker could normally do 10 billion hashes/second (e.g., with a high-end GPU), they are limited to 10 billion / 10,000 = 1 million guesses per second. While still fast, this is dramatically slower than the original rate.

The effect of key stretching is often described in terms of "additional bits of strength." If a process increases the work factor by a factor of F, it adds approximately log2(F) bits of strength against a brute-force attacker using comparable hardware. So, a factor of 65,536 (2^16) adds about 16 bits.

Practical Considerations:

• Moore's Law: As computers get faster, the number of iterations required to maintain the same level of security increases. The iteration count should ideally be increased over time, though this can be challenging for systems needing deterministic output from a password (e.g., deriving an encryption key). A common strategy is to pick a high number of iterations based on anticipated hardware advancements over the system's expected lifespan.
• Hardware Attacks: As discussed, simple iteration is vulnerable to specialized hardware. This is why memory-hard functions are crucial for modern systems. An attacker with custom silicon (ASICs) or massive GPU arrays can still significantly outperform general-purpose CPUs on CPU-bound functions. Memory-hard functions aim to neutralize this advantage.
• User Experience: The stretching time should be noticeable but acceptable for the user (e.g., 300ms to 1 second). This time directly translates to the attacker's cost per guess.

Salting: The Essential Companion

Key stretching is powerful, but it's typically insufficient on its own if you're storing password hashes. It must be combined with salting.

Salt: A unique, random string of data added to a password before it is hashed or put through a key stretching function. The salt is stored alongside the resulting hash/enhanced key.

Without a salt, two users with the same password would have the same enhanced key. An attacker could compute the enhanced key for common passwords once and build a "rainbow table" (a precomputed list of hashes/enhanced keys) to quickly look up the passwords for many users simultaneously.

Time-Memory Tradeoff (Rainbow Tables): An attack strategy where an attacker invests significant time upfront (precomputing hashes/enhanced keys for common passwords) to save time later during the attack (simply looking up a target hash in the precomputed table instead of recalculating it). Key stretching alone can still be vulnerable to this if the output is the same for the same password across users.

With a unique salt for each user:

1. The system generates a new, random salt for each user when they set their password.
2. The password and the unique salt are fed into the key stretching function.
3. The resulting enhanced key and the salt are stored (the original password is never stored).
4. To verify a login attempt, the system retrieves the stored salt for that user, feeds the entered password and the salt into the key stretching function, and compares the result to the stored enhanced key.

Because each user has a unique salt, the key stretching function produces a different enhanced key even for the same password. This means an attacker cannot use rainbow tables or precompute results that work for multiple users. They must perform the full, costly key stretching operation for each guess for each specific user they target. Salting defeats the time-memory tradeoff attack against password databases.

A Glimpse into History

The concept of making password verification intentionally slow isn't new.

• Early Unix crypt(3) (1978): Robert Morris's original system for encrypting Unix passwords used a modified DES algorithm and an iteration count of 25, combined with a 12-bit salt. While groundbreaking for its time (PDP-11 era), 25 iterations is trivial for modern hardware, and the 12-bit salt is too small by today's standards. The limited password length was also a severe constraint.
• Evolution: As computing power grew, the need for more iterations and stronger underlying algorithms became clear. PBKDF2 emerged as a standard (part of PKCS #5), leveraging modern cryptographic hashes and allowing for configurable, much higher iteration counts.
• Hardware Arms Race: The rise of GPUs and FPGAs capable of massively parallelizing simple hashes led to the development of memory-hard functions like scrypt (2009) and Argon2 (2015), which specifically aim to raise the hardware cost for attackers. The Password Hashing Competition was a direct response by the security community to find better algorithms resistant to these modern threats.

Where You'll Find Key Stretching (In the Wild)

This isn't theoretical stuff; key stretching is employed in many critical systems you interact with daily:

• Password Storage: Secure systems storing password hashes in databases use algorithms like PBKDF2, bcrypt, scrypt, or Argon2 with high work factors and per-user salts.
• Disk Encryption: Software like VeraCrypt (successor to TrueCrypt), BitLocker, and file systems with encryption (like LUKS on Linux) derive their master encryption keys from user passphrases using key stretching algorithms.
• Password Managers: Utilities like KeePassXC use strong algorithms like Argon2 to derive the key that encrypts your password database from your master password.
• File Archivers: Tools like 7-Zip use key stretching when encrypting archives with a password.
• Secure Communication Protocols: WPA and WPA2 (Wi-Fi security protocols) in Personal mode use PBKDF2 to derive encryption keys from the network passphrase.
• Email/File Encryption: PGP and GPG software utilize key stretching to derive encryption keys from user passphrases.

Relationship to Key Derivation Functions (KDFs)

Key stretching is often a core component of a larger process called a Key Derivation Function (KDF).

Key Derivation Function (KDF): A cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, password, or passphrase using a pseudorandom function. KDFs are often used to turn passwords (weak secrets) into cryptographic keys (strong secrets).

KDFs take an input secret (like a password) and potentially other parameters (like a salt and a work factor) and produce a fixed-length output that can be used as a cryptographic key for encryption, authentication, etc. Key stretching is the mechanism within many KDFs that makes this derivation process computationally expensive, thereby securing the original, potentially weak, input secret against brute force. PBKDF2, bcrypt, scrypt, and Argon2 are all modern KDFs that heavily rely on key stretching.

Conclusion

Key stretching is an indispensable technique in the arsenal of anyone building secure systems. It acknowledges the reality of weak human passwords and provides a practical, computationally enforced barrier against brute-force attacks. Simply hashing a password once is insufficient; you must make the hashing process expensive.

By understanding why iteration counts matter, why memory-hardness is a defense against specialized hardware, and the crucial role of salting, you move beyond basic concepts and into the practical, hard-won knowledge of defending systems in the real world. This isn't just good practice; it's essential knowledge they might not dedicate enough time to in a standard curriculum, making it a prime example of a technique from "The Forbidden Code." Master it, and you'll build significantly more robust defenses for user secrets.