Feature creep
Shai,
I agree: P1619 should move expeditiously to ballot.
Coming to closure over the feature set addressed by a draft standard produces disagreement in almost every working group ... that is quite common. Then a simple vote is required to move ahead. (Note that voting is not required when there is no dissenting opinion. We do not vote for the sake of voting.)
But regardless of the project/standard, there are two reasons to move ahead to ballot soonest.
First, a timely standard is much more likely to gain wide acceptance than one produced over years. Waiting to get more features included may result in a standard that is altogether a failure, gaining nothing for the additional features that are harder, take longer to incorporate. Then not only is the effort of the working group lost, but society, the market may be deprived, as you point out, of the basic benefits of the standard. Quoting Patton: "A good plan violently executed now is better than a perfect plan next week".
Second, standards are not chiseled in stone. Not only **must** they be re-balloted after five years, they **may** be re-balloted much earlier! How much earlier depends on the speed of the working group, not the IEEE. Missing features or aspects not included in the first ballot can be added and balloted a year later, or at some other time sooner or later depending on the speed of the group. This is not a once-in-a-lifetime event. Standards are not a fire-and-forget weapon. As soon after balloting as questions arrive on the working group's doorstep, and responses are made that modify the original standard, the new standard becomes the balloted standard plus the responses. When there are enough such modifications or a few very significant ones, then re-balloting is required. In short, a standard is a living document. The thought of getting everything in at first ballot is unrealistic and probably destructive.
The longer P1619 lingers, the more its value diminishes, eventually being extinguished completely. This is true for all standards projects except those few that anticipate technology, and arrive just in time (like 802.11).
Jack
-----Original Message-----
From: stds-p1619@ieee.org [mailto:stds-p1619@ieee.org] On Behalf Of Shai Halevi
Sent: Wednesday, May 31, 2006 3:53 PM
To: SISWG
Subject: 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