Key Derivation

The preceding HMAC discussion has touched on the notion of a secret key, which determines the output of a keyed cryptographic primitive. Secret keys should ideally contain enough entropy to render brute-force attacks impractical. That typically calls for MAC keys of at least 256 bits and encryption keys of at least 128 bits. The ideal way to generate such keys is to use either a true random number generator (rarely available), or a cryptographically-strong pseudo-random number generator (based on CSP, for example). There are very common scenarios, however, where such randomly generated keys are either impractical or insufficient (and can cause either usability or security flaws). Key derivation functions (KDFs) are often used in these scenarios to derive one or more strong keys from a single, secret value.

Some cryptographic algorithms and protocols can have keys that are known to be weak, and thus should be avoided; KDFs can help avoid weak keys in such systems. Another common use of KDFs is to extract entropy from user-provided keys (which we often call passwords or passphrases) and derive the actual key via a deliberately slow computation process intended to thwart brute-force password guessing attacks. KDFs are also often used as part of a defense in depth security strategy. We will not cover the weak key avoidance uses of KDFs since you will not encounter any cryptographic algorithms with known weak keys in this book, but we will cover the other two common KDF scenarios next.

KDFs are often designed as a two-part extract-then-expand process. The “extract” part extracts as much entropy as possible from the input key and generates a fixed-length intermediate key. This intermediate key is supposed to be a short but cryptographically strong, uniformly distributed representation of the entropy gathered from the input key. The second, “expand” part of the process takes that intermediate key and expands it into a final key or keys based on specific objectives that each KDF is designed to achieve.

PBKDF2

Password-based key derivation function version 2 (PBKDF2, covered by RFC-2898) is a specific KDF designed for user-provided password cryptography. Password-based KDFs like PBKDF2 typically employ three defense mechanisms to generate a strong derived key:

• Condensing all available password entropy into a uniform intermediate key (the “extract” process).
• Salting the “extract” process to prevent scalability of brute-force attacks against multiple keys.
• Expanding the intermediate key via a slow computation process that’s very costly to make faster.

The slow computation of the third item will affect both legitimate users and brute-forcing attackers, but not in equal proportions. A legitimate user’s password check might be subject to one such slow computation on every check, which is likely to be fast enough not to affect usability, while the attacker would have to do this computation for every new password guess.

It is also prudent to assume that a resourceful, driven attacker will have access to much better hardware (likely custom-built and optimized for brute-forcing) than a legitimate installation. Modern cloud computing services can also be easily utilized to spin up large, powerful server farms dedicated to brute-force guessing, which can achieve the same results with large numbers of commodity hardware as fewer, more powerful, custom-built hardware resources.

The third mechanism would not have been necessary had passwords contained sufficient entropy to begin with. Unfortunately, high-entropy passwords are typically at odds with usability because they are hard for humans to come up with quickly and reliably. They are also hard to memorize, and difficult and time-consuming to type and re-type without typos.

Three password-based KDF algorithms are worth considering: PBKDF2, bcrypt, and scrypt.

Table 3: Comparison of PBKDF2, bcrypt, and scrypt

Table 3 is a quick, non-comprehensive comparison of these three password-based KDFs based on criteria that should be relevant from a .NET security engineering point of view. The last two points make PBKDF2 the preferred choice, since you want neither to trust an unsupported implementation nor to roll out your own.

The .NET-provided implementation of PBKDF2 is in the Rfc2898DeriveBytes class, which implements the abstract DeriveBytes base. You might also come across PasswordDeriveBytes, which is an implementation of the older PBKDF1 algorithm—do not use it. The PBKDF1 algorithm is weak, and Microsoft’s implementation of it is broken to boot.

One issue that immediately becomes apparent about Rfc2898DeriveBytes is that it implements the PBKDF2 algorithm with HMAC-SHA1 only (another example of Microsoft’s tightly coupled design). It is not even possible to hack Rfc2898DeriveBytes into operating on any other HMAC hash primitive because SHA-1 is hard-coded into the Rfc2898DeriveBytes implementation. One reasonable approach is to simply accept what is given and use Rfc2898DeriveBytes. This is a reasonable choice given the limiting circumstances. Another approach is to build a new, flexible PBKDF2 implementation by reusing as much of Microsoft’s implementation as possible, and only removing the hard-coded HMAC-SHA1 dependencies. You can find such PBKDF2 class implementation in the Inferno crypto library. It has been validated against published PBKDF2-HMAC-SHA1, PBKDF2-HMAC-SHA256, and PBKDF-HMAC-SHA512 test vectors.

