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

• Actually, XTS is not what is normally named "malleable". You can change a ciphertext block and the corresponding plaintext block will change too, but the result of this change is not predictable by the attacker without knowing the key. For CBC, changing a ciphertext block will change the corresponding plaintext block in a unpredictable way and the next plaintext block in a predictable way. – Paŭlo Ebermann Jun 25 '13 at 15:12
• You should use a MAC, not a CRC (which is not a cryptographic operation), and preferably on the ciphertext, not the plaintext. – Paŭlo Ebermann Jun 25 '13 at 15:13
• Thanks for the comments... it was my impression that a MAC operation would be high-cost; CRC is low(er) cost, but provides no protection unless it too is protected. But to your point about malleability... perhaps MAC or CRC isn't really needed at all and it's fine how it is? – mark Jun 25 '13 at 16:05
• Quite likely calculating a MAC is cheaper than the IO-operations to write the block. I'm not sure if there is any cryptanalysis of an encrypted CRC, I suppose this also depends on the mode of operation. In CBC mode you can change the first block arbitrarily by manipulating the IV. Use a MAC (which should include the IV, by the way, and everything else which might relevant to the encryption) and you are on the safe side. – Paŭlo Ebermann Jun 25 '13 at 19:07
• @PaŭloEbermann: I felt your comment above was a better answer to this old question than any of the existing answers below, so I wrote an actual answer based on it. – Ilmari Karonen Aug 7 '18 at 14:08

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.

This appears to be a better question to offer this answer to, in addition to Seth's great answer to the question: "What is the advantage of XTS over CBC mode (with diffuser)?".

Non-malleable file encryption using AES XTS 256?

You'll want to add authentication to the encryption. See paragraphs 2 and 4 below. Links to an article and source code for authenticated encryption are provided at the bottom of this answer.

Wikipedia's webpage on Disk encryption theory provides an up to date answer (compared to Seth's great answer, dated Dec 5 2012) about CBC (Cypher Block Chaining) and XTS (XEX-based tweaked-codebook mode with ciphertext stealing) along with other modes.

CMC and EME have been proposed to fix the problems with XTS. XTS mode is susceptible to data manipulation and tampering so blocks require checksums or other means to detect tampering and it is susceptible to traffic analysis, replay and randomization attacks.

CMC requires two passes and EME is patented so neither is being considered by NIST uses XTS-AES but have been considered by the Security in Storage Working Group (SIS-WG).

Currently Authentication Encryption Modes are being considered. Authenticated encryption with associated data (AEAD) is a variant of AE where the data to be encrypted needs both authentication and integrity as opposed to just integrity. AEAD binds associated data (AD) to the ciphertext and to the context where it's supposed to appear, so that attempts to "cut-and-paste" a valid ciphertext into a different context are detected and rejected.

Other References:

$$\begin{array}{l} \text{Other Modes:} & \\ \text{CMC} & \text{CBC Mask CBC} \\ \text{EME} & \text{ECB Mix ECB} \\ \text{HCH} & \text{Hash Encrypt Hash} \\ \text{HCTR} & \text{Hash Counter Hash} \\ \text{HEH} & \text{Hash ECB Hash} \\ \text{PEP} & \text{Polynomial Hash Encrypt Polynomial Hash} \\ \text{TET} & \text{Hash ECB Hash} \\ \text{ } & \\ \text{Acronyms:} & \\ \text{CBC} & \text{Cypher Block Chaining} \\ \text{ECB} & \text{Electronic Code Book} \\ \text{XEX} & \text{Xor–Encrypt–Xor} \end{array}$$

In the article: "Practical Cryptographic Data Integrity Protection with Full Disk Encryption - Extended Version" by Milan Broz, Mikulas Patocka, Vashek Matyas (Submitted on 1 Jul 2018) they explain on page 1:

"A major shortcoming of current FDE implementations is the absence of data integrity protection. Confidentiality is guaranteed by symmetric encryption algorithms, but the nature of length-preserving encryption (a plaintext sector has the same size as the encrypted one) does not allow for any metadata that can store integrity protection information.

