Are PBKDF2 derived keys related if only the number of iterations is changed?

Question

I'd like to encrypt my disk with a password.

To generate a nice key from a password, I used PBKDF2, which applies a hash function $k$ times to a cleartext and outputs the final result.

When I modify that encrypted data, I decrypt it, modify it, and re-encrypt it.

When I re-encrypt, I plan to use a different key by increasing the number of PBKDF2 iterations during the key derivation (described soon), i.e., $k$ in the previous description, so that the encryption key differs from those in previous encryptions.

I derive the keys as follows.

$\mathsf{K}_\mathsf{derived} = \mathsf{PBKDF2}(\mathsf{password}, \mathsf{random\_salt})$, which constructs a key from the user-input password.

$\mathsf{K}_\mathsf{master} = \mathsf{HKDF\text{-}Extract}(\mathsf{K}_\mathsf{derived},\texttt{''no salt''})$, which derives a master key with an empty salt.

$\mathsf{K}_\mathsf{data} = \mathsf{HKDF\text{-}Expand}(\mathsf{K}_\mathsf{master}, \texttt{''AES-KEY''})$, which derives a symmetric key for AES encrypting the disk data. The derivation uses the salt $\texttt{''AES-KEY''}$.

where the PBKDF2 uses SHA-256, HKDF-HMAC function is HMAC-SHA256.

I set the parameter of PBKDF2 such that the following two conditions are satisfied:

1. The initial number of PBKDF2 iterations is large enough, such that the key derivation takes at least 1 second.

2. The number of PBKDF2 iterations is increased by at least 1 each time the message is re-encrypted.

---

My question is:

Are keys derived from the same password, but with different numbers of rounds in PBKDF2, computationally related?

---

If it matters, I use AES-CBC to encrypt, the data is not longer than 1 GB, and I'm only interested in keeping the data confidential.
P.S. I'm not serious about rolling my own crypto, I'm just looking to see if my hunch that this is safe is right or not.

Answer 1

Leave the iterations the same, they should be determined by the CPU time.

Instead provide a different random salt to PBKDF2 on each encryption, you can just concatenate the salt to the encrypted data, it does not need to be secret.

Of course for CBC you also need a new random IV for each encryption, it too can be concatenate to the encrypted.

You should also MAC the encrypted data so that you can determine ion the decryption succeeds, that is the correct key is used.

Answer 2

Do not count on PBKDF2 for different iteration counts $c$ to be unrelated; there are some exceptions to that. Rather, change a fixed-width portion of the salt (e.g. first byte) for different uses.

If for some legitimate reason (security upgrade) one must change the iteration count $c$, at least keep it even; or ban $c=1$, and always increase $c$ by more than $1$.

It is possible to relate different values of $\mathsf{PBKDF2}(\mathsf{Password}, \mathsf{Random\_salt},c_i,\mathsf{dkLen})$ with different $c_i$ at least when

• $\mathsf{Password}$ is known or guessed ($\mathsf{Random\_salt}$ is only required to remain unchanged when the iteration count changes);
• and $\mathsf{dkLen}$ is at least the width of the hash, or approaches it (allowing to guess the rest);
• and at least one of the following holds:
  • the smallest $c_i$ is 1
  • two $c_i$ are consecutive integers, and another one is higher.

Other than that, I do not see how we could make these correlations without guessing $\mathsf{Password}$ and $\mathsf{Random\_salt}$. I do not claim a proof.

---

Justification: restricting to $\mathsf{dkLen}$ equal to the width of the hash $\mathsf H$, $$\mathsf{PBKDF2\text{-}HMAC\text{-}H}(\text{Password}, \mathsf{Salt},c)=U_1\oplus U_2\oplus\ldots U_c$$ with $$\begin{align} U_1&=\mathsf{HMAC\text{-}H}(\mathsf{Password}, \mathsf{Salt}\mathbin\|\mathtt{00000001})\\ U_2&=\mathsf{HMAC\text{-}H}(\mathsf{Password}, U_1)\\ \cdots\\ U_c&=\mathsf{HMAC\text{-}H}(\mathsf{Password}, U_{c-1}) \end{align}$$

When one $c_i$ is $1$, the output is $U_1$ and if knowing $\mathsf{Password}$ it is easy to compute $U_j$ for any $j>0$, hence the value of PBKDF2 for any iteration count.

When two $c_i$ are $c$ and $c+1$, the XOR of the corresponding PBKDF2 is $U_{c+1}$ and if knowing $\mathsf{Password}$ it is easy to compute any $U_j$ for $j>c$, hence the value of PBKDF2 for any iteration count $c'\ge c$.

---

Fun fact: knowing only $\mathsf{PBKDF2\text{-}HMAC\text{-}SHA1}(\mathsf{Password}, \mathsf{Salt},c,20)$ for $c\in\{9999990,9999991,9999992\}$, testing a password guess requires a single $\mathsf{HMAC\text{-}SHA1}$; $\mathsf{Salt}$ is immaterial.

Morality: keeping iteration count $c$ even makes sense.