I finally found a few quite hours to think about this. The executive summary
of this (rather long) note is:
(a) The ciphertext-stealing extension can be shown to be "as strong as LRW"
(in some reasonable model). The proof essentially shows that anything that
an attacker can do when interacting with the extended mode can also be done
when interacting with the basic LRW.
(b) The "LBA to I mapping" is not quite the right question to discuss,
it should be "tweak to T mapping". (Recall that T is what you get when
multiplying I by Key_2.) I discuss below some of the proposals that where
raised and also suggest another alternative.
To make this note a bit less cluttered, I attach the discussion of these two
topics in two separate files (both ascii text). Below are some minor comments
about some issues that came up in the discussion.
[EMAIL PROTECTED] wrote:
> If the encryption is done in each individual disk drive, you just have
> to provide a different key for each. They can be K, K+1, K+2,...
You should not be using K+1, K+2, etc, lest you run into related-key
attacks.
> I could not explain my concerns clearly enough about small block
> encryption (~LRW) outside of the disk drive, so here I try it again.
> (Because of protests, we did not discuss this in the last P1619
> meeting.) [...]
> In this view, reasonable security is only achieved in practice, if the
> encryption is done internally in the disk drive. [...]
This discussion is valuable and should be written as a white-paper, but
in my view it has no place in the standard itself. (Is there such a thing
as "supporting documents" for a standard?)
> For the cases, where traffic analysis is a feasible attack, P1619 should
> revive one of the long block encryption modes.
The reason that I withdrew EME was that no one had shown any interest in
using it. We discussed in the past the possibility of writing another
standard (maybe p1619.2) that would describe other modes that are
"cryptographically strong" but have no aspects of interoperability.
We can put the wide-block modes in that standard.
Michael Torla wrote:
> Recall that I is the index within the scope of the second key K2.
> In a system with multiple K2's {K2_1 .. K2_n}
> [...]
> Unless scoping restrictions are documented in the specification,
> you have to assume the worst case deployment for K1 and K2. For
> worst case, I would assume that K1 applies to every disk drive
> deployed at the US Government, and that a different K2 is applied
> to every sector in every disk drive.
This usage should be disallowed by the standard. (I think that it is not
allowed by the current draft, and if I'm wrong then we need to change the
language so as to exclude it.) LRW is a single transform, and it takes a
48-byte secret key. The users of LRW should not care how this key is used
inside the transform. If they use several different keys, then all the
48 bytes have to be chosen "at random and independently" for each of these
different keys.
-- Shai
Roughly, the security analysis of LRW is done in a model with an
attacker that has arbitrary access to the encryption and decryption
routines for every block on the disk.
In this model, the attacker is successful if it can distinguish
between the following two vases:
(a) The system is indeed using LRW, or
(b) Every block of the disk is encrypted using a truly random
permutation, and moreover all these permutations are independent of
each other.
The LRW theorem tells you that any attacker that can distinguish these
two cases can also distinguish AES from a random permutation (with
about the same advantage). Since it is commonly accepted that no
feasible attacker can distinguish AES from a truly random permutation
with any noticeable advantage, this implies that no feasible attacker
can distinguish between cases (a) and (b) above. (BTW, that proof
works just as well when you have "tweak" value of zero.)
Why is any of it relevant to the security of LRW in our application?
The rationale is as follows: First, no realistic attacker would have
more information than the attacker in the mathematical model. So also
no realistic attacker can distinguish between cases (a) and (b). Which
means that whatever attack we are facing would be just as successful
if we were using case (b) to encrypt our disk rather than using LRW.
This is where the "security proof" of LRW ends. The rest is specific
to the implementations. That is, for a specific implementation you can
ask whether case (b) above provides sufficient security, and if it
does then that implementation can safely use LRW. As Laszlo explained,
there are cases where even (b) does not buy you enough security (e.g.,
from traffic analysis).
Looking at the extended LRW mode, it is easy to see that anything that
an attacker can do against this extended mode can also be done by the
attacker in the original mathematical mode. If the new attacker asks
to encrypt P_I P_{I+1} (with P_{I+1} a partial block), the attacker
from the model would first ask to encrypt P_I (and get C_I and C') and
then ask to encrypt the block (P_{I+1} C') thus getting C_{I+1}.
So also for the extended mode one cannot distinguish using the mode
from using truly random and independent permutations, and the same
rationale as above tells you that this implies security for the
extended LRW in our application.
The LRW paper [1] defines the mode
LRW(K1,K2; tweak; plaintext) = Cipher(K1; plaintext xor T) xor T
where T is computed from K2 and the tweak.
For this to be secure, you need that for any two different fixed values
tweak and tweak', if you choose K2 at random and compute T and T' then
(T xor T') is a random n-bit string. (They really need a slightly weaker
property, but no matter.)
In the current draft, the suggestion is to view the tweak as a sequence
number of the current block within the scope of the key (call it I), and
then compute
T = I * K2
where the product is defined as multiplication in the field GF(2^128).
This clearly has the needed property (even if you allow the case I=0).
In the discussion so far it was argued that computing T in this way
from the values that are available to the encryption device may not be
optimal. In particular, it was suggested that the tweak value should
consist of two or three indexes: the index of the current LBA (or
sector), the index of the current block in the sector, and maybe also
the index of the current disk.
I suggest that we introduce the notion of "compartments" within the
key-scope, and use exactly two two indexes, namely the compartment
index and the index of the block within the compartment. The expectation
is that access to different compartments be more or less random-access,
but blocks within a compartment will be accessed sequentially. (So the
compartment could be an LBA or LBA+disk index.)
I am not sure to what extent do we need to standardize the mapping
between these indexes and the information that is available to the
encryption device in the various settings that were discussed so far
(or in other settings that can dream of). My feeling is that we should
specify the mapping only for the case where there is one key per disk
(or virtual disk, or LUN, or volume, or whatever unit the encryption
device thinks it should manage).
Assuming that we indeed have these two indexes (with the usage assumption
as above), the suggestions that were discussed on the mailing list are
essentially to first compute
I = compartment-index * Some-number + block-index
and then to compute T = K2 * I as before, where Some-number is either
a big enough constant or something which is derived from the other
information that is available to the encrypting device. Between these
options I prefer to have Some-number as a constant that is specified
in the standard, because it make the standard less sensitive to usage
details (i.e., we don't need to have in the standard a long list of
"if you are in this environment then compute X, if you are in that
environment then compute Y, else compute Z").
Also, using a large fixed number for Some-number seems easy to optimize:
one stores both K2 and K2' = K2 * Some-number, and then computes
T = compartment-index * K2' xor block-index * K2 (this gives the right
answer if Some-number is a power of two and block-index does not exceed
Some-number).
A different proposal is to use two 128-bit values for K2, call them
K2a and K2b, and compute
T = K2a * compartment-index xor K2b * 2^{block-index}
(All the operations here are in the field GF(2^128).) The reason that I
propose to use K2b * 2^{block-index} instead of K2b * block-index is that
it makes it easier to compute the next T from the current one (here we
use the assumption that the block-index is incremented sequentially).
You no longer need to worry about carry bits and the like.
This would make the LRW key 64 bytes rather than 48 bytes. If people
think that this is big deal (and I don't see why it would be) then
perhaps there are simple ways of deriving both K2a and K2b from the
same 16-byte key K2 (but that requires additional study).
