Re: A New Triple-DES Key Wrap Algorithm

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.
 Second, given more time a cryptanalyst might find a better attack.  I do
not like to start a standard's life with known flaws.

I hope that others on this list will respond to your proposal.

Russ

At 05:26 PM 2/8/99 -0800, David Wagner wrote:
> I don't want to step on any toes, but frankly, I think all three of these
> are much too complicated for S/MIME.  I believe in fighting complexity and
> cryptographic bloat; complexity greatly introduces the potential for
> subtle bugs.
>
> S/MIME doesn't need to worry about encrypting 2^32 CEKs with the same KEK;
> this threat is just off the map, as far as I can tell.  (I've never sent
> 2^32 emails in my life, let alone to the same party.  And prudent
> cryptographic practice says you should change your KEK far more often than
> this, anyway...)
>
> I propose a much simpler algorithm.  In fact, it's so simple that it is
> _provably secure_.  (Oooh...)  To me, both of these features seem to greatly
> reduce the risk of surprising weaknesses.
>
> Basic idea:  You already have some shared keying material (KEK).  So just
> MAC the CEK using some shared key material, then encrypt the result using
> more of the shared key material.
>
> For the MAC, you can use SHA1-HMAC.  Secure if SHA1 satisfies some relatively
> plausible cryptographic properties.  See [1].
> (Or usse Triple-DES-CBC-MAC.  Provably secure if Triple-DES is, good for up
> to ~ 2^30 blocks or so.  See [2].)
>
> For encryption, you can use e.g. Triple-DES-CBC.  Provably secure if
> Triple-DES is, good for up to ~ 2^32 blocks or so.  See [3].
>
> You can also prove that the whole scheme (i.e. the composition of the MAC
> and the encryption) is secure (if both components are), if you use independent
> keys.  (Using the same key for the MAC and the encryption is a Bad Idea.)
> In practice, true independent keys are hard to arrive at.  But you can
> just derive as much keying material as you need from your KEK, and get
> keys which are computationally-indistinguishable from random.
>
> Thus, I suggest e.g. expanding the KEK with Triple-DES counter mode as far
> as needed to get a MAC key + an encryption key.  This is also provably secure,
> if Triple-DES is.
>
> Result: a whole scheme which is provably secure if Triple-DES (and maybe
> SHA1) are.  Seems like a potentially useful property to me...
>
> Of course, you have to ask what exactly is "proven" by the provable security
> results.  I claim that as far as I know, the proven security results will
> provide everything you need for S/MIME key wrapping.
> (But since you haven't specified the requirements precisely, or even at all,
> there are no guarantees.  Nonetheless I think the provable security indicates
> strongly that the basic approach is sound and plausible.)
>
> Of course, I'm also coming at this as an outsider, who's only recently started
> tracking the S/MIME stuff, so it's possible I've missed some requirement of
> the application.  But there are enough really sharp people reading this that
> if I made important oversights, I believe someone will call me on it...
>
> Regards,
> -- David
>
>
> [1]  Bellare, Rogaway, Krawczyk, ``Keying hash functions for message
>     authentication'', CRYPTO '96.
> [2]  Bellare, Kilian, Rogaway, ``The security of cipher block chaining'',
>     CRYPTO '94.
> [3]  Bellare, Desai, Jokipii, Rogaway, ``A concrete security treatment
>     of symmetric encryption: analysis of the DES modes of operation,''
>     38th FOCS (1997).