Re: LRW Key Derivation (formerly pink-herring)
james hughes wrote:
> [...]
> 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. [...]
I object to adding key derivation to the standard. This will burden
the implementations with yet another construct whose only purpose it
to solve an irrelevant problem (see more below).
The thing that worries me most with suggested changes is an endless
stream of suggestions to address a variety of marginal concerns, that
will delay this standard until the market overtakes it and makes it
irrelevant. If that happens, I believe that we will see a proliferation
of half-baked modes in various devices on the market that are
significantly weaker than LRW. I believe that the primary goal of this
working group should be to avoid this outcome, and that to do so we
should adopt an approach that would let us get this standard voted on
this year.
Back to technical discussion, I will try yet again to explain why I don't
believe that we should address this concern in the current standard. (I'm
pretty sure that I already presented these arguments in the past, but
here I go again..)
The issue with "encrypting its own key" stems from usage patterns that
allow keys to go "into the wild" (i.e., to an uncontrolled environment).
Once you do that, you don't know if whatever is out there in the wild
won't give you your key and ask that you encrypt it. Sound key-management
systems never allow this option, and therefore they will never face that
problem. If we try to "solve" that problem and make the claim that the
standard provides protection for such usage patterns, we will be lying.
Architectures that allow such usage patterns are so badly broken that
no low-level standard such as ours will be able to help. To be secure, an
application that operates in such architecture must constantly be aware
of all the low-level transformations that use keys and make sure that it
avoid all the bad interactions that may happen with its use of the key.
The first obvious example of things that can go wrong is that "whatever
is out there" can store the key on an unencrypted media. (There is no
reason to believe that it even knows what media is encrypted and what
media is not.) Similarly, a user can expose the cleartext key inside the
memory of his PC or leak it via a host of other OS or application related
weaknesses. In this respect, claiming that we provide protection for this
case will only provide a false sense of security.
Another example of "bad things to do with the key" is the issue with LRW
and K2, and some people mistakenly assume that the problem is due to the
GF operations in LRW. So one might propose, say, switching to the XEX
mode that Mart Sõmermaa proposed (in his email from Jan/6/2006 9:06AM).
In that mode, the value that is used for xor is derived from AES(i)
rather than K2*i as in LRW. This mode offers very similar performance
and security characteristics to LRW (see Mats' email for more details).
So XEX does not use GF operations, but does it solve the "key in the
wild" problem? No, since the exact same problem as in LRW happens if
"whatever is out there" stores two blocks that differ by some function
of AES(i), which it can do since it knows the key. (And it may not be an
unreasonable thing to do too, for example when this application is some
form of storage visualizer and knows about the low-level index i.) In
this case, just like for LRW, an attacker may be able to deduce the value
that is used for xor.
What about CBC? Well, here the the application need not do anything
special to break things. Indeed, the level of security that CBC offers
in this context is comparable to what you get from LRW *after the key K2
was leaked*. (Remember that once K2 is leaked, you are left with
something equivalent to ECB encryption.)
We can go invent yet more complex and more expensive constructs to solve
this issue, but the fact of the matter is that an application that has
the key can always do something that will expose it or interact badly
with whatever mode of operation we are using.
Thus I strongly believe that there is no reason for us to change the
draft. It offers a reasonable level of security for architectures that
handle their keys the way keys should be handled. Broken architectures
must either count on the specific applications to behave nicely, or fall
back to the level of protection provided by ECB.
As one final comment, I think that devising key derivation schemes to
"solve" the K2 issue is an extremely bad idea. In addition to my general
objections to changing the draft standard at this point, key derivation
has the added drawback that it may makes certification much harder (see
the discussion in 1619.1).
-- Shai
p.s. I would like to draw your attention to the minutes of the meeting
from Dec-2005 (see message by Fabio Maino from 12/12/2005 8:36 PM):
> [...]
> PROCEDURE
> ---------
> By December 25th Serge will update the doc with Laszlo's comments as
> instructed today during the meeting. Comments to this document shall be
> posted before January 15th to the reflector. The group will discuss the
> comments and decide to either reject or accept the comment. No more
> comments will be accepted after january 15th, and by January 25th Serge
> will prepare a final version of the doc to be voted by jan. 30th the
> group over email (one vote per company, at least half of the active
> members should vote).
>
> Odd Length LBA
> --------------
> The issue of addressing odd length LBAs has been discussed. The sense of
> the room is that it is not trivial to be addressed now, but everybody is
> encouraged to pos comments and proposals on how to address this issue.
> [...]
The algorithmic change for "odd length LBA" was since incorporated into
the draft standard, and we are now six months later. The fact that we are
still arguing about the algorithm makes me very worried about missing the
train with this standard.
james hughes wrote:
> 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