Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 blockoffset, so each data block can be encrypted independently (makes sense when encrypting harddrives/partitions). i cannot really see an advantage of XTS.

now, they write the following: "There are several advantages over alternatives such as AES in CBC: there is no requirement for an initialization vector (the tewak key can be derrived from the block number); each block is encrypted differently (since the tweak value will be different); and unlinke 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 seconde advantage, "...ES-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."?

Thank you very much! thomas

share|improve this question
    
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. –  CodesInChaos Dec 5 '12 at 14:18
    
@CodesInChaos I think the reference is to Microsoft's Elephant diffuser used in BitLocker (download.microsoft.com/download/0/2/3/… — warning: downloads PDF). –  dchest Dec 5 '12 at 19:12
    
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. –  Paŭlo Ebermann Dec 5 '12 at 23:24
add comment

migrated from stackoverflow.com Dec 5 '12 at 13:22

This question came from our site for professional and enthusiast programmers.

1 Answer

up vote 7 down vote accepted

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 scepticism 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.

share|improve this answer
    
In the context of disk-encryption simple MACs aren't good enough. You'll need hashtree with an authenticated root. –  CodesInChaos Dec 6 '12 at 10:12
    
thanks for this great answer!!! this made everything clear... 5***** –  tommynogger Dec 6 '12 at 10:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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