A side benefit of being forced to do a re-implementation of PBKDF2 is choosing better defaults. Rfc2898DeriveBytes defaults to 1,000 iterations, which was considered adequate in 1999, but is too low for current brute-forcing technology. PBKDF2 defaults to 10,000 iterations, but you are encouraged to override that and use the maximum possible value that does not affect usability in your scenario.

HKDF and SP800_108

There are many scenarios where your source key material (SKM) already has sufficient entropy (SKM is a CSP-generated 16-byte random key, which already has 128 bits of entropy). These high-entropy SKM scenarios do not require entropy extraction, but they might still benefit from entropy condensation, where a fixed-length or variable-length high-entropy SKM is condensed into a fixed-length uniformly distributed representation. This condensation is useful even when the SKM has a vast amount of entropy in it because the entropy may not be evenly distributed among all SKM bits (some SKM sections capture more entropy than others).

The salting step is still relevant, but for different reasons. Guessing is no longer a concern (due to high-entropy SKM), but potential SKM reuse still is, so a known distinguisher is often used for extra entropy in the expansion step. The expansion step is relevant when multiple derived keys need to be generated from a single master key, and the evenly-distributed, fixed-length condensation might not be long enough to simply slice it into multiple, derived key lengths. Why would you ever need multiple derived keys to begin with? Why would a single key derived from a high-entropy SKM (which you are fortunate enough to have) not be sufficient?

For over seven years (.NET 2.0 to .NET 4.0), Microsoft believed that it was perfectly sufficient, based on their ASP.NET machineKey implementation. Microsoft used the same strong machineKey master key for various components, each using the same master key for encryption.

Serious security vulnerability was uncovered in September 2010 in the implementation of one of these components, which allowed an attacker to uncover the encryption key for that component. The affected ASP.NET component was not a critical one, and did not itself have a high exploitability or damage potential. However, because the same key was used by all other components, an attacker essentially obtained the key to the kingdom. This ASP.NET vulnerability was a serious blow to the security design of ASP.NET 4.0 and all earlier versions—serous enough to warrant a major security overhaul in ASP.NET 4.5, and a new ASP.NET crypto stack (covered in the following chapters), which is now based on multiple keys derived from a single high-entropy machineKey master key.

The Microsoft ASP.NET security team working on ASP.NET 4.5 realized that .NET had no KDF implementation designed for high-entropy SKM, and had the following to say on the .NET Web Development and Tools Blog:

“At this point we resigned ourselves to the fact that we'd have to implement the KDF in our own layer rather than calling any existing APIs. … We ended up choosing NIST SP800-108 [PDF link] due to the fact that it is designed to derive a new key from an existing high-entropy key rather than from a low-entropy password, and this behavior more closely aligns with our intended usage.”

Microsoft’s SP800-108 implementation is in a new SP800_108 class, which along with about 18 other tightly-coupled new security classes, is marked private internal in their System.Web.dll. It seems that we also have to resign ourselves to the fact that we have to implement our own KDF because Microsoft does not share its new toys.

Faced with such resignation, we can give some thought to whether SP800-108 is the best general-purpose high-entropy KDF to implement. SP800-108 is a decent choice, and also comes NIST-recommended. Microsoft had to react quickly, and their choice of SP800-108 shifted the algorithm risk to NIST. SP800-108 actually defines three KDF algorithms: a counter mode algorithm, a feedback mode algorithm, and a double-pipeline iteration algorithm. Microsoft’s SP800_108 class implements the counter mode algorithm because it is simple, fast, and allows O(1) derivation of any key subsection. However, there is another KDF algorithm, HMAC-based KDF (HKDF), which is arguably a better generic multi-purpose KDF than the SP800-108 algorithms. HKDF is proven to be secure, well-specified (RFC-5869), and includes distinct entropy-extraction and key-derivation steps. SP800_108 counter KDF is better suited for scenarios where performance is crucial and the entropy-extraction step is not necessary, while HKDF is a better and safer general-purpose KDF. The Inferno crypto library provides both HKDF and SP 800_108_Ctr implementations.

PBKDF2 combined with HKDF

It often makes sense to use both PBKDF2 and HKDF together to derive multiple keys. PBKDF2 excels at deriving a single master key from a low-entropy SKM, such as anything user provided. However, PBKDF2 is ill-suited for producing output beyond the length of its HMAC-wrapped hash function, because each additional PBKDF2 rotation is subject to the same slow computation process. For example, PBKDF2-SHA256 has a single-rotation output length of 32 bytes (256 bits). If you ask PBKDF2-SHA256 for 64 bytes of output (for example, if you need two 256-bit derived keys), or even if you ask it for 32+1=33 bytes, PBKDF2-SHA256 will take twice as long to run, because it will do two rotations instead of one.

