3
$\begingroup$

I'm trying to find a sufficient encryption mode that supports random read and write access. It seems like XTS is a perfect fit, since in my use case authentication and integrity insurance are handled elsewhere, and from my current understanding, these are the only two drawbacks of XTS.

The only thing I don't get (yet) is: I'm not supposed to encrypt any data with the same key and IV twice, right? Now, what if I edit one of the XTS encrypted blocks? The tweak will stay the same since it depends on the block location, so if I use the same key again, this premise is violated. If I use a new key, I'd have to encrypt the whole file again, which means I don't really have random access anymore.

I feel like I got something wrong here. Can someone enlighten me please – and/or maybe even suggest a sufficient mode if XTS is not it?

Thanks in advance.

Improve this question
$\endgroup$
2
  • $\begingroup$ How are you protecting integrity? A merkle tree of hashes/MACs? $\endgroup$
    – CodesInChaos
    Jul 3, 2015 at 9:56
  • $\begingroup$ Of hashes, exactly. @CodesInChaos♦ $\endgroup$
    – elisae__
    Jul 3, 2015 at 10:29

1 Answer 1

Reset to default
4
$\begingroup$

XTS has been designed for disk encryption, where an attacker typically has access to the disk only a single time (when they steal/confiscate the device).

When an attacker sees several ciphertexts encrypted using the same key, they can tell which blocks differ between the versions, but not the content of the blocks. Compare this with CTR mode, which leaks which bits differ, which is far worse.

XTS should be used when an attacker typically sees only one version, but it doesn't fail completely when they see several.

As an alternative, you could either increase the effective block size. Since blocks being identical becomes rarer with longer blocks, this reduces the leak, but it doesn't eliminate it. BEAR, LION, LIONESS, "wide blockcipher" EME and AEZ might be worth reading about (I'm not familiar with the details of these).

Or you could store an IV alongside each sector of ciphertext, replacing it by a new IV when overwriting. If you use a 16 byte IV and 4096 byte sectors, this is an overhead of 0.4%. The bigger downside is that you won't have a direct mapping between equal sized plaintext and ciphertext blocks, which may impact performance and prevents write-through.

You can't avoid information leaks completely, if you can't afford per-sector IVs and need random write access.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes! An answer from CodesInChaos! – I've read your name below so many other good answers and was hoping for that. Thank you, the first part already clarified a lot. So, some follow-up questions if I may: Isn't the problem with using the same key twice that an attacker can draw conclusions about both plaintexts by looking at the differences? Then, how does a bigger block size reduce the leak? Because it takes more effort to calculate differences..? Also, aren't all the ciphers out there designed for a fixed block size and I can't just alter it without writing my own implementation? $\endgroup$
    – elisae__
    Jul 3, 2015 at 10:26
  • $\begingroup$ Besides, the downside you mentioned is exactly the problem; I can't just save 16 extra bytes per 4k, that's why I'm looking for some tweakable cipher. $\endgroup$
    – elisae__
    Jul 3, 2015 at 10:27
  • $\begingroup$ @elisae__ The attacker learns which blocks (at the same position) changed between versions. If blocks consist of a single bit (xor based streamciphers, including CTR mode), they learn which bits are identical, which is often enough to recover the message. If you use AES-XTS they learn which 16 byte blocks are identical. If you use some kind of wide block cipher construction to get 4096 byte blocks, they only learn if such a large block changed. But since you need to rewrite a whole block at once, larger blocks limit random access operations. $\endgroup$
    – CodesInChaos
    Jul 3, 2015 at 10:39
  • $\begingroup$ Okay, I think I got it. Thanks, as well as for the updated alternatives. Unfortunately none of these seem like a really good choice upon first view, but I'll have a closer look at them. Thank you very much! $\endgroup$
    – elisae__
    Jul 3, 2015 at 11:57

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.