# Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it?

I'm referring the NIST document about PBKDF2, NIST Special Publication 800-132, Recommendation for Password-Based Key Derivation, Part 1: Storage Applications, Page 8 and 9, section 5.4 Using the Derived Master Key to Protect Data.

Here is Figure 3 from this document:

I am using the Option 1b: Generate Master Key (MK) first, and the get Data Protection Key(DPK) for file encryption.

1. If I have a lot (more than $2^{32}$) of files to be encrypted, each file is encrypted using newly generated DPK. Will it somehow cause the MK to be easily found? or easier to find?

2. The document does not specify which KDF to be used when generating DPK. Can I use back the PBKDF2 again?

3. Should I generate new random salt for each DPK? Or should I use something related (timestamp or file name) for the salt?

Reference: Secure Programming CookbookΤΜ for C and C++, Page 142, 4.11 Algorithmically Generating Symmetric Keys from One Base Secret

-

"If I have a lot (more than $2^{32}$) of files to be encrypted, each file is encrypted using newly generated DPK. Will it somehow cause the MK to be easily found? or easier to find?"

It's not going to make it harder. But no, as long as the KDF you're using lives up to its security claims, in practice it should not be feasible to construct the master key from the derived keys even if you have a lot of them.

If you want to be sure, check the standards and/or white papers defining your KDF and see if the security claims come with any restrictions like "assuming that at most $2^{64}$ bits of key material are derived from a single master key".

"The document does not specify which KDF to be used when generating DPK. Can I use back the PBKDF2 again?"

In practice, yes, you could use PBKDF2 also for the second-stage KDF. Since your input has already been key-stretched by the first application of PBKDF2, I'd suggest using an iteration count of 1 for the second stage to improve performance. In fact, I'd recommend doing this whenever you want to derive more than one hash output block's worth of key material using PBKDF2, since it reduces the attacker's work advantage.

To conform with NIST SP 800-132, your second-stage KDF needs to be "approved". Specifically, it needs to be (section 3.1):

"Approved: FIPS-approved and/or NIST-recommended. An algorithm or technique that is 1) specified in a FIPS or NIST Recommendation; or 2) adopted in a FIPS or NIST Recommendation; or 3) specified in a list of NIST-approved security functions."

There are several NIST Special Publications describing key derivation functions. SP 800-132 specifically references NIST SP 800-108, "Recommendation for Key Derivation Using Pseudorandom Functions", which specifies a set of approved methods for constructing a KDF from an approved pseudorandom function (HMAC or CMAC). Then there's also NIST SP 800-135 rev. 1, "Recommendation for Existing Application-Specific Key Derivation Functions" and NIST SP 800-56C, "Recommendation for Key Derivation through Extraction-then-Expansion". In particular, SP 800-56C specifically mentions HKDF (RFC 5869) as an instance of the general construction described therein, which I believe makes it approved, at least as long as it's instantiated with an approved hash function, such as SHA-2 or SHA-3.

As for PBKDF2, I'm not quite sure whether it should be counted as an "approved KDF" for this purpose or not. Certainly it has been approved by NIST for password-based key derivation, and one could (and I certainly would) argue that key-based key derivation is merely a subset of that, but I'm not sure if that argument is actually explicitly supported by any official NIST publication. In particular, I'm not sure if the use of PBKDF2 with an iteration count of 1 as a KBKDF is really sanctioned by any NIST publication.

In any case, HKDF isn't too different from PBKDF2 (they're both based on HMAC), and should be a simple and safe choice for a second-stage KDF.

"Should I generate new random salt for each DPK? Or should I use something related (timestamp or file name) for the salt?"

The important requirement for the salt is that it should be globally unique. A sufficiently long random string (at least 128 bits, preferably 256) is certainly one way to satisfy that requirement, but there are other options too.

For example, in the KDFs described in SP 800-108, the "salt" is, in effect, specified as the concatenation of two strings, Label and Context (separated by a null byte), defined as:

"3) Label – A string that identifies the purpose for the derived keying material, which is encoded as a binary string. The encoding method for the Label is defined in a larger context, for example, in the protocol that uses a KDF.

4) Context – A binary string containing the information related to the derived keying material. It may include identities of parties who are deriving and/or using the derived keying material and, optionally, a nonce known by the parties who derive the keys."

For your use case, the Label could include a number or file name identifying the DPK you want to derive, while Context could include a user identifier, and perhaps a fixed application identifier.

Similarly, HKDF takes both a "salt", used in the compression step, and an "info" string used in the expansion step, defined as:

"salt: optional salt value (a non-secret random value); if not provided, it is set to a string of HashLen zeros."

and

"info: optional context and application specific information (can be a zero-length string)"

The "salt" in the HKDF compression stage is basically the same as the salt for PBKDF2. Indeed, HKDF allows omitting the compression stage entirely if the input is already a cryptographically strong key, such as the output of PBKDF2, so one could basically replace the compression stage of HKDF with PBKDF2.

The "info" string, however, is part of the second (expansion) stage, and can, among other things, be used to allow several different keys to be derived from the same compressed master key (PRK in the HKDF terminology). For example, in your use case the "info" string could consist of a file number / name, a user ID and perhaps an application ID, plus whatever other information might be relevant. The important part is that it should be globally unique for each DPK.

-
That's a pretty complete answer Ilmari, +1 of course – Maarten Bodewes Jun 24 '13 at 19:01
Ya pretty complete answer. But I have a question about the 2nd part (salt) If I use random salt for each DPK for each file, I need to store it somewhere right? Either append infront of encrypted file, or maybe store in a database. But if I use Salt = Label+Context, it would be easier as I can retrieve it easily and I don't need to store it somewhere. – tcboy88 Jun 25 '13 at 0:42
@tcboy88: Yes, that is correct. Indeed, that's presumably the reason why SP 800-108 and RFC 5869 both suggest using a deterministic unique DPK identifier rather than a random salt for the expansion phase. Of course, if you can store a random salt for each file, there's no reason why you couldn't do both. – Ilmari Karonen Jun 25 '13 at 3:13
@IlmariKaronen thanks for the clear and throughout explanation! – tcboy88 Jun 25 '13 at 4:11
@IlmariKaronen: SHA-3 is not an approved hash function. But SHA-1 still is approved in this context. NIST SP 800-56C is a bit of a stretch, because it is intended to take shared secrets from NIST SP 800-56A/B as input. – user4982 Jan 16 '14 at 21:11