You have already picked the PBKDF2 iteration count to be as high as possible without affecting usability of your system. The maxed-out iteration count was for one rotation only—making more than one PBKDF2 rotation would surely affect usability. You could switch to a longer hash function for PBKDF2 (essentially maxing out at 512 bits with SHA-512), but you would be avoiding the problem instead of solving it (nor would it scale beyond 2–4 keys, depending on their purpose).

A better approach is to use PBKDF2 to derive the master key, and then use HKDF (or SP800_108_Ctr) keyed with the PBKDF2-derived master key to efficiently generate any number of additional master-key-derived keys.

Salt

Cryptographic salt is an additional non-secret source of entropy used to prevent vulnerabilities due to reuse of SKM, either by the same source, or across multiple sources that happen to use the same SKM. Salt should always be used when you cannot guarantee the non-reuse of SKM (either deterministically or statistically). Note that the quality or entropy of SKM does not matter, only its potential reuse does; you should use salt even if you have a high-quality SKM with a potential for reuse.

The only requirement for salt is to be unique. If salt is not unique, then it can no longer act as a distinguisher when SKM is reused, and you fail. The uniqueness requirement can be implemented deterministically, for example, by using an atomically incrementing counter which you can guarantee to never repeat for all SKMs. Uniqueness can also be implemented statistically or statelessly by using a 128-bit, CSP-generated random value.

GUIDs are perfect candidates for salt because they are designed to provide uniqueness, not unpredictability. Deterministic implementations have the undesirable requirement of having to keep state, which adds more complexity and more opportunities for mistakes. We recommend that you use a GUID when you need a salt for two reasons: (1) GUID meets all salt requirements and the new GUID generation in the .NET Framework is impossible to screw up (we dare you); (2) Using GUIDs for salt clearly communicates the intent: uniqueness, not unpredictability. When we say GUID, we mean the 16-byte array representing a GUID, not GUID string form.

Salt is often confused with initialization vectors and misused; we’ll discuss the differences in the “Symmetric Encryption” chapter.

Client-side KDF

One obvious consequence of employing PBKDF2 and similar password-based KDF schemes to derive keys from low-entropy passwords is their high computational cost, measured in CPU or memory utilization. This cost can quickly become a limiting factor for server-side throughput, measured in requests per second.

One tempting idea is moving PBKDF2 computation from the server side to the client side. Let’s cover why this idea falls apart on closer inspection.

Typical client-side devices tend to have inferior CPU and memory resources compared to server-side infrastructure. Client-side software is often not even able to fully utilize the client-side resources that are available. Many modern browsers are stuck in 32-bit mode even when they are running in 64-bit environments and are unable to fully utilize available memory. Even when browsers are running in 64-bit mode, their computational capabilities are typically limited by their single-threaded JavaScript engines and are unable to fully utilize available CPUs. Mobile client devices are often primarily battery-powered, and are even further constrained in their resource capabilities. There is also client-side CPU throttling to preserve and extend battery life.

The crucial implication of client-side resource inferiority and unpredictability is that the number of client-side PBKDF2 rounds that can be tolerated with acceptable usability is typically a lot lower compared to server-side execution. Any substantial reduction in the number of PBKDF rounds would weaken PBKDF2 security and circumvent its intended purpose.

Another problem is that PBKDF2 is salted (if it’s not, then you’re not using it right). Salt values are available on the server side (which makes server-side PBKDF2 straightforward), but not on the client side. Sending salt values to the client side would not only introduce additional complexity, but would weaken security as well. While salt values do not have to be secret, they should not be blissfully disclosed to anyone who asks, either. An adversary could ask for a salt value of an administrator account and combine it with a list of common passwords to generate potential credentials and quickly mount an online attack. Blindly disclosing salt values is clearly not in our best interests.

Key separation

The key separation principle states that you should always use distinct keys for distinct algorithms and distinct modes of operation. Some violations of this principle can even lead to plaintext recovery without ever knowing the secret key. Fortunately, it is easy to adhere to the key separation principle by using a master-keyed HKDF or SP800_108_Ctr with a purpose-specific distinguisher to generate as many distinct keys as you require. In symmetric encryption scenarios, different encryption and decryption purposes as well as different operations (for example, encryption versus authentication) should use independent keys. In asymmetric encryption scenarios, encryption and signing should use independent key pairs.