Nice job with the security proofs, Shai, and in such a short time!
Thanks!
Some related notes:
>>The "LBA to I mapping" is not quite the right question to discuss, it should
>>be "tweak to T mapping".
That is true, but we all kept in mind that an I=0 leads to T=0, what
some consider insecure. I don't.
>>You should not be using K+1, K+2, etc, lest you run into related-key attacks.
I am not aware of any weakness of LRW in this regard. I was proposing to
use related K1 (AES) keys. Even if an attacker figures out the relations
between the drive keys, what kind of attack does it enable? Also, K,
K+1, K+2 was just an example to make my point clear. In practice I
would use the Galois multiplier to generate drive keys, like K1, K1+K2,
K1+K2^2,...
>>This discussion is valuable and should be written as a white-paper, but in my
>>view it has no place in the standard itself.
I understand that it is the current practice. Nevertheless, the
applicability, the limitations, the problem to be solved would be
important pieces of information in the standard. As I told in the
meeting, an engineer has to choose one of many possible algorithms for
stored data encryption, and we could give him a hand. All the details
should go to an accompanying document, but stating, that the standard
is intended to protect data at rest, and *not* in transit, is what I
missed. (I constantly have to explain the differences.) Implementing
P1619 on different ends of the wire represents different security
tradeoffs.
>>The reason that I withdrew EME was that no one had shown any interest in
>>using it
We badly need a long block encryption mode. EME looks expensive, so we
might not be able to implement it. XCB might be faster or cheaper, but
we need a cost/security tradeoff analysis. Also, the long block mode
has to be able to handle odd size LBA's without any additional
performance penalty. Again, XCB looks easier, and I have not seen a
modification of EME, which supports 520-bit LBA's. Before we could make
any decision, we need to know the licensing terms, which do not seem to
be cleared, either.
>>LRW is a single transform, and it takes a 48-byte secret key.
Is not it {K1,K2} = 32-byte? Only with AES-256 it would go up to
48-byte.
>>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.
Do you know a specific threat, or does only the security proof require
this?
>>introduce the notion of "compartments" within the key-scope, and use exactly
>>two indexes, namely the compartment index and the index of the block within
>>the compartment
Why not use three compartments: Drive_Index, LBA,
Cipherblock_within_LBA?
>>A different proposal is to use two 128-bit values for K2
We seem to have enough bits in I for partitioning: 64-bit drive ID,
48-bit LBA (up to 140,737 TB disks with 512-byte LBAs), 16-bit
cipher-block index, so one K2 key looks sufficient.
Laszlo
> -------- Original Message --------
> Subject: p1619 (disk): ciphertext-stealing, tweak-mapping, other
> From: Shai Halevi <[EMAIL PROTECTED]>
> Date: Mon, December 19, 2005 4:48 pm
> To: SISWG <[EMAIL PROTECTED]>
>
> 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).
>
