You Don't Want XTS

http://sockpuppet.org/blog/2014/04/30/you-dont-want-xts/

by pytrin • 12 years ago

64 107 12 years ago

tptacek36• 12 years ago

If anyone's interested in a fun project:

It's apparently pretty common for people to create virtual Truecrypt volumes and stick them on Dropbox, as a sort of poor-hacker's encrypted Dropbox.

Someone should bone up on the "Evil Maid" attack and do a proof-of-concept of it on a Dropbox-backed volume. Call it "Evil Maid In The Cloud", or "The Mallory Poppins Attack".

My intuition is that the Evil Maid attack is much more powerful vs. Dropbox-backed volumes.

NateLawson2• 12 years ago

The block layer is a poor location to support security, whether access control or encryption. The lack of knowledge of upper layers & the resource constraints of the lower layers (block stealing for metadata) unnecessarily hamper its security and performance.

The only reason for block-level encryption in software is because it was too much work to retrofit UFS, ext23456fs, FAT, NTFS, etc. with encryption. The block device provided a convenient bottleneck, and no one cared too much about the downsides you bring up because it seemed better than nothing.

ZFS generally gets this right, using AES-CCM (an AEAD mode as you recommend). It also has proper integration with the deduplication layer so encryption doesn't waste space. These reasons and more show why security needs to be implemented at the filesystem layer.

Another good example people here may be familiar with is Tarsnap. Again, it handles encryption, integrity protection, and deduplication without storing keys on the server side or unnecessarily restricting itself to a block device metaphor.

You're right that TC+DB are not a safe combo. Dropbox needs to be the encrypted Dropbox.

helper• 12 years ago

It's too bad that ZFS encryption is only in Oracle ZFS, not OpenZFS.

tveita3• 12 years ago

Keep in mind that the simpler implementation of block layer encryption also makes it easier to implement and audit.

I'm not as confident in the design and implementation of encryption in e.g. ZFS as I am in full disk encryption.

I'm not sure Tarsnap is a great example of doing encryption at a high level either. As I understand it the encryption layer only deals with opaque chunks of data; it doesn't know anything about high-level concepts like files and folders that the Tarsnap application operates on.

schoen9• 12 years ago

What kind of access are you assuming the attacker has here? Modifying the ciphertext stored with Dropbox?

Evil Maid attacks that I've heard described before typically involved modifying (unencrypted and unauthenticated) bootloaders or kernels, rather than FDE ciphertext, although I realize that's not part of the definition of the attack.

makmanalp• 12 years ago

Right, wouldn't it be extremely difficult to modify the ciphertext to create a meaningful change in the plaintext, such that checksums do not fail?

rdl2• 12 years ago

