LRW Key Derivation (formerly pink-herring)
I believe that I understand this and suggest this is not a case of
grandma writing her keys to the disk, but is a concerted effort of
someone to write K2 to the disk (without knowing the value of K2 or
this would be silly) two times with understandable modification. This
trivially leaks K2. Is this correct? OK, lets solve it.
I have personally discussed this with Phil Rogaway here at Eurocrypt.
The issue here is not LRW -per-se- but is one of key derivation.
Specifically, we can change the draft to add {a,b,c} as unequal but
standardized constants and use a single LRW key K. Traditional key
derivation would be -something-like- (using a more standard
terminology where AES_K(a) is ECB encryption of a using key K and ||
is concatenation):
K1 = AES_K(a) || AES_K(b)
K2 = AES_K(c)
This way, if K is written to the disk, this has no obvious way of
modifying K in the plaintext in the methods discussed below to leak K
or K2. Further, since K2 is a derived key, this key is expected to be
kept secret. (We can add informational / cautionary note that
implementations that page out their derived keys are not secure).
As a member of the committee, I would endorse such a change as prudent.
After having said that, Phil suggests that there may be no ways known
in the literature to prove security when the key to a cipher is
encrypted under that key.
Jim
On May 29, 2006, at 5:42 PM, laszlo@hars.us wrote:
> Landon raised a number of very important issues. I fully share his
> views.
>
> As I understand the encrypted-key weakness:
>
> C[2k] = T[2k] ^ K1(K2 ^ T[2k])
> C[2k+1] = T[2k+1] ^ K1(0 ^ T[2k+1])
>
> where T[2k+1] = T[2k]^K2, and K1(x) is AES encryption with the key K1.
> This gives:
>
> C[2k+1] = T[2k] ^K2 ^ K1(T[2k] ^ K2), that is
> C[2k] ^ C[2k+1] = K2
>
> In this light, the proposed text is too vague: "it may be possible to
> deduce the last 128 bits of the key from the ciphertext". It is not
> only "may be", but the two ciphertext blocks directly give K2.
>
> As Landon say, this works backward, too: T[2k] = T[2k+1]^K2. Now we
> need
> K2 in an odd indexed plaintext block.
>
> Landon is also right about the low-Hamming weight situation. In fact,
> with any 16-byte number H, if K2^H is stored on disk, and the adjacent
> block contains H, the attack still works:
>
> C[2k] = T[2k] ^ K1(K2^H ^ T[2k])
> C[2k+1] = T[2k] ^K2 ^ K1(H ^ T[2k]^K2)
>
> These invalidate my proposed key blending function #1: it CAN
> accidentally happen that K1 and K2' = K1^K2 is stored in consecutive
> blocks. Thanks, Landon, for the hint!
>
> XOR and + are too similar (they are the same if you have no carry).
> This
> was the reason I put "may still leak" next my proposed whitening
> function #3 (add a magic constant).
>
> The danger is larger than it seems. One might think that it is not
> likely to have {0,K2} or {K2,0} pairs stored accidentaly. If K2 gets
> swapped to disk by the OS from the memory, some time in the past or in
> the future a block of 0's could be there too, because this is the most
> often seen content of memory. We don't need K2 and 0 be seen in the
> same time! Even if it does not happen accidentally, an attacker could
> send you a large file (image, video) with lots of 0's. If you open it,
> it becomes very likely, that some 0's land in the right place, and
> that
> night an intruder could get his missing piece of information.
>
> To understand how realistic is an attack like this, we should consider
> if and how an attacker could convince the user to check his keys, and
> be exposed to the danger, that the memory will be swapped to disk in
> the wrong moment. I am thinking of an email, saying that "We
> discovered
> a security problem. If your key has its second last byte = 0xAB, the
> encryption can be broken. Please verify if it affects you, and change
> the key if it does." Since the email does not ask the user to disclose
> anything secret, or visit a dubious website, it does not look suspect.
> A super cautious user disconnects the PC from the web, reboots his
> machine, loads his key to see the "danger", he even could generate a
> new key, making him vulnerable to a swap-to-disk issue.
>
> Again, this is not a real attack, but some ideas, what a real attacker
> might employ. Don't you see real dangers here?
>
> As a user you must remember some unintuitive rules: never look at your
> keys with any unapproved software, don't generate keys with you own
> random number generator, even if you don't trust the supplied one,
> etc.
> Also, the encryption module has to come with specially written
> software
> for all operation systems imaginable. It has to lock critical memory
> from swapping to disk. You have to find this program when you need it:
> it cannot be stored on the encrypted disk, so you need a CD. It has to
> be shipped to you in a secure (tamper proof way), you have to be able
> to verify the authenticity of the CD, etc. This is complex, error
> prone
> and costs money. It is much simpler if the standard defines a key
> blending scheme, which makes it safe to look at, edit, generate and
> load your own keys.
>
> Laszlo
>
>> -------- Original Message --------
>> Subject: pay attention to P1619 so-called "Pink herrings"
>> From: "Landon Noll"
>> Date: Mon, May 29, 2006 6:03 pm
>> To: <stds-p1619@IEEE.ORG>
>>
>> Folks,
>>
>> Let us pay attention to some of these P1619 so-called "pink
>> herrings"!
>>
>>> I have not received any meaningful response to the issue of
>>> grandma storing her keys on an encrypted drive. The WG must
>>> have considered it the first time it came up ...
>>
>> I have not spoken up until now because I thought a "me too"
>> message would not add to the discussion until now.
>>
>> Draft 5, section C.5, 3rd bullet point states:
>>
>> * As with most cryptographic algorithms, LRW-AES transform
>> should not be used to encrypt its own secret-key. In
>> particular, when using LRW-AES to encrypt its own secret-key
>> followed by a block of zeros, it may be possible to deduce
>> the last 128 bits of the key from the ciphertext.
>>
>> BTW: I believe the cryptological attack might be possible
>> if the LRW-AES secret key is also preceded
>> by a block of zeros, not just if it is followed by zeros.
>>
>> I would like to explore how the LRW mode can be improved to mitigate
>> this problem.
>>
>> I would also like to explore the possibility of constructing attacks
>> where the LRW-AES secret-key is preceded or followed by a known and
>> chosen
>> non-zero (perhaps a low hamming weight (low number of 1 bits)) block
>> of data. I am not convinced that some form of interesting attack
>> with
>> a low hamming weight block is out of the question. The more general
>> problem might be somewhat wider than we suspect.
>>
>> chongo () /\oo/\
>> =-=
>> p.s. Editorial (rat-hole warning) side note:
>> Given the level of issues that some people saw in some
>> bad implementations and mis-uses of CBC mode, I'm still
>> amazed at how easy LRW passed the working group with this
>> kind of issue hanging over it.