Rethinking Block Storage Encryption with Virtual Disks

AES-XTS is the prevalent standard used for disk encryption to date. Among others, it is available in Android (documentation, [n.d.]), Apple’s Filevault (Apple, [n.d.]), Microsoft’s BitLocker (Microsoft, [n.d.]), and Linux’s DMCrypt (Linux, [n.d.]). It is a specific implementation of tweakable encryption (Liskov et al., 2011) - a block encryption mode that takes as input an additional parameter (the tweak) that can be public and adds variability to an otherwise deterministic encryption function. AES-XTS is used in disk encryption by setting the tweak, also referred to as the IV (Initialization Vector), to be the sector number, also referred to as the LBA (Logical Block Address). Therefore, if the same data is written to different sectors they will result in totally different ciphertext as they will use different IVs. A critical security property required of tweakable encryption is that if different plaintexts are encrypted with the same IV, still no information can be deduced about the encrypted data. AES-XTS only achieves this to a certain extent.

In an ideal block cipher, even if it is deterministic, changing a single bit in the plaintext of a sector will result in an entirely different, (random-looking) ciphertext sector. However, AES-XTS falls short of this (as do many other AES-based encryption modes). In AES-XTS, changing a single bit in the sector (without changing the key or IV) will yield the expected change only to the sub-block in the cipher to which this bit belongs. The sub-blocks are the same size as the encryption key - either 32 bytes (AES-256) or 16 bytes (AES-128) and stem from the way AES-XTS is built on top of the AES primitive - a building block that works on small 16/32 byte blocks. Such ciphers are referred to as narrow-block encryption. This means that during an overwrite of a sector (using the same LBA and thus the same IV), an adversary can detect exactly which of the sub-blocks has changed and which have remained the same. Moreover, one can manipulate ciphertexts at a sub-block level. For example, given two versions of ciphertexts written to the same LBA, one can generate a new ciphertext of this sector that combines sub-blocks from both versions. The resulting ciphertext is legal and the manipulation cannot be detected. So encrypting different plaintexts with the same IV provides very good security guarantees at a granularity of a single sub-block, yet leaks some information about the relation between the plaintexts at a sector granularity. Still, due to the practicality of AES-XTS for disk encryption, it is widely used.

Similar shortcomings also exist in other popular block cipher modes. For example, in AES-CBC (Ehrsam et al., 1978) one can detect the first sub-block in which a bit has changed. Note that other methods like AES-GCM (McGrew and Viega, 2004a, b) are completely insecure if the same key and IV are used and may leak information about the plaintext. Hence such modes can only work with a true nonce as an IV (one that never repeats).

The approach that we take to remedy the security shortcomings is to use a random IV rather than use the LBA. If the random IV is chosen from a large enough range, the probability of ever repeating an IV is negligible. This in essence removes the determinism of encryption for overwriting a sector and an adversary would not be able to detect if the underlying plaintext has changed at all. However, as described in the introduction, this requires writing the per-sector IV to the disk so that the sector could be decrypted during reads. Note that one should also include the sector number as part of the IV in order to avoid replay attacks where data encrypted at one LBA is replayed at another LBA.³³3In a system with snapshots one can also integrate the snapshot number into the IV to avoid cross snapshot replay attacks.

Using an authentication code (MAC) on the ciphertext can prevent the various manipulation attacks described above, but also requires additional space. Also, using authentication alone still exposes which parts of the plaintext have changed during an overwrite.

Another approach is using wide-block encryption (IEEE, 2021), an encryption method in which every bit of the plaintext of a sector will influence the entire ciphertext of the sector (as opposed to methods like XTS which are narrow-block ciphers). This holds even if it is built on top of a building block like AES which works on a much smaller size than the sector. Wide-block encryption has been standardized (IEEE, 2021), with two certified methods - XCB-AES(McGrew and Fluhrer, 2007) and EME2-AES (Halevi, 2004; IEEE, 2021). Yet it has not been widely adopted mainly due to lower performance, as well as implementation and patenting considerations. Using a wide-block cipher still carries the limitations of a deterministic cipher (an exact overwrite is easily identified), yet limits the attack granularity to that of a full sector.

The security concerns about the commonly used methods for disk encryption have been raised and studied by the cryptographic community. This was the main motivation for studies on wide-block encryption and their standardization effort (IEEE, 2021).

Brož et al. (Brož et al., [n.d.]) studied adding additional per-sector metadata as part of the dm-crypt encryption framework in the Linux kernel. They do this by using an additional device-mapper called dm-integrity that can be used for storing authentication information, or in the encryption case also a random IV. To ensure consistency between the data sector and its metadata, they resort to using a journal which is shown to reduce the throughput by nearly one-half. Zhang et al.  (Zhang et al., 2020) integrate the AES-XTS encryption with the Flash Translation Layer (FTL) of an SSD and use the number of overwrites a sector has as a seed for its IV (hence ensuring that each overwrite gets a unique IV). This approach works well for storage-side encryption, which means that the data exists in the clear at the storage before being encrypted. Our work targets encryption at the client-side of a distributed storage system, ensuring that the data is always encrypted outside of the client, and attempts to piggyback the indirection layer of the distributed storage system.

Note that some storage protocols like NVMe (starting from version 1.2) (Workgroup, 2014) include the option for a per-sector metadata support. However, this is not widely implemented in existing SSDs and existing implementations typically only allow for 8 bytes of metadata per sector, which is too short for our use-case.

Ceph (Weil et al., 2006) is an open-source distributed storage platform that provides support for object storage, block storage, and file storage. In this work, we focus on the block-storage of Ceph called RBD (Rados Block Device).

