ietf-smime
[Top] [All Lists]

Re: A New Triple-DES Key Wrap Algorithm

1999-02-16 19:50:45
Just for the record, text attacks such as Burt mentioned were discussed by
Coppersmith, Johnson and Matyas in their paper on CBCM mode of Triple DES
as a justification for considering it in ANSI X9.  They might have been
known before that, but the ref in the HAC is to that paper, so I know of no
earlier ref.

Don J.





"Bob Jueneman" <BJUENEMAN(_at_)novell(_dot_)com> on 02/16/99 08:53:37 PM

To:   daw(_at_)cs(_dot_)berkeley(_dot_)edu, housley(_at_)spyrus(_dot_)com
cc:   cme(_at_)ACM(_dot_)ORG, berson(_at_)anagram(_dot_)com, 
bschanni(_at_)BayNetworks(_dot_)com,
      kent(_at_)bbn(_dot_)com, pcain(_at_)bbn(_dot_)com, 
mhetzel(_at_)bell-labs(_dot_)com,
      brickell(_at_)certco(_dot_)com, djohnson(_at_)certicom(_dot_)ca, 
schneier(_at_)counterpane(_dot_)com,
      denning(_at_)cs(_dot_)cosc(_dot_)georgetown(_dot_)edu, 
smid(_at_)csmes(_dot_)ncsl(_dot_)nist(_dot_)gov,
      omura(_at_)cylink(_dot_)com, 
dickie(_at_)EMPIRE(_dot_)eclipse(_dot_)ncsc(_dot_)mil,
      carlisle(_dot_)adams(_at_)entrust(_dot_)com, paulv(_at_)entrust(_dot_)com,
      Blake(_dot_)Greenlee(_at_)greenlee(_dot_)com, 
ietf-smime(_at_)imc(_dot_)org,
      cjwagne(_at_)missi(_dot_)ncsc(_dot_)mil, jis(_at_)mit(_dot_)edu, 
merkle(_at_)parc(_dot_)xerox(_dot_)com,
      BSnow(_at_)radium(_dot_)ncsc(_dot_)mil, burt(_at_)rsa(_dot_)com, 
ekr(_at_)rtfm(_dot_)com,
      jlinn(_at_)securitydynamics(_dot_)com, ams(_at_)terisa(_dot_)com,
      rivest(_at_)theory(_dot_)lcs(_dot_)mit(_dot_)edu, 
balenson(_at_)tis(_dot_)com, denny(_at_)tis(_dot_)com,
      acc(_at_)tycho(_dot_)ncsc(_dot_)mil, jhs(_at_)tycho(_dot_)ncsc(_dot_)mil, 
smatyas(_at_)us(_dot_)ibm(_dot_)com,
      desmedt(_at_)uwm(_dot_)edu (bcc: Don Johnson/Certicom)
Subject:  Re: A New Triple-DES Key Wrap Algorithm




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!")...