4
$\begingroup$

PBKDF2 should only be used to generate a larger output than the hash function it uses if the output is used in such a way that it has a flat keyspace. As far as I am aware, XTS does not have a flat keyspace, and the first half of the input is far more sensitive than the second half, which is only the tweak key. Am I correct in assuming that disk encryption utilities which use PBKDF-HMAC-SHA256 to derive a 512-bit key for a 256-bit cipher in XTS mode are in error?

If so, what can they do instead? Can they derive the cipher key and master key directly from the 256-bit output of the KDF, e.g. $K_1 = H(D \mathbin\| 0)$ and $K_2 = H(D \mathbin\| 1)$ for PBKDF2 digest $D$?

$\endgroup$
4
$\begingroup$

Background. PBKDF2 has a stupid design where generating two blocks of output costs the legitimate user twice as much as generating one block of output, without necessarily putting additional cost on the adversary's task of confirming a password guess. This is because each block of PBKDF2 output is generated by iterating the PRF on distinct initial inputs, which prevents sharing the work to generate each block: $$\operatorname{PBKDF2}(F, s, p, n, b) = \Bigl[\bigoplus_{i=1}^n {F_p}^i(s \mathbin\Vert 1)\Bigr] \mathbin\Vert \cdots \mathbin\Vert \Bigl[\bigoplus_{i=1}^n {F_p}^i(s \mathbin\Vert b)\Bigr].$$ Here ${F_p}^i$ is the $i$-fold iteration of the PRF $F$: ${F_p}^0(\sigma) = \sigma$, ${F_p}^{i+1}(\sigma) = {F_p}^i(F_p(\sigma))$.

It would have been more sensible to separate the computation into two stages like HKDF does (for a different but related purpose) with HKDF-Extract and HKDF-Expand: a costly computation to generate a master secret once, and then a collection of cheap computations to generate each block of output. But PBKDF2 did not do this.

In general, PBKDF2's stupid design hurts security: if the legitimate user can afford to compute $n$ iterations of the PRF, and needs $b$ blocks of output, the number of iterations that the legitimate user can spend on each block independently is at most $n/b$. If the adversary has a cheap way to confirm a password guess given any one of the blocks of output, e.g. in a password hash, then it is as if the legitimate user had a budget for only $n/b$ iterations and not $n$ iterations of the PRF.

Does this hurt in the case of XTS? XTS is the tweakable 128-bit block cipher defined on tweak $(i, j)$ in terms of the block cipher $E$ by $$\operatorname{XTS}_{k_1,k_2}(P, i, j) = E_{k_1}(P + T_{ij}) + T_{ij}, \quad\text{where}\quad T_{ij} = E_{k_2}(i) \cdot x^j.$$ Here arithmetic is in $\operatorname{GF}(2^{128})$ represented by the irreducible polynomial $x^{128} + x^7 + x^2 + x + 1$, with your favorite choice of identification of $\{0,1\}^{128}$ with $\operatorname{GF}(2^{128})$, e.g. little-endian. (Details of ciphertext stealing are omitted because we use sensible block sizes for everything.)