The general architecture of a Ceph RBD deployment is depicted in Fig. 1. The Ceph cluster is made out of OSD nodes (Object Storage Devices) that actually store the data and its replicas, monitors that maintain maps of the cluster state and perform access control, and managers that provide additional metrics and interfaces.

In its standard deployment, Ceph RBD employs a client-side driver called libRBD at each host accessing the storage. For every virtual disk, libRBD maps each LBA to a specific OSD node by breaking the LBA space into objects (typically 4MB in size) and computing a placement algorithm for objects. The libRBD library distributes each IO to its corresponding OSD via a proprietary protocol called RADOS. The RADOS protocol supports several high-level functions such as snapshots. It also has supports transactions in which writes of several small IOs are guaranteed to be written atomically. This proved very useful in ensuring consistency between written data and per-sector metadata.

RBD supports client-side encryption (website, [n.d.]a), allowing for data to never leave the host in the clear. The encryption follows the LUKS standard for encrypted disks in which the default encryption is AES-XTS.⁴⁴4Note that LUKS has 2 versions, LUKS1 (Fruhwirth, 2018) and LUKS2 (Milan, 2018). In LUKS2, the default sector size is 4KB per block whereas in LUKS1 it is limited to 512 bytes only which makes adding per-sector information far more costly. In this work, we only consider 4KB sectors.

We explore how to integrate support for additional per-sector information. We focus on the use-case of using a random IV with AES-XTS encryption, but this can be used also for storing integrity information, or using an alternative cipher like AES-GCM. We leave evaluation of these options to future research.

We implement three alternatives on where to store the IV with Ceph RBD, which are illustrated in Fig. 2.

The first alternative is the naïve approach of storing each IV after its matching block in an unaligned contiguous manner. Thus, each access is contiguous to the data and its matching IV, but since the IV size is less than a disk sector size, almost all of the data is unaligned to the disk sectors.

The second alternative keeps the sector alignment by packing several IVs together. The Ceph architecture of breaking data into objects lends itself nicely to this approach. For each object 4MB in size, we store all the IVs of the object after the encrypted data, i.e., at the object end. In this manner, we keep the division into objects as before, the address of an LBA within an object also remains the same, and the IVs are batched together at the object end.

Lastly, we consider using a separate key-value database to store the IVs. In Ceph, each object has a matching database to store additional metadata. This database, which is named OMAP, is implemented using RocksDB (website, [n.d.]c) and can be used to store the IVs. OMAP supports accessing multiple values based on a range of integer keys with a single operation. Thus, if the key used to store each IV is the offset of the block in the object, then a contiguous read or write of the data can also be accessed with a single operation on the key-value database.

In all of the above implementations we use the support in the Ceph RADOS protocol for atomically writing multiple IOs to ensure data and IV consistency.

We implement the three alternatives and test their performance on a 3 node Ceph cluster running Ceph version 16.2.4. We use Ceph’s default configuration of 3-way replication, an object size of 4MB, and an encryption block size of 4KB. We only modify the code on the client nodes that run our modified libRBD code. The OSD nodes are Intel Xeon E5-2650 v4 CPUs. Each node has 9 Intel NVMe disks, of 1.8TB each, and 128GB of memory by 8 DDR4-2400 CL17. The OS is Red Hat Enterprise Linux version 8.4 (Ootpa). The client nodes have a similar CPU and OS version, but with 384 GB memory by 12 DDR4-2400 CL17 of 32GB each. The links between all nodes are 100 Gb/s, and when running iperf between the nodes we measure a bandwidth of around 13 Gb/s.

To measure the throughput performance, we use fio (website, [n.d.]b) which has native support for Ceph RBD. We use fio version 3.1, and deploy a single client random read and write workloads, with 32 maximum parallel accesses on a full Ceph image of 64GB. There are tests for IO sizes ranging from 4KB to 4MB and each test is repeated 10 times. Sequential IO tests are not presented, but give similar results to random IO with large sizes.

Fig. 3 presents a comparison of the three approaches to the baseline which is Ceph’s LUKS2 implementation (website, [n.d.]a) with deterministic LBA based IVs that are not stored. Of the three random IV implementation options, the object end gives the best results for both reads and writes.

For the read workloads, all three approaches perform nicely, likely due to the backend’s ability to do the IV reads in parallel to the data IO. The OMAP version fares slightly worse, due to the overhead of accessing the DB. The object end approach closely mirrors the baseline where the biggest difference we measure is $3\%$.

For the write workloads, there is a significant difference between the three options. Fig. 4 presents the performance degradation of each method compared to the LUKS2 baseline, i.e., lower is better. For the small block sizes, the OMAP solution gives the best performance, but this briefly changes as the IO size increases and the DB fails to provide high performance. The object end option performs better for almost all IO sizes, resulting in 1%–22% performance loss, depending on the IO size.

As the IO size grows, the theoretical overheads of unaligned and object end, measured as the number of sectors that need to be read or written to disk, decrease. For example, in a 4KB write/read, a minimum of two physical disk sectors need to be accessed (one for the data and one for the IV) versus one in the baseline. Whereas a 32KB IO typically requires 9 sectors to be accessed versus 8 in the baseline. Indeed, as the IO size grows we see an improvement in the measured performance overhead (except for an unexplained degradation at 1024KB writes). In the OMAP solution, this calculation does not work and hence the overhead grows significantly with the IO size. We suspect that the unaligned solution performs worse due to unaligned operations that trigger costly read-modify-write operations (these could potentially be further optimized with intelligent buffer writes).