David,
The reason why I got interested in this subject at all was that I realized that
within
Novell's cryptographic architecture we wrap all sorts of keys, and when a
possible
attack was pointed out I became concerned.
I understand Russ Housley's point about wanting to solve this problem for
S/MIME --
that is his charter, and he wants to deliver a product. Admirable dedication.
And I
certainly agree with you that there are other, probably more effective ways to
compromise S/MIME. than by mailing a billion keys around!
But as a vendor, I don't want to have to solve the key wrapping problem one way
for S/MIME, plus N other ways for the next N protocols to come along.
Believe me, it is very tough to get the attention of the real experts in this
area,
and so once the problem was raised, I think we should solve it as best we can,
once and for all. The S/MIME spec will then make a convenient point of reference
for something that was done right.
For that reason, then, I would tend to dismiss any and all arguments about
whether
some particular attack might or might not be feasible in an S/MIME context --
that type of
subtlety is exceedingly hard to get right, and besides I want a more general
purpose
solution.
Although Steve Kent's argument about the cost of changing keys often is quite
valid,
your argument about wanting to refresh your KEKs more often is NOT necessarily
the way to improve security. It depends upon the threat.
Most approaches to brute force attacks try to speed up the number of key search
operations that can be done simultaneously or in parallel, e.g., the recent
success
at the RSA conference of the EFF's Deep Crack engine in combination with lots
of
distributed computers, all working on the same challenge cipher.
But there is another approach, which I call the vacuum cleaner technique, where
you
don't target any specific key, but rather you suck up million or billions of
keys and
process all of them simultaneously. With this approach, for every new key that
is
tried, either singly or in parallel, the attacker looks at billions of
ciphertexts to see
if the result of encrypting a chosen plaintext with a given key matches any one
of the
ciphertexts that have been collected. (This assumes a chosen plaintext attack
is
feasible, which is the usual conservative assumption.) In other words, don't
look for
a needle in a haystack -- take the entire haystack.
After all, if I am trying to steal credit card numbers, I don't care much whose
credit card it is --
I'm not trying to target Bill Gates or Donald Trump specifically -- I'll settle
for yours or
almost anybody else's.
In this scenario, increasing the number of KEKs that are used actually
_increases_
my chances of success, for it gives me that many more ciphertext examples to
look at,
assuming that success is measured in terms of how many keys are cracked in a
given amount of time, rather than how long it takes to crack a specific key.
Bob
David Wagner <daw(_at_)cs(_dot_)berkeley(_dot_)edu> 02/15/99 03:42PM >>>
David:
I had the same reaction to the 4 billion wrapped keys; however, there are
two reasons why we should address this issue. First, when mail list keys
are used, the same KEK is used to encrypt CEKs for every message sent to
the mail list. Depending on the activity on the mail list ad the
cryptoperiod of the KEK, the 4 billion wrapped keys might actually happen,
especially if severs ever communicated with each other using this facility.
Ok. I certainly support a conservative approach!
But I must say, my feeling is that if you ever encrypt 2^32 session keys
under the same KEK, "birthday"-style weaknesses will be in the noise:
you'll be in far-deeper trouble, because that KEK will start to look like
an awfully fat target.
In this scenario, I don't think the adversary is going to bother attacking
the crypto (especially when this only divulges partial information about
two session keys).
Instead, he'll go after your KEK by other means (bribe your cleaning service
to Trojan your computer, suck signal off the power lines, send a TEMPEST
van in your direction, break in to your computer, social engineer his way
into your secure facility, take a job at your company as a janitor, etc.)
The right defense is to refresh your KEK's more frequently. (For instance,
IPSEC expires keys based not just on time but also on # of blocks encrypted.)
I'd argue that this is just prudent cryptographic hygiene. And once you do
this, the cryptanalytic attacks go away.
Taking this up a level, my initial reaction is that ietf-smime is optimizing
for the wrong quantity.
Maximizing the number of session keys you can encrypt under the same KEK
is a second-order concern. It seems much more important to try really hard
to reduce the risk that someone finds a subtle bug in your protocol.
(And, if what I've heard is correct, subtle protocol properties are exactly
the reason ietf-smime is devoting so much effort to key wrapping techniques.)
If you accept this, then the complicated constructions proposed earlier
may be exactly the wrong way to go; simplicity is arguably the most crucial
quantity to optimize for.
(And some provable security results can't hurt, either.)
(Of course, simplicity is only a heuristic. For instance, Boyko's recent
results on all-or-nothing transforms look very promising, and deserve more
investigation. Even though the construction is not quite as simple as e.g.
encrypt-and-MAC, provable security results are a great way to reduce the
risk of subtle protocol failures.
[One warning is that the proofs depend on the "random oracle" model and
thus do not necessarily transfer to real-world scenarios -- but they are
still very useful as validation that the basic approach is likely to be
sound.])
Second, given more time a cryptanalyst might find a better attack. I do
not like to start a standard's life with known flaws.
Yes. This is a very good point, and normally this would be a very telling
criticism. There's a saying: "attacks always get better".
However, I feel that this case is different. Remember, Kaliski's attack
(did I get the author right?) meets the proven lower bounds on security
very closely. I would argue that in fact the existence of the attack
should reassure us that the proofs of security were on the right track,
rather than raising concerns that better attacks might be "out there".
I hope that others on this list will respond to your proposal.
Me too... As a newbie to ietf-smime, I would definitely welcome feedback
(and/or criticism: even "you have no clue, go away!")...