analysis and implementation of LRW

[Hal Finney]

To clarify a couple of points with regard to IEEE P1619 and LRW.

The original proposal which P1619 called "LRW" was actually a particular
concrete instantiation of a general construction from the LRW paper
(Liskov, Rivest and Wagner, Tweakable Block Ciphers, Crypto 02,
http://www.cs.berkeley.edu/~daw/papers/tweak-crypto02.pdf ).

The LRW construction was C = E_k(P xor h(T)) xor h(T) where E_k
is a block cipher with key k, T is the "tweak" and h(T) is a keyed
almost-xor-universal function.  P1619 instantiated E as AES and h as
galois field multiplication by a secret constant value: h(T) = k2*T
where T is the block number.  This is what they called "LRW" and it
has the weakness described, that if you have two consecutive blocks
containing k2 and zero, P xor h(T) can be the same for both of them.
This is what the group called a "collision", meaning two blocks whose
input to the AES is the same.  For this simple definition of h(T) as
k2*T a collision can reveal k2.

However this is not a general flaw in LRW, it is merely a problem with
this very simple instantiation of the construction.

In fact the replacement, which the group calls XTS, is also an instance
of LRW.  Based on work by Rogaway, the construction is the same as above
but the universal hash h(T) = E_k2(T1) * alpha^T2, where T1 are the
leftmost bits of the block number T and T2 are the rightmost bits (alpha
is a primitive root, and the math is finite field).  Rogaway proved that
this hash is universal and hence this is an instance of LRW and is secure.

So it is an over-simplification to say that P1619 found LRW insecure
and replaced it.  P1619 found that a particularly simple instantiation
of LRW had this problem when encrypting part of its key, and substituted
a more complicated version of LRW which appears to be largely immune to
the problem.  P1619 is still using LRW and it should still be considered
a very seminal and useful cryptographic construction.

It should be noted that almost no cryptographic proofs of security work
when arbitrary functions of the key are allowed as inputs to other parts
of the cipher, and at this point we must largely rely on heuristic and
informal arguments to see whether any weaknesses are real or merely
theoretical.

Hal Finney
PGP Corporation
P1619 Member

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com