6
$\begingroup$

XTS, as given by the below equation, is a mode of operation primarily targeting full-disk encryption scenarios.

By the way it works it also doubles the keylength although a meet-in-the-middle attack applies (by enumerating all the whitening values). However one only needs to calculate the whitening value once per sector.

So is there any way to break XTS or a double application thereof in less time and/or space than expected?

The expected time for standard XTS is time $2^{512}$ for 256-bit AES and $2^{513}$ time and $2^{512}$ space for double encryption.

Relation to the title:
XTS is the most well-known / used scheme for turning a 256-bit cipher into a 512-bit mode. It does this in such a way that each block requires merely one finite field multiplication and one encryption operation and every few blocks (e.g. 32+) require one additional encryption operation which means it should be a very "cheap" way of doing double encryption. So the question: Is this as good as it sounds?


The equation as documented by VeraCrypt:

$$C_1=E_{K_1}(P_1\oplus(E_{K_2}(n)\otimes\alpha^i))\oplus(E_{K_2}(n)\otimes\alpha^i)$$

with $C_1$ being the ciphertext, $P_1$ being the plaintext, $K_1$ and $K_2$ being the keys, $n$ being the sector index, $i$ being the block index within the sector, $\oplus$ denoting bitwise XOR, $\otimes$ denoting multiplication in the binary Field $GF(2)\bmod x^{128}+x^7+x^2+x+1$ and $(E_{K_2}(n)\otimes\alpha^i)$ being called "the whitening value".


Justification of the expected time / space values:
Single Encryption case:
This is essentially "single-key" XEX, providing 256-bit security combined with a 256-bit keyed permutation, one needs $2^{512}$ to find the correct whitening key and the correct permutation.
Double Encryption case:
Standard meet-in-the-middle attack: Enumerate all the possible intermediate values ($2^{512}$ time and space) and then try decrypting all the ciphertexts with all possible keys, looking for intermediate matches.

$\endgroup$
  • $\begingroup$ I think simply xor-ing the same value before and after the encryption operation has a similar effect. en.wikipedia.org/wiki/Xor-encrypt-xor $\endgroup$ – CodesInChaos Oct 31 '15 at 18:29
  • $\begingroup$ @CodesInChaos, but then you'd be limited to 384-bit keys maximum for AES. $\endgroup$ – SEJPM Nov 1 '15 at 14:02
4
$\begingroup$

So is there any way to break XTS or a double application thereof in less time and/or space than expected?

The expected time for standard XTS is time $2^{512}$ for 256-bit AES and $2^{513}$ time and $2^{512}$ space for double encryption.

Yes, there are better attacks than that.

With XTS a single sector is encrypted with a single $E_{K_2}(n)$ value, so the attacker can treat it as constant. It is only 128 bits, so a brute force attack can find both it and the AES key $K_1$ in about $2^{384}$ time. Once the attacker knows $K_1$, they can separately, given multiple sectors, attack the key $K_2$ in negligible time compared to the first step.

A meet-in-the-middle attack applies on double XTS as normal, in about $2^{385}$ time and $2^{384}$ space.

Note that with AES-128 the above would not be the case, since $K_1$ is the same size as the block, so a brute force takes $2^{256}$ time regardless of whether you are looking for the key or the encryption of the sector index.

There are of course other weaknesses that have to do with the fact that it is deterministic and lacks authentication. You can look at it as a sector sized cipher in ECB mode, if the attacker can see multiple ciphertexts for the same sectors. Any random string is a valid ciphertext, due to the absence of authentication or even padding.

XTS should not be used as general purpose encryption when IVs and authentication can be used.

$\endgroup$
  • $\begingroup$ Would a brute force of XTS AES-128 still be around $2^{256-1}$ time if the IV was known to be the sector number, as is used in LUKS? $\endgroup$ – Tom Hale Oct 28 '16 at 2:27
  • 2
    $\begingroup$ @TomHale yes. The IV is assumed to be public, but it gets encrypted using $K_2$ before use. $\endgroup$ – otus Oct 28 '16 at 4:16
  • $\begingroup$ And this is still the case in XTS-PLAIN-64? Wikipedia didn't seem to mention it. $\endgroup$ – Tom Hale Oct 28 '16 at 5:20
  • 2
    $\begingroup$ @TomHale, yes, the -plain64 part only means how the IV is generated, namely by taking the plain 64-bit sector position. XTS still passes the IV through the cipher normally. $\endgroup$ – otus Oct 28 '16 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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