Does XTS provide random write access?
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.