7
$\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 tweak 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$
2
  • $\begingroup$ Information security has become so complex that end users can barely make informed choices about things that matter. Which disk encryption should I use? OK, let me get a PhD,,, I'll know in 6 years. I'll really know in 8. Perhaps. $\endgroup$
    – Patriot
    Commented Aug 4, 2019 at 1:36
  • 1
    $\begingroup$ @Patriot That's why it's useful to use an existing encryption program, e.g. LUKS for disk encryption. My question here is largely theoretical and, even if it was problematic in the sense that I mean, it would still not have any impact whatsoever on the practical security of XTS. $\endgroup$
    – forest
    Commented Aug 4, 2019 at 5:16

1 Answer 1

8
$\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) &= \left|\Pr[A_0(E_{k_2}) = 1] - \Pr[A_0(\pi) = 1]\right| \\ &= \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]\right|, \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) &= \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(U) = 1]\right| \\ &\leq \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]\right| \\ &\quad + \left|\Pr[A(f(\pi(i))) = 1] - \Pr[A(U) = 1]\right| \\ &= \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) &= \left|\Pr[A_1(E_{k_1}) = 1] - \Pr[A_1(\pi) = 1]\right| \\ &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right|, \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) &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(U) = 1]\right| \\ &\leq \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right| \\ &\quad + \left|\Pr[A(\alpha(\pi(\alpha(P)))) = 1] - \Pr[A(U) = 1]\right| \\ &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right| \\ &= \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$
3
  • 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$ Commented May 25, 2018 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$ Commented May 25, 2018 at 4:15
  • $\begingroup$ I would imagine that XTS mode using iSCSI (or NBD or anything similar) would have other problems as well, given that it would allow observing a single sector's contents changing over time (something XTS mode does not much like dealing with). $\endgroup$
    – forest
    Commented May 25, 2018 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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