Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

XEX and LRW-TBC



-- SECTION 1: XEX ---

Has SISWG considered using XEX as specified in [Rog04] instead of LRW
for the
tweakable narrow-block encryption standard recommendation?

XEX is a general-purpose provably CCA-secure tweakable block cipher, and
like
LRW, an instantiation of the class of tweakable block ciphers described in
[LRW02]. XEX is the primary building block of OCB mode. It has many
advantages
over LRW, see below.

We will use XEX as specified on page 4 of [Rog04]. XEX is a general-purpose
algorithm, a concrete application for sector encryption follows.

Let a 512-byte sector with index N be divided into 32 plaintext blocks p_i,
i = 0..31 (16 bytes each). Let E_K(.) and D_K(.) denote AES encryption
and decryption
with key K. The transformed tweak T will be

    T = 2^i * E_K(N)

where i in [0 .. 31] is the block index in the sector. Sector will be
enciphered as follows:

T_0 = E_K(N)

for (i in [0 .. 31])
    c_i = E_K(p_i + T_i) + T_i
    T_(i+1) = T_i * 2

where c_i are ciphertext blocks, = is assignment, * and + are
multiplication and
addition in the field GF(2^128) respectively. Sector will be deciphered in a
similar manner:

T_0 = E_K(N)

for (i in [0 .. 31])
    p_i = D_K(c_i + T_i) + T_i
    T_(i+1) = T_i * 2

Multiplication by two will be carried out as specified in the SISWG EME
document
("two" is actually the second element of the field GF(2^128)). Addition is
equivalent to XORing.

Note that E_K(N) is only calculated once per sector, thus XEX-AES is not
significantly less efficient than LRW-AES. But we avoid the inconvenience of
implementing general multiplication in GF(2^128) and can use a
single key.

Summary benefits (in comparison with LRW):
- provably secure,
- as efficient as LRW,
- single key,
- only utilizes multiplication by "two", XOR and cipher calls,
- parallelizable,
- probably unencumbered by intellectual property issues. NOTE: Phillip
Rogaway
  has filed a patent on OCB, of which XEX is a subroutine. Even if the
patent
extends to XEX, a free licence is available for GPL-licenced
implementations. On
the other hand, it is unlikely that mr Rogaway will claim IP rights
on XEX, as it is a Liskov-Rivest-Wagner cipher and they have made no IP
claims on the theoretical construction XEX is directly based on. However,
this needs clarification.

--- SECTION 2: LRW-AES-TBC mode ---

If XEX is of no interest, has the working group considered using tweak
block chaining
mode as specified in [LRW02] as the standard for LRW implementations?
That considerably increases the security of LRW, creating a CBC-like
scheme that
alleviates the "LRW has more data modification leakage than CBC" problem
previously
pointed out by Adam J. Richter in [Richt04].

--- References ---

[LRW02] M. Liskov, R. Rivest, and D. Wagner. Tweakable block ciphers.
Crypto'02
2002.

[Rog04] Phillip Rogaway. Efficient Instantiations of Tweakable
Blockciphers and
Refinements to Modes OCB and PMAC. Asiacrypt 2004.
http://www.cs.ucdavis.edu/~rogaway/papers/offsets.html

[Richt04] Adam J. Richter. LRW has more data modification leakage than CBC?
http://grouper.ieee.org/groups/1619/email/msg00242.html