How to Implement Authenticated Encryption on XTS-Enabled Devices

XTS is a block cipher mode for storage encryption. IEEE and NIST have standardized it, and it is widely deployed in real-world applications, including FileVault2, Bitlocker, and dm-crypt. However, it is well-known that XTS provides limited confidentiality and no integrity. XTS prevents simple attacks, e.g., information extraction from a stolen device. However, applications of XTS are expanding, such as cloud storage and CPU memory, where this issue implies a significant security threat. To address this issue, we propose iXTS, a family of black-box conversion methods of XTS into an authenticated encryption (AE). To make our proposal usable in practice, we need to assume that the only controllable part of the XTS engine is the plaintext input, because XTS engine’s ciphertext output is typically directly connected to the storage device and we assume the adversary is able to access the device directly, in addition to the black-box access to the engine. It is also desirable that the conversion could be done without the knowledge of the internal XTS key and without touching it. These constraints pose non-trivial technical challenges, and iXTS is the first effective solution meeting these constraints. We prove that each member of iXTS achieves n/2-bit security as a randomized AE using an n-bit block cipher. This security level is equivalent to popular AE modes such as GCM. iXTS is efficient as it requires no additional cryptographic computation beyond the original XTS. Plaintexts are expanded by a small amount, which is necessary for achieving AE. Our benchmarks on Intel platforms with AES-NI demonstrated that iXTS incurs only minor computation overhead from the underlying XTS.