XTS-AES Mode For Block-Oriented Storage Devices

XTS-AES MODE FOR BLOCK-ORIENTED STORAGE DEVICES

NIST is currently in the process of approving an additional block cipher mode of operation, XTS-AES. This mode is also an IEEE standard, IEEE Std 1619-2007, which was developed by the IEEE Security in Storage Working Group (P1619). The standard describes a method of encryption for data stored in sector-based devices where the threat model includes possible access to stored data by the adversary.

The XTS-AES mode is based on the concept of a tweakable block cipher, introduced in [LISK02]. The form of this concept used in XTS-AES was first described in [ROGA04]. The standard has received widespread industry support.

Storage Encryption Requirements

The requirements for encrypting stored data, also referred to as “data at rest” differ somewhat from those for transmitted data. The P1619 standard was designed to have the following characteristics:

1.                                       The ciphertext is freely available for an attacker. Among the circumstances that lead to this situation:

a.                                                                                                      A group of users has authorized access to a database. Some of the records in the database are encrypted so that only specific users can successfully read/write them. Other users can retrieve an encrypted record but are unable to read it without the key.

b.                                                                                                     An unauthorized user manages to gain access to encrypted records.

c.                                                                                                       A data disk or laptop is stolen, giving the adversary access to the encrypted data.

2.                                       The data layout is not changed on the storage medium and in transit. The encrypted data must be the same size as the plaintext data.

3.                                       Data are accessed in fixed sized blocks, independently from each other.That is, an authorized user may access one or more blocks in any order.

4.                                       Encryption is performed in 16-byte blocks, independently from other blocks (except the last two plaintext blocks of a sector, if its size is not a multiple of 16 bytes).

5.                                       There are no other metadata used, except the location of the data blocks within the whole data set.

6.                                       The same plaintext is encrypted to different ciphertexts at different locations, but always to the same ciphertext when written to the same location again.

7.                                       A standard conformant device can be constructed for decryption of data encrypted by another standard conformant device.

The P1619 group considered some of the existing modes of operation for use with stored data. For CTR mode, an adversary with write access to the encrypted media can flip any bit of the plaintext simply by flipping the corresponding ciphertext bit.

Next, consider requirement 6 and the use of CBC. To enforce the requirement that the same plaintext encrypt to different ciphertext in different locations, the IV could be derived from the sector number. Each sector contains multiple blocks. An adversary with read/write access to the encrypted disk can copy a ciphertext sector from one position to another, and an application reading the sector off the new loca- tion will still get the same plaintext sector (except perhaps the first 128 bits). For example, this means that an adversary that is allowed to read a sector from the sec- ond position but not the first can find the content of the sector in the first position by manipulating the ciphertext. Another weakness is that an adversary can flip any bit of the plaintext by flipping the corresponding ciphertext bit of the previous block, with the side-effect of “randomizing” the previous block.

Operation on a Single Block

Figure 6.9 shows the encryption and decryption of a single block. The operation involves two instances of the AES algorithm with two keys. The following parame- ters are associated with the algorithm.

Key                    The 256 or 512 bit XTS-AES key; this is parsed as a concatenation of two fields of equal size called Key1 and Key2, such that Key  =  Key1 7 Key2.

Pj                      The jth block of plaintext. All blocks except possibly the final block have a length of 128 bits. A plaintext data unit, typically a disk sector,

consists of a sequence of plaintext blocks P1, P2, Á , Pm.

Cj                      The jth block of ciphertext. All blocks except possibly the final block have a length of 128 bits.

j                         The sequential number of the 128-bit block inside the data unit.

i                         The value of the 128-bit tweak. Each data unit (sector) is   assigned a tweak value that is a nonnegative integer. The tweak values are assigned consecutively, starting from an arbitrary nonnegative   integer.

a                       A primitive element of GF(2128) that corresponds to polynomial x

(i.e., 0000 Á 0102).

aj                      a multiplied by itself j times, in GF(2128).

Ⓧ                      Bitwise XOR.

Ⓢ                      Modular multiplication of two polynomials with  binary coefficients modulo x128  + x7  + x2  + x  + 1. Thus, this is multiplication in  GF(2128).

In essence, the parameter j functions much like the counter in CTR mode. It assures that if the same plaintext block appears at two different positions within a data unit, it will encrypt to two different ciphertext blocks. The parameter i functions much like a nonce at the data unit level. It assures that, if the same plaintext block appears at the same position in two different data units, it will encrypt to two differ- ent ciphertext blocks. More generally, it assures that the same plaintext data unit will encrypt to two different ciphertext data units for two different data unit positions.

The encryption and decryption of a single block can be described as

To see that decryption recovers the plaintext, let us expand the last line of both encryption and decryption. For encryption, we have

C  = CC Ⓧ T  = E(K1, PP) Ⓧ T  = E(K1, P Ⓧ T) Ⓧ T

and for decryption, we have

P  = PP Ⓧ T  = D(K1, CC) Ⓧ T  = D(K1, C Ⓧ T) Ⓧ T

Now, we substitute for C:

P  = D(K1, C Ⓧ T) Ⓧ T

= D(K1, [E(K1, P Ⓧ T) Ⓧ T] Ⓧ T) Ⓧ T

=  D(K1, E(K1, P Ⓧ T)) Ⓧ T

= (P Ⓧ T) Ⓧ T = P

Operation on a Sector

The plaintext of a sector or data unit is organized into blocks of 128 bits. Blocks are labeled P0, P1, Á , Pm. The last block my be null or may contain from 1 to 127 bits. In other words, the input to the XTS-AES algorithm consists of m 128-bit blocks and possibly a final partial block. 

For encryption and decryption, each block is treated independently and encrypted/decrypted as shown in Figure 6.9. The only exception occurs when the last block has less than 128 bits. In that case, the last two blocks are encrypted/decrypted using a ciphertext-stealing technique instead of padding. Figure 6.10 shows the scheme. Pm-1 is the last full plaintext block, and Pmis the final plaintext block, which contains s bits with 1 … s … 127. Cm-1 is the last full ciphertext block, and Cmis the final ciphertext block, which contains s bits.

Let us label the block encryption and decryption algorithms of Figure 6.9 as

Block encryption: XTS-AES-blockEnc(K, Pj, i, j) Block decryption: XTS-AES-blockDec(K, Cj, i,  j)

Then, if the final block is null, XTS-AES mode is defined as follows:

As can be seen, XTS-AES mode, like CTR mode, is suitable for parallel operation. Because there is no chaining, multiple blocks can be encrypted or decrypted simultaneously. Unlike CTR mode, XTS-AES mode includes a nonce (the parameter i) as well as a counter (parameter  j).