Review of XEX in P1619
December 5, 2006
James Randall
RSA Laboratories
781-515-6548
RSA Labs has reviewed Phil Rogaway’s paper on XEX as well as the P1619 drafts (D7, D9, and D10).We support the use of XEX in P1619 and we encourage the development of an optional sector-wide diffusion operation in a future version of P1619 to address concerns about block-level data manipulation and pattern analysis.
We have a number of comments and questions regarding P1619:
· XEX is the name for Rogaway’s tweakable block cipher construction. P1619 combines XEX with what might be called “tweaked codebook mode” (TCB) and “ciphertext stealing” (for the last block). The overall mode of operation in P1619 is therefore AES-XEX-TCB+CTS, and this is what we are deciding to support (or not) rather than just XEX.
· NIST has not yet received a formal submission of the XEX construction, and would not have a position until such a submission is made. It is important for the working group to make such a submission. (Actually, this should be done for the full mode, AES-XEX-TCB+CTS, not just the XEX component.)
· We recommend that Phil Rogaway’s paper: Efficient Instantiations of Tweakable Blockciphers and
Refinements to Modes OCB and PMAC, September 24, 2006, be referenced in P1619.
· Previous drafts of P1619 used AES-LRW-TCB+CTS, where LRW was the working group’s implementation of the Liskov-Rivest-Wagner mode from their original paper about tweakable block ciphers. The main difference between the previous drafts and the current ones is thus the tweakable block cipher construction, not the rest of the mode.
· Rogaway’s paper points out features of XEX that are not used in P1619. One difference in Rogaway’s paper is that the same key is used both for the underlying encryption and to derive delta from the sector index. Rogaway shows how to do this while ensuring the overall security of the algorithm. It doesn’t hurt to use different keys K_1 and K_2 for the two purposes, but it’s not clear why P1619 does this rather than following Rogaway more closely, except perhaps that the P1619 implementation of LRW needed two keys. Some explanation of these differences would be useful. Another difference is that Rogaway defines the tweak as the collection of offsets, whereas in P1619 just the sector index is the tweak. For consistency, the tweak in P1619 should consist of both the sector index and the block index within the sector. To meet the definition of the XEX, there also needs to be an upper bound on the block index (just to ensure that the alpha^j values are unique – so not a practical limitation).
Rogaway’s paper doesn’t analyze TCB+CTS mode. While it seems reasonable that TCB+CTS mode would preserve the security properties of the underlying tweakable block cipher and the claims made about possible attacks, it would be useful to have a formal proof that this is the case. The bounds on the birthday attacks in the appendix may need to be updated slightly.
· A long time ago, Ron Rivest developed another XEX-type construction for RSA, with two fixed delta values, one applied before and one after encryption. This was intended as a simple way to increase the key size of a block cipher such as DES. It has been shown over time to be quite effective in doing so. Since the delta values are fixed, however, this particular construction wouldn’t provide the appropriate security properties for TCB+CTS which requires each block to be encrypted with a different “tweak”.
· TCB+CTS provides reasonably good security for sector encryption, given the constraint that no message expansion is allowed. There are three basic security threats to consider:
(a) One-time disk reading. An adversary obtains access to a disk once, and reads the ciphertext stored on it. The mode provides adequate protection against this threat. The ciphertext does not reveal any information about the message or the keys (except for the pathological case where the message consists of delta-related values).
(b) Many-time disk reading. An adversary reads the ciphertext at many different times. The adversary can tell whether a given block has changed, and therefore may be able to infer information about the behavior of an application. If the mode included a sector-wide diffusion operation, then the adversary would only be learn which sectors had changed, not which blocks.
(c) Disk writing. An adversary modifies the ciphertext. The adversary can cause block-level changes in the corresponding decrypted message. For instance, the adversary can “roll-back” a block to a previous value, or try to cause a block to have certain patterns (at random). The application will need some other means to verify the integrity of a decrypted block.
TCB+CTS thus deals with the primary threat (a), with some protection against (b) and (c). Other modes are much weaker. For instance, counter mode is significantly vulnerable to many-time disk reading (it’s a one-time pad and loses security if used more than once) and disk writing (individual message bits can be changed by changing the corresponding ciphertext bits). Given the constraint on message expansion, it’s not possible to get much better. The diffusion operation (for which there is yet no standard we’re aware of) is the only significant improvement. If message expansion were allowed, there would be many other modes to consider that offer some form of integrity protection, but these are currently out of scope.
· TCB+CTS’s parallelism may be an advantage, for instance compared to CBC mode which is inherently sequential (for encryption). However, it’s not clear to us how important parallelism is in the overall performance of encryption relative to disk access time. AES encryptors with 40K gates are available that can run at 4 Gb/sec; parallelized versions can run at 40 Gb/sec. Would the time to encrypt the full sector, one block at a time, present a bottleneck in a disk operation?
· Since the set of recommended algorithms may change over time, it’s important to have some flexibility (aka “algorithm agility”) in the encryption architecture. Algorithm information should be stored along with the key so that in case there’s a transition to a new algorithm at some point, it’s possible to distinguish which sectors are encrypted with one algorithm versus another. This flexibility will be useful if there’s an upgrade to P1619 as suggested above to include a sector-wide diffusion operation.
· If the data stored on the disk were ever copied at the physical layer to another disk (e.g., in a backup or mirroring operation below the encryption layer), it would be essential to maintain information on the sector numbers, since the decryption operation (the tweak) depends on the sector number.
· The usual key management and access management issues apply, as with encryption at other layers of storage.