Re: LRW Key Derivation (formerly pink-herring)
> The thing that worries me most with suggested changes is an endless
> stream of suggestions to address a variety of marginal concerns
So far I only heard about one suggested change.
I think the WG knows your opinion that the own-key-encryption issue is
marginal. There are at least two members, who disagree.
> delay this standard until the market overtakes it
This is a valid concern. In fact, it already has happened. There are a
large number of secure storage devices out there, which use different
encryption modes, and they will not be re-designed. The WG should have
produced a standard, years ago. It is not Shai's fault: several months
usually pass without any real discussion in the reflector. It delays any
progress. I think the P1619 WG already "missed the train".
> The issue with "encrypting its own key" stems from usage patterns that
> allow keys to go "into the wild"
I agree. The current draft requires the use of an XML document to archive
the key. This document contains the key, that is, the standard itself helps
the key to get into the wild. A user can and is tempted to look at his key,
just to see if it looks really random or not padded from a short one, etc.
I proposed removing the key archive part of the P1619. This would allow
implementers to architect a system, where the user does not know his key
(he needs to perform elaborate computation to get it).
However, the set goal of interoperability would suffer. If we want
encrypted data to be decrypted by another module, we need to standardize
some key encoding, from which the actual keys can be derived. This key
derivation is best done in the encryption module itself, so the true keys
never accidentally appear outside. Performing complex key decoding in an
insecure environment is not common, and cannot accidentally happen.
> Architectures that allow such usage patterns are so badly broken
True. A couple of trivial architectural requirements:
- The P1619 key archive document
1. Must not be prepared, edited or viewed with standard tools. Special SW
has to be provided for each common OS, for each version, for each processor
architecture, for each virtual memory architecture, etc. This SW has to be
supplied in an authenticated, temper proof form.
2. Key load has to be performed in such a manner, that critical memory
cannot accidentally swapped to the encrypted disk.
If the key is encoded in a standard way, these requirements can be dropped,
making the architecture much simpler and cheaper.
> store the key on an unencrypted media
This is a very real danger, although less of a concern, because typical
PC's operated by unsuspecting users have only one disk. However, if there
is an external encryption module for removable storage devices (not common,
because, e.g. many USB sticks have their own internal ciphers), and the
main disk is left unencrypted, a key appearing in the memory could be
exposed. This is one more argument not to let the user know or process his
key.
> only provide a false sense of security
We don't even tell the user about the key coding and its affects on the own
key encryption issue, we don't make any new claims, so where this false
sense of security come from? If there is one less obvious weakness, which
can be thwarted almost for free, we should do it: there will be fewer
innocent victims.
> mistakenly assume that the problem is due to the GF operations in LRW
> ...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)
In XEX we have
C[i] = K2(i) ^ K1(P[i] ^ K2(i))
C[j] = K2(j) ^ K1(P[j] ^ K2(j))
Since encryption by K1 hides any relation between the plaintexts, a
weakness is only there if
P[i] ^ K2(i) = P[j] ^ K2(j)
It only happens, if there is a 16-byte number H, such that
P[i] = K2(j)^H and P[j] = K2(i)^H.
What accidental user activity creates such plaintexts? He has to know the
location of both blocks on disk, encrypt and store them in the *other*
location. I don't think a "storage visualizer" would do it. It is much less
likely to happen accidentally than storing K2, which is available in the
key archive document and has to be loaded to the encryption module.
> an application that has
> the key can always do something that will expose it
Absolutely right. The issue is not if it *can* do bad things, but if it
does that accidentally, under normal, common mode of operations.
> key derivation
> has the added drawback that it may makes certification much harder
I don't think key encoding has an affect on certification. The issue is
only, what is stored in the key archive and loaded to the module. The
actual key is not affected at all.
>> Comments to this document shall be
>> posted before January 15th to the reflector
They have been posted, but no sufficient discussion followed. I don't
consider a comment, that the issue is a red herring to be part of a
discussion, until reasons are given. The email I am responding to is one,
with real arguments. I hope to get more like this.
Shai Halevi
Sent by:
stds-p1619@ieee.o To
rg SISWG <stds-p1619@IEEE.ORG>
No Phone Info cc
Available
Subject
Re: LRW Key Derivation (formerly
05/31/2006 03:53 pink-herring)
PM
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