Mart, which document are you referring to? The last draft (dated Dec-20
2005) doesn't have section 5.2.1 and doesn't describe any optimizations.
As for your question, the current spec defines the tweak as
i = some-number + block-position-in-sector
where some-number is something which is computed once per sector (which
is a power of two, at least the number of blocks in a sector), and
block-position-in-sector is the index of the block within the sector,
starting at zero. The standard trick for optimizing the computation
of K2*i, is to prepare a table T[] (example for 32-block sectors):
T[0] = K2
T[1] = 3*K2
T[2] = 7*K2
T[3] = 15*K2
T[4] = 31*K2
Then, you initially compute some-number*K2 using a full multiplication.
Once you have i*K2, computing (i+1)*K2 is done as follows:
1. Let s = index of the leftmost '1' bit in i+1 (must be between 0 and 4)
2. compute (i+1)*K2 as i*K2 xor T[s]
For the case where each value of K2 is used only for one sector (as
in your question), you can compute T in an on-line fashion by setting
T[0] = K2, and
T[s+1] = 2*T[s] xor K2
> It has to be noted, that XEX as specified in
> http://grouper.ieee.org/groups/1619/email/msg00610.html does not suffer
> these drawbacks and it seems that XEX is considerably more efficient
> than LRW in multiple key mode.
The update in XEX is somewhat more efficient than in LRW, but not really
"considerably more efficient". I proposed a different optimization with
the same performance characteristics a few weeks ago (see end of message
http://grouper.ieee.org/groups/1619/email/msg00528.html) which drew
distinctively non-enthusiastic reactions. People appear to think that
the difference in performance is not large enough to bother with this
change.
-- Shai
Mart Somermaa wrote:
Suppose we have a key derivation function f, that, given a global key GK
and sector index i, generates a unique sector key K_i
f(GK, i) = K_i
that will be used to key e.g. LRW-AES.
In this case, LRW key scope is only a single sector (generally 32
blocks). Hence, the table based optimisation for multiplication in
GF(2^128) do not work -- multiplication table (as described in LRW draft
section 5.1) scope is also only 32 blocks. Also, the tweak increment
optimisation (ibid. 5.2.1) is useless for the same reason.
Are there ways to optimize multiplication in GF(2^128) even when key
scope is a single sector?
It has to be noted, that XEX as specified in
http://grouper.ieee.org/groups/1619/email/msg00610.html does not suffer
these drawbacks and it seems that XEX is considerably more efficient
than LRW in multiple key mode.
