Subject: RE: A New Triple-DES Key Wrap Algorithm

From: Russ Housley <[email-masked]>
Date: Mon, 15 Feb 1999 09:03:17 -0500

Burt:

Thanks for the pointer.  I found the article very interesting.  I did not
try to comprehend the proofs, but I found the AONT discussion very useful.

Has the double-encryption approach that we are considering been analyzed as
an AONT?  If so, how does it stack up when compared to OAEP?

Russ

At 10:52 AM 2/12/99 -0800, Burt Kaliski wrote:
>FYI, Victor Boyko has just posted his research results showing how OAEP
>enhances the security of symmetric encryption. See
>http://theory.lcs.mit.edu/~boyko/aont-oaep.html.
>
>-- Burt

---

From: David Wagner <[email-masked]>
Date: Mon, 15 Feb 1999 14:42:01 -0800 (PST)

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

---

From: Stephen Kent <[email-masked]>
Date: Tue, 16 Feb 1999 14:49:34 -0500

David,

The particular heavy use of the KEK that Russ cited is a side effect of the
mailing list key management approach adopted by MSP, and later by S/MIME.
It is driven by a strong desire to NOT distribute KEKs more frequently, or
on a piecemeal basis, because of the costs of doing so.  So, in this case,
I think we just have to live with this as a problem constraint for the
S/MIME environment.  However, I agree that there may be lots of better ways
to go after the KEK in these instances, givens its widespread distribution.

steve