Suppose you use XTS to encrypt your laptop, and the adversary, a thief, has stolen your laptop. They have a candidate guess for a password, for which they have spent the cost to compute either $k_1$ or $k_2$, but not the other. How expensive is it to use this partial information to confirm a password guess, vs. spending the additional cost to compute the remaining $k_2$ or $k_1$ and confirm a password guess with full candidate key information? Assume that $P$, $i$, and $j$ are fixed and known to the adversary.

  1. The adversary has a candidate $k_1$ but not $k_2$. The question is whether the function $$\phi\colon k_2 \mapsto E_{k_1}(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j$$ is a pseudorandom generator. Define $f\colon \sigma \mapsto E_{k_1}(P + \sigma \cdot x^j) + \sigma \cdot x^j$, so that $\phi(k_2) = f(E_{k_2}(i))$. Let $A$ be a putative distinguisher for $\phi$. Define $A_0(\mathcal O) = A(f(\mathcal O(i)))$ as a putative PRP-distinguisher for $E$. Note that $$A(\phi(k_2)) = A(f(E_{k_2}(i))) = A_0(E_{k_2}),$$ so that \begin{align*} \operatorname{Adv}^{\operatorname{PRP}}_E(A_0) &= |\Pr[A_0(E_{k_2}) = 1] - \Pr[A_0(\pi) = 1]| \\ &= |\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]|, \end{align*} where $\pi$ is a uniform random permutation. Then, if $U$ is a uniform random 128-bit string, \begin{align*} \operatorname{Adv}^{\operatorname{PRG}}_\phi(A) &= |\Pr[A(\phi(k_2)) = 1] - \Pr[A(U) = 1]| \\ &\leq |\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]| \\ &\quad + |\Pr[A(f(\pi(i))) = 1] - \Pr[A(U) = 1]| \\ &= \operatorname{Adv}^{\operatorname{PRF}}_E(A_0) + \operatorname{Adv}^{\operatorname{PRG}}_f(A). \end{align*} Thus, it effectively reduces to the question of whether $f$ is a PRG. This is close to the question of whether $\sigma \mapsto \pi(\sigma) + \sigma$ is a PRG, if we model $E_{k_1}$ by a uniform random permutation $\pi$, which is essentially the Matyas–Meyer–Oseas construction as studied by Black, Rogaway, and Shrimpton in 2002. By a wing-waving argument, I assert that this seems like a reasonable model for most block ciphers (note related-key attacks are not relevant), and I conjecture the answer is no, the adversary can't effectively confirm a guess knowing only $k_1$ without computing $k_2$ unless they've broken $E$.

  2. The adversary has a candidate $k_2$, but not $k_1$. The question is whether $$\psi\colon k_1 \mapsto E_{k_1}(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j$$ is a pseudorandom generator. This straightforwardly reduces to the PRP-security of $E$. Given a PRG-distinguisher $A$, define the PRP-distinguisher \begin{align*} A_1(\mathcal O) &= A(\mathcal O(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j) \\ &= A(\alpha(\mathcal O(\alpha(P)))) \end{align*} where $\alpha\colon \sigma \mapsto \sigma + E_{k_2}(i)\cdot x^j$ is a permutation, so $A_1(E_{k_1}) = A(\psi(k_1))$, and \begin{align*} \operatorname{Adv}^{\operatorname{PRP}}_E(A_1) &= |\Pr[A_1(E_{k_1}) = 1] - \Pr[A_1(\pi) = 1]| \\ &= |\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]|, \end{align*} where $\pi$ is a uniform random permutation. Clearly since $\alpha$ is a permutation, $\alpha(\pi(\alpha(P)))$ has uniform distribution, so \begin{align*} \operatorname{Adv}^{\operatorname{PRG}}_\psi(A) &= |\Pr[A(\psi(k_1)) = 1] - \Pr[A(U) = 1]| \\ &\leq |\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]| \\ &\quad + |\Pr[A(\alpha(\pi(\alpha(P)))) = 1] - \Pr[A(U) = 1]| \\ &= |\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]| \\ &= \operatorname{Adv}^{\operatorname{PRP}}_E(A_1). \end{align*} The answer is no, the adversary cannot effectively confirm a guess knowing only $k_2$ and not $k_1$ unless they've broken $E$.

Why couldn't we just make $k_2$ public like an IV? If we did that, the following chosen-plaintext distinguisher would trivially break it: Submit $(P, i, j)$ and $(P + \delta, i, j')$ for the challenge, where $j \ne j'$ and $\delta = E_{k_2}(i) \cdot x^{j'} - E_{k_2}(i) \cdot x^j$, and test whether their ciphertexts differ by $\delta$.

