Enhance system security with better data-at-rest encryption

Dave Kleidermacher

March 24, 2012

Dave Kleidermacher

Which encryption algorithm?
Data-at-rest presents some unique challenges for encryption algorithms relative to network security protocols.

For data-at-rest protection, an encryption algorithm must be performed without adding additional storage space: A plaintext media block is encrypted in place, generating a ciphertext block of the same size. The most basic encryption mode, electronic code book (ECB), would provide this memory conservation but is not suitable for data-at-rest encryption since any two same plaintext blocks will encrypt to the same ciphertext, making it easy for an attacker to find patterns in the data and potentially derive information. We must consider other modes, most of which require an initialization vector (IV). However, to avoid space expansion, the data-protection system must include a means for implicitly deriving this IV.

Implicit IV derivation poses a surprisingly difficult challenge for common encryption modes. Many modes require uniqueness: The same IV must never be reused for a particular key. For example, with counter mode, a predictable counter can be used, but the same number can never be repeated for a given key. For cipher block chaining (CBC) mode, a unique and unpredictable number must be used. Network security protocols have the freedom to generate the IV and send it along as part of the transmitted data; for the Advanced Encryption Standard with CBC (AES-CBC), each transmission can generate a new random number for the IV and transmit this IV to the receiver. But for data-at-rest, we have no room to store the IV for subsequent decryption.

The obvious source for an implicit IV would be the sector number and offset for a particular data block. Using this combination provides every disk block with a unique input value. However, as data is read and written over time, the same sector and offset are reused for the same key. This implies a serious weakness in the applicability of common encryption modes for data-at-rest protection. Numerous other weaknesses of common modes, especially CBC, have been identified when applied to data-at-rest protection protocols. Clemens Fruhwirth has written an excellent paper discussing these weaknesses.²

Tweakable ciphers
The good news is that cryptographers have worked diligently to address this encryption mode challenge. Liskov, Rivest, and Wagner introduced the concept of a tweakable block cipher in 2002.³ The basic idea of a tweakable cipher is to apply the IV concept to the single-block cipher itself rather than to a chaining mode built on top of the block cipher. As shown Figure 2, the block cipher converts a plaintext block to a ciphertext block, using both the traditional key as well as the tweak as inputs.

The practical application of tweakable ciphers for the data-at-rest protection problem is the property that the cipher's security doesn't preclude reuse of the IV; thus, media sector number and block offset within the sector provide a perfect fit for tweak selection.

XTS-AES
In 2007, IEEE's Security in Storage Working Group (SISWG) published standard P1619.⁴ The IEEE P1619 standard defines the XTS-AES cipher mode as a result of a thorough study of numerous potential tweak-based algorithms for use in data-at-rest protection.

This choice is further bolstered by NIST in "Special Publication 800-38E", which approves the XTS-AES cipher mode and references its definition in IEEE P1619-2007.⁵ NIST has also amended FIPS 140-2 to include XTS-AES as an approved cipher for validation.⁶

The tweak algorithm found in XTS-AES is based on and almost identical to the one originally created by noted cryptographer Phillip Rogaway, called XEX.⁷ In addition to strong security, XEX (and hence XTS-AES) are also designed for efficiency when applied to storage of many sequential data blocks (as is common with file storage).

The XTS-AES block cipher is depicted in Figure 3. Oddly this cipher requires twice the keying material; for 128-bit security, 256 bits of key must be used. The first half of the key is used to process the plaintext; the second half is used to encrypt a 128-bit representation of the sector number, which acts as the primary tweak, as shown in Figure 3. The result of this encryption is fed to a function that performs a Galois field multiplication (implemented as a sequence of shifts and XORs) of the encryption result with a Galois constant derived from the secondary tweak, the numeric index of the data block within the sector. The result of this Galois multiplication is used twice. First it's added (XOR) to the plaintext block, which is then encrypted with the first key half. The Galois result is added (XOR) again to the plaintext block encryption result to create the final ciphertext block.

Decryption is similar; however, while the AES-ECB decryption algorithm is used to process the ciphertext, the tweak cipher remains the same, using the AES-ECB encryption algorithm.

In practice, data is stored to media in sectors. Therefore, the block encryption algorithm shown earlier must be executed in a loop across the entire sector. Note that while XTS-AES handles partial blocks, that part of the algorithm is often unnecessary. For example, the common sector size of 512 bytes will result in 32 block encryptions, and most media-management layers will access a full sector at a time. For such a system, given a function, xts_encrypt, which takes the sector number and size in bytes, plaintext block, and encryption key as input, the simple code sequence in Listing 1 handles the sector encryption.

sector_encrypt(uint8_t *sector, uint32_t sector_num, uint32_t
       sector_size, uint8_t key[])
{
    uint32_t i;
    assert((sector_size % AES_BLOCK_SIZE) == 0);      /* 512 % 16 */
    for (i = 0; i < sector_size/AES_BLOCK_SIZE; i++)  /* 32x */
      xts_encrypt(sector+i*AES_BLOCK_SIZE, key, sector_num, i);
}

It's also easy to see from this code sequence that XTS-AES is parallelizable. If the embedded system contains an AES hardware accelerator (especially one that has direct support for XTS mode), this implementation should be modified to take advantage of the accelerator's ability to process multiple AES blocks at once. Furthermore, if the media allows for sector size configurability, developers may want to vary the sector size to see if better throughput (potentially at the expense of slightly reduced space efficiency) can be achieved.

When selecting data-at-rest protection products, avoid legacy approaches that use weaker modes (numerous CBC-based implementations have been commercialized). Employ the NIST- and FIPS-approved standards instead.