Does key derivation with known parameters add any security?

Question

First up: this is a question about a concept that I try to wrap my head around; it is not about the specific implementation. Anyway…

I have the following scenario (simplified to show the problem I have with the concept):

1. I have a symmetric master-key, lets assume the strongest algorithm out there at the time you read this: $KM$.
2. I have a bunch of PDF files that have to be encrypted with $KM$.
3. As a security feature it is defined that, for every PDF, $KM$ and the $filename$ are shoved into a publicly known function $derive(KM, filename)$ to get a file-specific key $KF$.
4. I now proceed to encrypt all the documents with these keys.

Does this add to security or does it just pose a dangerous risk?

The one pro argument I get to hear:

Not all files are encrypted with the same key - it is harder to guess the key.

1. So I need to solve $derive(KM, filename)$.
2. I have the $filename$ and know $derive$. Which leaves me with one equation with one variable – solvable for $KM$.

The only catch I see is: it will take a little longer to brute force a key, as I have to solve the equation for every key I try. If I brute-force offline, this seems more like a minor inconvenience but not a problem – I will only have to solve for one PDF though, as I can get knowledge $KM$. So, as opposed to forward secrecy, cracking one PDF will crack them all.

The big problem I see:

Losing the $filename$, loses the file. If all chains break, all backups fail and the $filename$ is changed, I cannot for the life of me decrypt the files. I would have to brute-force the master-key, which gracefully I'ld only have to do with one file as described in the previous paragraph.

Additions:

As Maarten Bodewes pointed out in a comment at Stack Overflow question (before this question was moved here):

If a Password Based KDF is used then it is possible to adjust to load factor for derivation. Furthermore, if you would use ${KM}$ directly you would also need to derive or store an Initialization Vector. If the size of the files is not an issue, you could however make this scheme more secure by using hybrid encryption using a public/private key pair, and possibly a MAC. In that case you may not need a KDF (but you would need a secure random generator).

^{(emphasis mine)}

An IV is still generated and stored in the first X bytes of the encrypted document. This does not, however effect the overall concept I think, since he wrote:

If the size of the files is not an issue, you could however make this scheme more secure by using hybrid encryption using a public/private key pair

The whole encryption takes place in a HSM that, for the sake of this question, protects the master-key 100% - you cannot in any way get the master-key in any way other than brute-forcing. But these remarks are not what i was aiming to get as an answer.

---

The process is as follows:

1. User sends a file, encrypted with a ephemeralKey, wrapped with a publicKey only the HSM knows the privateKey for.
2. The HSM decrypts the file, genrates $KD$ using the $filename$ and $KM$ only known to the HSM, encrypts the file and stored the file on a harddrive.
3. When a user asks for a file, the HSM will generate a ephemeralKey, generate $KD$ from the filename and $KM$, decrypt the file, encrypt it with the ephemeral Key, wrapt the key for the user and send the wrapped key and the file to the user. - $KD$ is never used by anyone but the HSM.

As an admin one does have direct access to the harddrive where the files are stored - does the derivation significantly slow me down if i offline bruteforce a file and, using this $KD$ to solve the derivation function for $KM$?

So:

• PRO: brute-forcing will take marginally longer.
• CON: no real gain like forward secrecy, additional risk.

Wrapping it up…

I generate a derived key for every document via$KD = KDF * KM * filename$ where $KDF$ and $filename$ are known to the public. If I brute-force a document and get the correct $KD$, I know 3 out of 4 variables and therefore know $KM$. As a result, I’m able to derive every $KD$.

This makes me ask: does the whole scheme actually add any security at all?

Answer 1

Yes, key derivation with known parameters can add to security.

For a start, in the scenario of the question (understood as a real-world scenario, with PDF encryption used in step 4), when key derivation is used, you can hand one encrypted PDF document and its derived key to a person, and that won't enable her to decipher other enciphered documents; this exclusion is often desirable. Also, notice that even if that person changes the filename, she is still able to read the file.

Contrary to what's assumed in the question, knowledge of $derive(KM,filename)$ and $filename$, even for several different $filename$, should NOT enable to recover $KM$ or otherwise compute $derive(KM,filename)$ for arbitrary $filename$. For a good derivation function (that is, such that for each value of $KM$, the transformation $filename\to KF$ appears to be an arbitrary random function), that will be possible only if $KM$ is weak (guessable). Even if that was, $derive$ might/should be an intentionally slow function (a Key stretching aka Password-based Key Derivation Function), which will make brute-forcing $KM$ challenging.

Another common use of key derivation with known parameters is when one manufactures many devices embedding a secret and an identifier/serial number. It is standard and sound practice to derive the secret from a secure master key and the identifier. This practice (called diversification in the Smart Card industry) insures that one can not deduce the secret of one device by extracting the secret(s) from other device(s).

---

We are now told that "$KD$ is just for storing the files on the server". In that usage, key derivation does not help, assuming a secure encryption scheme is used and $KM$ is strong (wide/random enough). Rationale: since "No user will ever get $KD$", the derived keys exists only in the HSM; since the encryption scheme is secure, using that scheme with either $KM$ or $KD$ is equally secure and can't result in key leak; there is no reason to fear the leak of a key enciphering a file other than by leak of $KM$, with or without derivation, thus no incentive for key derivation. In fact, the complexity of the derivation increase the risk of implementation error leading to vulnerability.

On the other hand, key derivation might help to stay within the limit within which the encryption scheme is secure. For example, if the file encryption scheme is TDES in CBC mode with random IV, this becomes (even so slightly) insecure after about 30GB are encrypted using the same key, because of likely ciphertext block collision; key derivation will help ensure that this does not occur if 100 files each 1GB are encrypted. As another example, perhaps the HSM is secure against DPA with 1GB encrypted with a given key, but insecure after 100GB.

---

To sum up, proper key derivation helps when any of the following applies:

• a derived key can leak (key derivation limits the damage to the file which key leaked);
• the master key is weak, and the derivation function is made purposely slow (derivation significantly increases cost of brute force search);
• the encryption scheme or its implementation has weakness when enciphering a lot of data (the multiple derived keys will help stay within safe limits, by reducing the amount of data enciphered with the same key).

Answer 2

I generate a derived key for every document via KD=KDF∗KM∗filename where KDF and filename are known to the public. If I brute-force a document and get the correct KD, I know 3 out of 4 variables and therefore know KM. As a result, I’m able to derive every KD.

The main problem here is, that you assume the existence of a function, which can calculate the master key from the derived key.

This is wrong. A KDF is a oneway function (and it usually includes hashing). and one of the most important features is that you can not compute backwards from the derived key.

So yes, the breaking of a single file does not expose the master key.

One adaption you could do is instead of using the filename as salt (well, it is kinda the same concept as salting passwords), you can just add a salt, which is not changed if the filename changes, and save it along with the file (e.g. in the meta information). It just needs some data, which is accessible both with encrypted and unencrypted content.