Cryptographic data integrity protection is useful not only for detecting random data corruption (where a CRC-like solution may suffice) but also for providing a countermeasure to targeted data modification attacks. Currently deployed FDE systems provide no means for proving that data were written by the actual user. An attacker can place arbitrary data on the storage media to later harm the user."

"We introduce an algorithm-agnostic solution that provides both data integrity and confidentiality protection at the disk sector layer. Our open-source solution is intended for drives without any special hardware extensions and is based on per-sector metadata fields implemented in software. Our implementation has been included in the Linux kernel since the version 4.12. This is extended version of our article that appears in IFIP SEC 2018 conference proceedings.".

On page 3 and 4, section 2.2, "FDE Protection Types" they further detail:

• Pure FDE - Length-preserving encryption that provides confidentiality only.
• Authenticated FDE - Encryption that provides both confidentiality and integrity protection, but limited by COTS devices (no hardware for authentication).
• HW-trusted - The ideal solution with confidentiality and integrity protection. It stores some additional information to external trusted storage in such a way that the system can detect data replay.

"Authenticated encryption enforces that a user cannot read tampered data but will see an authentication error. It not only stops any attempts to use tampered data on higher layers, but also helps a user to realize that the device is no longer trustworthy. An overview of the features among FDE types is summarized in Table 3.".

On page 5, section 3.2, "Authenticated Encryption" they continue:

"We have two options for integrity protection combined with device encryption: either to use Authenticated Encryption with Additional Data (AEAD) or to combine length-preserving encryption with an additional cryptographic integrity operation. The major difference is that for the combined mode, we can ignore integrity tags and decrypt the data without such tags. In the AEAD mode, the authentication is an integral part of decryption. Additionally, for the combined mode, we need to provide two separate keys (encryption and authentication), whereas the AEAD mode generally derives the authentication key internally. Both mentioned integrity methods calculate an authentication tag from the final ciphertext (encrypt-then-MAC).

The encryption operation output consists of the encrypted data and the authentication tag. Authentication mode with additional data (AEAD) calculates the authentication tag not only from the input data but also from additional metadata, called additional authentication data (AAD). Table 4 summarizes examples of the encryption modes mentioned in this text.".

References from page 20 of their article:

[25] CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness, 2016. https://competitions.cr.yp.to/caesar.html
[26] Hongjun Wu and Bart Preneel. AEGIS, A Fast Authenticated Encryption Algorithm (v1.1). Technical report, 2016. https://competitions.cr.yp.to/round3/aegisv11.pdf
[27] Hongjun Wu and Tao Huang. The Authenticated Cipher MORUS (v2). Technical report, 2016. https://competitions.cr.yp.to/round3/morusv2.pdf

A search for AEGIS256 (AES with authentication) turns up many results, as do searches for the other AEAD algorithms. Unfortunately there is currently no COTS hardware available, whether there is a website somewhere that sells an SDD (or HD) that implements AEAD entirely on the drive is something I'll need to do further research to determine.

It shouldn't be too difficult to use a AES encrypting drive with sedutil and add authentication support to the PBA. For further examples of using sedutil see V$$_x$$Labs article: "Use the hardware-based full disk encryption of your TCG Opal SSD with msed".

Since 2016 there exists a dm-integrity target that can do simple CRC32 verification, or full blown HMAC-SHA1/SHA-256 with encryption keys, to ensure the integrity of the volume.

It's integrated with LUKS (if you use --type luks2), see cryptsetup man page for --integrity option, or use standalone with the integritysetup tool.

You can find some benchmarks in this FOSDEM presentation

I made an XEX based WDE appliance recently and from a file modification perspective, what happens is that if an attacker modifies any bit, then the result is a scrambling of a 16 byte (that is, the block size of AES) chunk of the resulting plaintext.

That... well... kinda blunts any potential bit-flipping attacks, as it means that they can't easily construct an alteration of their choosing.

In my implementation, since I was doing WDE, I was dealing with a 512 byte block at a time in isolation. In my case, I perturbed the nonce on a per-block basis. It's not clear what your data block size is going to be, but for XEX/XTS your random-access "chunks" are going to need to be done in such a blockwise fashion, and you should similarly perturb the nonce. Your nonce perturbation need not have a ton of cleverness, as step 1 is to run the nonce through AES ECB anyway.