37
$\begingroup$

I have some problems in understanding the "advantage" of AES-XTS compared to CBC with diffuser.

I read something about FileVault, in this paper they mention the two modes of operations XTS and CBC (with diffuser) and the advantages of XTS.

Both modes encrypt data units almost the same way. For CBC, the sector number is somehow used to build the IV, for XTS, there is a "tweak value", which also includes (somehow) the block offset, so each data block can be encrypted independently (makes sense when encrypting harddrives/partitions). I cannot really see the advantage of XTS.

Now, they write the following about XTS:

There are several advantages over alternatives such as AES in CBC: there is no requirement for an initialization vector (the tweak key can be derived from the block number); each block is encrypted differently (since the tweak value will be different); and unlike AES-CBC, AES-XTS prevents an attacker from changing one specific bit in a data unit by xor-ing each AES input with a different shifted version of the encrypted tweak.

Maybe they just compare XTS against CBC (without diffuser)... if so, does anybody know any advantage of XTS?

And can somebody explain the second advantage: "AES-XTS prevents an attacker from changing one specific bit in a data unit by xor-ing each AES input with a different shifted version of the encrypted tweak."?

$\endgroup$
3
  • 1
    $\begingroup$ What's "diffuser"? "the sector number is somehow" how? You didn't describe the scheme clearly. If the algorithm is predictable, this leads to weaknesses, and an unpredictable algorithm is expensive. $\endgroup$ Commented Dec 5, 2012 at 14:18
  • 3
    $\begingroup$ @CodesInChaos I think the reference is to Microsoft's Elephant diffuser used in BitLocker (download.microsoft.com/download/0/2/3/… — warning: downloads PDF). $\endgroup$
    – dchest
    Commented Dec 5, 2012 at 19:12
  • 2
    $\begingroup$ Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being more on-topic here. Please register your account here, too, to be able to comment and accept an answer. $\endgroup$ Commented Dec 5, 2012 at 23:24

1 Answer 1

43
$\begingroup$

XTS vs. Undiffused CBC. The issue here is malleability. Both XTS and CBC prevent an attacker from learning information about encrypted data. However, neither one completely succeeds in preventing an attacker from tampering with encrypted data.

However, it's arguably easier to tamper with an (undiffused) CBC ciphertext than it is to tamper with an XTS ciphertext. Let's say that an attacker happens to know some message says

"blah blah Give Alice \$400 ... blah blah blah".

If this message is encrypted using CBC, the attacker can tamper with the ciphertext in such a way that it will now decrypt to

"blah blah !^%@^^ Give Alice \$800 blah blah blah"

The \$400 has become \$800. This is what your quote about "AES-XTS prevents an attacker from changing one specific bit in a data unit" refers to. Here I write !^%@^^ to indicate that the previous 16-byte block will become gibberish once decrypted, and this gibberish will be beyond the attacker's control.

On the other hand, using XTS prevents this attack. The attacker can corrupt a message by turning any 16-byte block into random gibberish, but he will not be able to have the same degree of control as he did in the CBC example.

But Microsoft decided not to use XTS anyway. The reason is that the ability to corrupt a 16-byte block could still be damaging. Here's the quote from the paper dchest linked:

For example, there could be a configuration file (or registry entry) with a value that, when set to 0, creates a security hole in the OS. On-disk the setting looks something like "enableSomeSecuritySetting = 1". If the start of the value falls on a 16-byte boundary and the attacker randomizes the plaintext value, there is a $2^{16}$ chance that the first two bytes of the plaintext will be 0x30 0x00 which is a string that encodes the ASCII value ’0’.

(This quote is referring to the LRW tweakable cipher, but the XEX tweakable cipher used in XTS has the same problem).

Adding a diffuser. Using a diffuser is Microsft's solution to this problem. The idea here is to "mix" the plaintext up before encrypting it so that an attacker can't change \$400 to \$800 --- meddling with part of the ciphertext will change almost the entire plaintext, not just small parts of it.

This sounds good, but there's a catch: No one actually knows if Microsoft's diffuser actually is secure. To my knowledge, it hasn't received any published formal analysis from cryptographers. This means you should be skeptical about relying on it. Microsoft acknowledges this:

On the disadvantage side, the diffuser is a new unproven algorithm, and this inevitably leads to questions. Without extensive public scrutiny and analysis of an algorithm, there is a justified skepticism about its security. People are reluctant to trust new algorithms. So why did we choose this option anyway? In our final analysis, we decided this was the better choice for our product. The performance gain over the alternatives was important enough to outweigh the disadvantages of a new diffuser algorithm. Time will tell whether we made the right choice.

The bottom line. XTS is less malleable than undiffused CBC. However, CBC+Diffuser is probably less malleable than XTS, at least for practical purposes.

An important aside. Neither CBC nor XTS were designed to be non-malleable. Ensuring that ciphertexts are not tampered with is a separate problem, one that should be solved by using Message Authentication Codes (MACs), such as HMAC-SHA256. The reasons MACs aren't typically used for full-disk encryption algorithms are (1) performance issues and (2) using a MAC requires storing extra information with the ciphertext, which makes adding it transparently a bit tricky.

A middle ground between MACs and diffusers would be to use a wide-block encryption mode, such as CMC, EME, or HEH. You can think of these as having a "built-in" diffuser, that makes them non-malleable. Unlike Microsoft's diffuser, these algorithms have formal security definitions and peer-reviewed mathematical proofs. They are secure under the assumption that AES is secure. Microsoft opted not to use these because of (1) performance issues and (2) patents.

$\endgroup$
6
  • 2
    $\begingroup$ In the context of disk-encryption simple MACs aren't good enough. You'll need hashtree with an authenticated root. $\endgroup$ Commented Dec 6, 2012 at 10:12
  • $\begingroup$ thanks for this great answer!!! this made everything clear... 5***** $\endgroup$ Commented Dec 6, 2012 at 10:52
  • $\begingroup$ Probably this won't work, but won't the problem of malleability be solved by ecnrypting same data twice using different passwords and/or different algorithms? So, instead of using unproven diffuser algorithm, why not use proven AES again? $\endgroup$ Commented Mar 25, 2016 at 10:58
  • 1
    $\begingroup$ @Yura That will depend on how AES is used (XTS for example, usually is built on top of AES). If you use CTR-AES mode twice, the result doesn't become less malleable (flipping a bit in the ciphertext still flips the corresponding bit in the plaintext). If you use CBC-AES mode twice, you can still do the same attack I mentioned in my answer, but the length of the uncontrolled random "garbage" section will double. Finally, using AES in a secure "wideblock" mode would be roughly as fast as either of these solutions, anyway. So might as well do that, instead. $\endgroup$
    – Seth
    Commented Apr 17, 2016 at 6:16
  • 7
    $\begingroup$ Update: Windows 10 does provide the option to use XTS mode. Even bigger/worse update: In Windows 8 Microsoft REMOVED the diffuser. So windows 8 bitlocker doesn't even have the diffuser. $\endgroup$
    – hft
    Commented Mar 17, 2017 at 4:50

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.