While this justifies keeping $k_2$ secret in the cryptosystem in general, it's not clear that this power of the adversary is relevant to password-guessing for stolen laptop disk encryption: for every password they guess, the thief who stole your laptop would have to submit to you a chosen plaintext to encrypt in order for them to confirm that password. It's hard to imagine how this could happen unless you're willing to help me recover a large sum of money from a Nigerian prince I know.

But laptop disk encryption is not the only application of disk encryption. You might use iSCSI over the network, and the adversary might have compromised the iSCSI storage server without your knowledge, and may be able to control blocks of data written by the iSCSI client. In that case, the adversary may be able to submit a chosen plaintext derived from the value of $k_2$ for every password they guess, and use the client as an oracle to confirm the password at lower cost than evaluating PBKDF2 again to compute $k_1$.

Conclusion. In the case of laptop disk encryption with AES-XTS, the stupid design of PBKDF2 does not appear to hurt the way that it might generically. But that took a lot more work to prove (and there's some gaps: e.g., does it make a difference if the adversary has many blocks of output to confirm a guess?—rewrite $\phi$ and $\psi$ as PRFs of $(P, i, j)$). And it's possible I posed the wrong question, or made a mistake answering the questions I posed: this is, after all, a pseudonymous internet fowl talking feathery nonsense at you, not a bespectacled cryptographer writing in a respectable peer-reviewed journal. And there are imaginable applications of disk encryption for which this use of PBKDF2 does hurt security. It would have been safer to derive a master key with PBKDF2 and then derive subkeys from it with HKDF.

P.S. You should use scrypt or argon2, not PBKDF2. They make a much bigger difference than this quibbling! They also don't have this stupid design. That, or just generate your passwords uniformly at random from ${\geq}2^{128}$ possibilities.

$\endgroup$
  • $\begingroup$ I don't mean to imply that the security is reduced, but that this setup brings out the worst in XTS (due to this stupid design). It would be a fine design if XTS had a flat keyspace, but it doesn't. $\endgroup$ – forest May 25 '18 at 0:37
  • $\begingroup$ By flat keyspace, I mean the first 256 bits give away more information than the second 256 bits, because the second is only the tweak. The stupid design is only stupid when the attacker can optimize away extra computations (which is the case for e.g. password hashes, but not for, say, deriving 256 bits of key material for AES using SHA-1). If it takes me 10 seconds to derive the main key and the tweak, an attacker could run for only 5 seconds and derive the main key, but not the tweak. If it had a flat keyspace, then that 5 seconds would still leave them $2^{256}$ keyspace short. $\endgroup$ – forest May 25 '18 at 1:05
  • $\begingroup$ Yes, you understood correctly. Since it's common for disk encryption utilities to do this, the adversaries do have many blocks of output, sometimes with known plaintext/ciphertext pairs. Much of this math is beyond me, so I cannot "rewrite $\phi$ and $\psi$ as PRFs of $(P, i, j)$)". I understand from this that knowledge of one of $k_1$ or $k_2$ is not problematic for only a single block, but I cannot extrapolate from this post exactly how problematic it is when an attacker has a large number of blocks. $\endgroup$ – forest May 25 '18 at 3:24
  • 1
    $\begingroup$ @forest The gist is that it accidentally works out that the stupid design of PBKDF2 does not hurt security in this case. What if you generated three blocks of output instead of two with PBKDF2, and stashed the third one in the clear as a way to let the legitimate user verify they typed in their password correctly before trying to read a randomized disk decrypted under the wrong key? Then you do hurt security. Single-block PBKDF2 followed by HMAC would be generally safer. scrypt and argon2 are better both because they're memory-hard and because they avoid this stupid design. $\endgroup$ – Squeamish Ossifrage May 25 '18 at 4:00
  • 1
    $\begingroup$ @forest Correction: The gist is that it accidentally works out that the stupid design of PBKDF2 does not hurt security in the case of laptop disk encryption against a thief who steals the laptop. But an iSCSI server is a different story. I updated the question. $\endgroup$ – Squeamish Ossifrage May 25 '18 at 4:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.