Non-malleable file encryption using AES XTS 256? I'm looking to do file encryption of a bunch of individual files, some small, some quite large.  The files will be write-once/read-many, so I could use CBC, however, since the read-access needs to have seekability, XTS seems a better fit.  One issue, as I understand it, is that XTS (or CBC for that matter) is malleable... i.e. if the encrypted cipher text is modified, an attacker could potentially do some targeted things to files.  So I was thinking surely this problem is already solved but it wasn't clear to me what the standard was, if any.  Performance is a concern, so one thought I had was simply running a CRC on each XTS sector and including the CRC result in the plaintext for encryption of that XTS sector (e.g. just expand each sector by the 4 octets).  Thus, if anything in the sector was modified by an attacker, the decrypt would fail (i.e. the CRC wouldn't likely match).  Is there a smarter way, or a standard that's "fast"?

EDIT: it occurs to me that if the files are rewritable (which currently they are not) a CRC on each cluster in XTS mode is still open to an attack where an attacker can guess at the plaintext and write a cluster to a known location in the file and see if it matches the cluster that's already there.  Only way to prevent that is to have a random IV per block as well, that changes per write, I think.
As Paŭlo Ebermann notes in a comment above, the time cost of a proper MAC calculation is almost certainly negligible compared to the cost of reading or writing the data on the disk.

Applying a MAC to each encrypted sector (and the sector number used to derive the IV) will fully protect your data against most forms of tampering.  The main drawback of this method, of course, is the need to store the MAC outputs somewhere so that they can be verified when the data is read back.  But, of course, the same drawback applies to your proposed "encrypted CRC" method as well.



As for the security of using an encrypted CRC as a MAC, it probably depends on details of the way the encryption is done (and I'm not aware of any security analyses of such a scheme in combination with XTS mode).

In particular, if the sector data was encrypted using CTR or OFB mode (or something similarly malleable), then the linearity of CRCs would allow bit-flipping attacks to be done in a way that does not change the CRC checksum.  As Wikipedia notes, this was one of the main weaknesses in the (by now thoroughly broken) WEP protocol, which used an encrypted CRC for integrity protection.

On the other hand, if one were to encrypt both the data and the CRC using a wide-block encryption mode like CMC or EME, this would probably be secure, at least if the CRC was long enough to resist brute force.  Then again, in that case we could presumably achieve equivalent security just by replacing the CRC with a block of zero bytes of the same length, and checking that they're still zero after decryption.  And it would presumably still be slower than XTS plus a proper MAC.



Note that one form of tampering that even proper per-sector MACs will not prevent is a "reversion attack" where the attacker replaces the entire contents of a sector with previously captured ciphertext from the same sector, in effect reverting the corresponding plaintext data to an earlier version.  To prevent such attacks, you could for example compute an additional MAC (preferably of the Carter–Wegman type, such as VMAC or Poly1305, since those can be efficiently updated when part of the input data changes) over the per-sector MACs, and verify that global MAC when the disk is mounted.

Of course, even such a global MAC will still not protect you against whole-disk reversion attacks, where the entire content of the disk is replaced by an earlier copy of it.  In general, there is no way to prevent such attacks unless some data (like a copy of the global MAC) can be securely stored somewhere outside the disk itself.

Also, avoiding accidental MAC verification failures e.g. in the event of a power loss during a write is possible but rather tricky.  Basically, it would require some kind of a secure intent log where you first write an (encrypted and MACed) record of the data you intend to write and the way this will affect the global MAC, flush it to disk, and only then perform the actual write to the rest of the disk.  Done properly, that should ensure that, at any given point in time, either a) the rest of the disk is in a consistent state and properly MACed, or b) the intent log is consistent and properly MACed, and the rest of the disk can be brought to a consistent and properly MACed state by replaying the planned changes recorded in the intent log.  Of course, if you do all that, as a nice side effect you'll also gain extra resiliency against accidental (as well as deliberate) data corruption.