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$
2
  • $\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$ Oct 31, 2015 at 18:29
  • $\begingroup$ @CodesInChaos, but then you'd be limited to 384-bit keys maximum for AES. $\endgroup$
    – SEJPM
    Nov 1, 2015 at 14:02

1 Answer 1

5
$\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$
5
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 12:18
  • $\begingroup$ @otus If the key size is not a multiple of block size, does this attack still applies to it? In the Linux kernel there is a cipher called "Anubis" that has 128-bit block size and 320-bit key size, the XTS mode when applied to it make the encipherment has 640-bit key size. $\endgroup$ Jan 11, 2022 at 0:58

Your Answer

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

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