I guess the question is if you could do bad things to truecrypt itself this way, or if it would be easier to rely on user intervention. There is also "what can be done by Dropbox itself" (potentially via court order) vs what could be done by mitm (not sure what protections Dropbox has against this; if it uses the host ca certs to authenticate vs in app cert pinning (which is obvious and good), etc.

Being able to "glitch" someone's truecrypt volumes without even compromising the crypto could lead to fun. Also, OS/file system cruft on the level above, essentially the equivalent of an .htaccess file, could be fun.

sillysaurus33• 12 years ago

Would you mind expounding? It sounds very interesting, but I'm having trouble figuring out how an evil maid attack might be employed against Dropbox-based Truecrypt volumes, since people can't boot from those.

tptacek36• 12 years ago

You need to generalize the attack past boot, to the core concept of "victim interacts with disk, attacker tampers with disk, victim interacts with disk".

sdevlin• 12 years ago

Here's one possible approach.

Assume the attacker can modify plaintext on disk indirectly. This might be viable if e.g. the user's browser cache lives in the TC volume. (Not sure what typical TC-in-Dropbox usage patterns are, so this may or may not be realistic.)

Further assume that the attacker can observe ciphertext changes in Dropbox.

XTS is vulnerable to the same byte-at-a-time plaintext recovery attacks as ECB. This is usually irrelevant, because adaptive chosen plaintext attacks are outside the threat model considered for FDE. But in our scenario, the attacker has at least some degree of plaintext control.

The success of this attack will depend a lot on how fine-grained the attacker's control over his insertion point is, i.e. can he reliably write to the same location over and over again? Any number of components might thwart that control, so I'm not sure how easy it will be to make this work.

pedrocr• 12 years ago

It's apparently pretty common for people to create virtual Truecrypt volumes and stick them on Dropbox, as a sort of poor-hacker's encrypted Dropbox.

People do that? encfs/ecryptfs sounds like a much better fit for that use case. Encryption is per file and you can even disable the filename encryption if you want to still be able to navigate your files using their interface. Are there no good similar solutions for Windows/OSX?

makomk5• 12 years ago

encfs uses the same questionable encryption techniques that motivated the creation of XTS in the first place. It's structured almost like full-disk encryption at the file level. I think the same's true of ecryptfs.

schoen9• 12 years ago

After reading the original article and this whole thread, including some quite useful discussions about the security goals of disk encryption, I'm convinced that this is extremely hard (with XTS) under realistic attack scenarios.

However, I've been reminded that a realistic attacker can do much more to an FDE volume than we would first imagine. So, I'm planning to try to play around with this to improve my intuition of how bad the attacks actually are. Thanks for the challenge.

... huh. Actually, suppose the attacker could somehow cause a very large number of file downloads to happen (with known sequence, timing, and contents). The Birthday Paradox gives the attacker a high probability of being able to see a pair of files from two separate sets of files (of different kinds and different origins) land on a particular sector at different times. When that happens, the attacker can then substitute one for the other.

If we think of a computer for some reason downloading and storing a lot of "trusted" files and a lot of "untrusted" files, and that the attacker can see empirically where each file was stored, then when a trusted file gets stored at an offset where an untrusted file was previously stored, the attacker will be able to substitute the contents of the latter for the contents of the former. For this attack to be harmful, the untrusted file that was stored at that location just needs to contain something that it would be harmful for the attacker to be able to replace the corresponding trusted file with.

Tomte3• 12 years ago

I don't get the title.

The title tells me I don't want XTS.

Then the post explains that I don't want FDE, for sundry reasons. Then it tells me, sure, go ahead and use FDE, but be aware of the limitations.

At that point it looks like I want XTS, after all.

Then it shows how XTS works and where cryptographers are seeing problems.

And then... well, there is no "then". The recommendations don't deal with FDE at all.

I think the post would be much stronger, if it either had some alternative mode to present or (I'd be more interested in that) it showed other ways to achieve what people usually try to achieve with FDE. And usability is a big one there. Bitlocker is huge. FileVault is huge. People can actually use it.

An aside: Has anyone ever seriously used XTS mode for anything but FDE? I've only encountered it in Truecrypt and the part of Boneh's Crypto I where he's talking about FDE. But that doesn't mean much, I admit.

tptacek36• 12 years ago

The post ends with the takeaways I'm hoping for:

1. Try not to rely on FDE at all.

2. For God's sake don't use XTS for anything other than FDE.

There's an encrypted filesystem guy that suggested they were moving to XTS. That's what prompted the post.

Usability is great. I think you should turn FDE on. But turning on FDE buys you a lot less than you think it does. There's a pretty good chance that FDE isn't going to do anything for you if your computer is seized by the FBI, because the key will probably resident when they do that.

You don't want XTS, in general, because you don't want to turn a simpler problem (safely encrypting your secrets) into a hard problem (simulating hardware encryption).

Tomte3• 12 years ago

Okay, so I seem to have gotten the gist of it.

Still, I want XTS. :-)

schoen9• 12 years ago

Do you know if there are any effective forensic attacks in use against the TRESOR design?

(I was one of the authors of the cold boot paper at USENIX Security, but I haven't followed the subsequent history of attacks and defenses very consistently.)

makomk5• 12 years ago

In practice, many encrypted filesystems already use encryption that's strictly worse than XTS, and they generally use the same block-based model as full disk encryption for exactly the same performance reasons.

elliotz2• 12 years ago

I agree. Although the article content is good and reaches a good, nuanced conclusion, the title is going to confuse people. Many people will only ever encounter XTS when setting up full disk encryption with dm-crypt, where they'll be presented with the choice between XTS and CBC-ESSIV. This is already a confusing choice with no good context to help a user make a decision. Remembering this headline, I bet some people are going to pick CBC-ESSIV over XTS, which is wrong.

The title is also somewhat link-baity, since I clicked expecting bombshell revelations about XTS. I suggest the mods to change it to "You don't want XTS (except for full disk encryption)."

tptacek36• 12 years ago

Since the article doesn't really endorse XTS in any context, I'm not sure your proposed title is accurate.

I didn't write the article for the front page of HN. I wrote it so that the next time someone says "we're going to switch from CBC to something more advanced like XTS", I can point them at the article instead of writing a long comment.

zokier2• 12 years ago

Authors recommendations seem bit "handwavy" to me. I understand that this article probably is not intended for end-users, but still it would have been nice to have more concrete advice. Eg dm-crypt is usually used with XTS mode, what would the author (or the good crowd of HN) say to be "better" solution (not necessarily at block layer) for eg. protecting laptop?

NateLawson2• 12 years ago

As I mentioned above, ZFS is a good example of filesystem encryption without the block device constraints.

But between your OS and the hard drive in your laptop, use whatever full disk encryption software that is best supported & most secure. He's not criticizing FDE in general, he's saying "don't constrain yourself to the block device model if you're designing database encryption etc etc."

zokier2• 12 years ago

ZFS is a good example of filesystem encryption without the block device constraints

Would you happen to know if there is anything equivalent planned/done for btrfs (or ext4)?

midas00712• 12 years ago

TL;DR For random-seek block encryption, don't use XTS, use CTR.

It's simple. I like simple maths and code, it's less to screw up and less for implementations to screw up. For example, I don't trust EC or GCM, even if some people thinks they're the new hotness, because complexity creates more opportunities for obfuscation and puts the code further out of reach of the already few eyeballs actually (or not) looking at it.

Maybe 'cpervica explain why

tptacek36• 12 years ago

What? No. Don't do that.

ronaldx• 12 years ago

This is why you should never tell people what not to do, without also telling them what they should be doing ;)

midas00712• 12 years ago

? What's wrong with CTR? CTR is basically an OTP. Being OTP, encryption and decryption are basically the same construction (thank you XOR).

    cipherblockdata = blockcipher(key, nonce . block #) ^ plainblockdata
    plainblockdata = blockcipher(key, nonce . block #) ^ cipherblockdata

If MAC is needed, that can happen after encrypting, before decrypting. (Needed if bytes traverse network, but maybe not for local disk or file encryption unless.)

Edit fixed my maths:

comex3• 12 years ago

So why can't we authenticate all the sectors? Is the performance really that bad, even with AES-NI and such? Chrome OS and Android devices that use dm-verity already do this (albeit for read only), so that's hard to believe...

With SSDs, seek time shouldn't be an issue. You can argue that if an attacker can modify your disk, they can probably run code to steal your password, but this does not apply to Dropbox-stored disk images, and AFAIK you can try to secure a PC against modified code seeing the keys using TXT.

tptacek36• 12 years ago

This is a good question. Here are some reasons:

* If you're working with 512 byte sectors, the cost of individual MAC tags gets high.

* No matter what your sector size, reserving space for the MAC tag gets you odd-sized sectors.

* Most importantly, what does it mean to have a sector with a bad MAC? How does that get reported back to the filesystem? Filesystems aren't designed to cooperate with the disk to track cryptographic attacks.

By the time you solve that last problem, you've already gotten yourself pretty far down the track of just providing crypto in the filesystem layer. Which, because the filesystem layer is format-aware, you might as well just keep going and make a proper cryptographic filesystem.

schoen9• 12 years ago

For the last question, couldn't a sector with a bad MAC get reported the same way that a hardware failure reading the sector would be? (Maybe that would produce misleading error messages to the user?)

caf3• 12 years ago

Is there anything wrong with reporting a sector with a bad MAC as an unrecoverable read error, just as the hardware would do if the CRC failed?

Reserving the space is the real killer - either you end up with non-512-byte sectors (and what is more problematic, sectors that don't divide the system memory page size) or you stash the MACs elsewhere in which case every write to a sector also requires a read-modify-write of the sector that holds the MAC.

sweis3• 12 years ago

I primarily like XTS because it's very fast and can be efficiently pipelined on x86 platforms with AESNI. I can get 215 Gbps throughput on 8 cores of a modern Intel CPU.

Also, if XTS is used in a length-preserving fashion, it can encrypt standard block devices without significant changes.

However, length-preserving means that it's either not going to be authenticated or you need to keep authentication material elsewhere. In the latter case, I'd rather use GCM.

tptacek36• 12 years ago

The AES-NI properties that XTS exploit can also be exploited by better wide-block-narrow-block constructions; Rogaway for instance suggests that XTS could have cleaned up the CTS construction by using a better understood Feistel construction.

Even better would be a "native" wide-block tweakable cipher, one that created a strong PRP out of the entire sector, rather than chunking the sector into narrow blocks and then ECB'ing those narrow blocks. However you did that, it would also probably involve invocations of the AES block transform, and thus benefit from AES-NI.

But you're right: XTS has a convenience advantage for encryption in the standard hardware block device setting. What's sad about that is that simulated hardware block encryption is actually not a particularly strong protection for users.

pbsd• 12 years ago

Have you checked Rogaway's AEZ? Its core could probably be repurposed to disk encryption, being an AES-based tweakable wide block cipher.

oggy6• 12 years ago

I don't want XTS? Yes I do, for the purpose it was designed - block device level encryption. The title is misleading, and potentially dangerously so - I could see somebody switching to some CBC-like mode in TrueCrypt "coz tptacek said so" (even if that's not what he said).

And I think several statements are, well, let's say disputable. OK, XTS has the unnecessary complication of two keys, introduced in the standardization process. But the security in storage group (whatever it's called) has apparently seen the light is working on essentially allowing just one again.

Furthermore, XTS is denounced for having "unclear security goals", and the post leaves the impression that wide-block schemes are so much better. Yet their goals are essentially exactly the same as those of XTS, just on a sector as opposed to a (cipher) block level. And do correct me if I'm wrong, but I believe they are pretty clear: essentially ECB encryption of every cipher block on the disk, with a different key. In more concrete terms, I believe those translate to security under deterministic chosen-plaintext attacks, and non-malleability.

Finally Evil Maid attacks (at least the ones presented so far) have absolutely nothing to do with any cipher mode you're using, and everything to do with the trusted platform problem. Maybe in a Dropbox setting the attacker could benefit from the cut-n-paste abilities, but I'm not sure how realistic/severe those attacks would be (presumably you wouldn't have your system partition on Dropbox). I'm having a hard time imagining them, but then again there exist much smarter people than myself in this world.

Not to be only critical of the article, I do believe that the basic messages are sound: be aware of the limitations of FDE and don't use XTS in the contexts outside of FDE (unless you really know what you're doing, I guess). But the rest of it I could do without.

tptacek36• 12 years ago

Couple responses:

You scare-quote "unclear security goals", but that's not my objection, that's Phil Rogaway's objection. And his argument (and Ferguson's argument, and Liskov's argument) isn't hard to understand: by adopting disk sectors as the setting for your encryption, you trade transparency (the ability to use encryption on any filesystem) for a whole mess of constraints, which the article you're commenting on lays out in detail. The worst of these constraints is that you lose any real authentication, but the fact that XTS is basically XEX-ECB is another problem.

You've also taken the "two keys" issue out of context. The issue isn't that it unnecessarily uses two keys. The issue is that it's hard to derive clean security proofs for XTS, because of all its complications. The way Rogaway puts it: there are three constructions involved in XTS --- the XTS wide-to-narrow block adapter, the "XEX2" two-key XEX construction for full narrow blocks, and the "XEX3" two-key construction for partial narrow blocks.

I believe you're also wrong about the Evil Maid scenario. Perhaps you're getting hung up on a detail that I wasn't implicating (for instance, booting from the drive). The issue is that in a normal FDE setting, attackers don't get repeated use-tamper-use cycles. But in a cloud-backed FDE setting, they easily do get that, so more sophisticated versions of the same attack scenario are possible. Think "Evil Maid" here in the same sense as Kenny Patterson used the "BEAST" attack scenario to build a plausible attack on RC4.

The problem with XTS is that there are better modes you can use, even for sector-level encryption, if you shake off the constraint that you're working with physical disk geometry. Which, in the real world, a lot of FDE users can in fact do, because they're not working with real disks but rather virtual disks stored on cloud filesystems.

If you don't need to comply with physical disk geometry, it is probably feasible to get block-level encryption with strong authentication guarantees, and with a native wide-block PRP that will get rid of the ECB data leak in XTS.

Finally, don't use XTS for anything but FDE, even if you know what you're doing. That's a bit of a tautological statement for me to make, because if you know XTS, you also know that it's only meant for FDE --- but I've been getting comments from people who have seen XTS used in application-layer crypto. Bad. Ick.

oggy6• 12 years ago

As for security goals: are they not the ones I stated in my post? No, ciphertext integrity is not among them, and yes, there are consequences to this. Yes, it's a trade-off for efficiency. But I really don't see how all of that relates to the issue of missing security goals.

What paper by Rogaway are you referencing there? I'm assuming it's not the original XEX paper, and I'm genuinely interested in reading it, this discussion aside. Anyway, I don't understand the "wide-to-narrow block adapter" part. Assuming that the standard group removes the two key "improvement", the only bit that I can see that remains to be proved, is the ciphertext stealing. I admittedly don't know whether proofs for the whole construction exist. A quick search revealed Liskov's review of the XTS draft which gives a sketch, but not the whole proof.

I'm confident about my Evil Maid statement. The essence of (what's commonly referred to as) Evil Maid really is the fact that you cannot trust your own computer. The multiple visits make the attack significantly easier, but are not necessary - you just need a more advanced malware.

As for repeated tampering, I'm still having a hard time imagining a realistic attack. I just don't see how the attacker can get any predictable amount of control of the FDE's inputs, but like I said, people can come up with smart things. The "system drive" in my post was referring to things like weakening the system security by overwriting configuration files with garbage and the like, which are theoretically possible although I don't really see them being practical.

Yes of course you can get better security guarantees if you change the constraints. You're probably correct that it should be feasible to offer a 512 byte sector view to the OS on the one side, and use whatever size on the physical side, if your physical side isn't really physical.

P.S. I didn't really think much of the the scare-quotes retort, seemed like a bit of a cheap jab. If you however have a better idea (or pointers for that matter) about how to refer to a specific part of a blog post I disagree with, I'd be interested to hear.

zanny• 12 years ago

Man I've been having a run around recently with a notebook I just ordered.

First intuition is to just LUKs both disks. Ok, that might work, and then I see the horrible performance degradation from FHDing an SSD.

Second intuition is SED, and I got a Crucial m550 to hopefully satisfy that, but then I find out there is no documentation on if the ATA password is stored in the firmware. If it is, I'm just wasting my time, and I kind of just have to hope Crucial does the right thing and doesn't store the AES key anywhere. I also have to hope the marketing "hardware encryption" is true like on my 840 Pro, where I don't see any performance loss.

And even userspace level encryption of config files that use plaintext passwords is terrible (and lets be honest, way too many different programs hide credentials in plaintext somewhere for me to find all of them easily with a full desktop - off the top of my head, networkmanager, KDE-PIM, Telepathy, Firefox, and Steam all have their own independent unrelated credential stores).

In general I would just want to encrypt all of base ~, /var, and /etc, since that is where personal data can end up (and maybe /opt, because random stuff ends up there) - but then I'm still losing most of the reason of having an SSD, especially one with a hardware AES accelerator that would go unused.

And don't get me started on the mechanical drive, which I'm going to have to part bin when I get the thing and see if it has working hardware encryption. At least on that it isn't too bad to use LUKs, because then the overhead isn't as bad - but having overhead at all kind of sucks.

tbirdz• 12 years ago

As someone who uses dropbox to store encrypted VirtualBox vdi virtual hard disk files using XTS encryption, can someone tell me what I should be using instead of XTS?

You Don't Want XTS

Related Stories