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

From: Russ Housley <[email-masked]>
Date: Sun, 07 Feb 1999 16:07:18 -0500

All:

After a fair amount of open and public debate, I see three approahces to
Triple-DES key wrapping.  In this note, I list all three.  To keep this note a
resonable lenght, I have omitted the unwrap algorithm description.  The
alternative algorithms are listed in my oreder of preference.  The rationale
for my ordering is complexity.  The simplest is first, and the most complex is
last.  If the simple wrap algorithm meets the requirements, then what value
does the complexity add?

The S/MIME v3 specifications will include the selected Triple-DES key wrap
algorithm as well as a variant for wrapping RC2 keys (40-128 bit keys).

Please review the algorithms.  Please do not propose improvements that are
covered by any issued or pending patents.

Thanks for your assistance,
  Russ

= = = = = = = = = = 

WRAP ALOGRITHM #1:  DOUBLE ENCRYPTION

A.1  Key Checksum

The CMS Checksum Algorithm is used to provide an content-encryption key
integrity check value.  The algorithm is:

1.  Compute a 20 octet SHA-1 message digest on the 
    content-encryption key.
2.  Use the most significant (first) eight octets of the 
    message digest value as the checksum value.

A.2  Triple-DES Key Wrap

1.  Set odd parity for each of the DES key octets comprising 
    the content-encryption key.
2.  Compute a 8 octet key checksum value on the content-encryption
    key as described above.
3.  Concatenate the key checksum value and the content-encryption key.
    The result is four 8 octet blocks: B1, B2, B3, and B4.
4.  Encrypt in CBC mode the four blocks using the key-encryption key.
    Use an IV of all zeros.
5.  Reverse the order of the four ciphertext blocks.  The resulting
    order is B4, B3, B2, and B1.
6.  Encrypt the four blocks a second time.  Encrypt in CBC mode 
    using the key-encryption key.  Use an IV of all zeros.

WRAP ALOGRITHM #2:  MASK AND ENCRYPT

B.1  Key Checksum

The CMS Checksum Algorithm is used to provide an content-encryption key
integrity check value.  The algorithm is:

1.  Compute a 20 octet SHA-1 message digest on the 
    content-encryption key.
2.  Use the most significant (first) eight octets of the 
    message digest value as the checksum value.

B.2  Triple-DES Key Wrap

1.  Set odd parity for each of the DES key octets comprising 
    the content-encryption key.
2.  Compute a 8 octet key checksum value on the content-encryption
    key as described above.
3.  Generate an 8 octet random number: RAND.
4.  Let H1 = SHA-1 ( RAND ).
5.  Let H2 = SHA-1 ( H1 ).
6.  Let MASK equal the most significant (first) 32 octets of H1 || H2.
7.  Let KEYICV equal the content-encryption key concatenated with
    the key checksum value.
8.  Let PLAIN = RAND || ( KEYICV XOR MASK ).
9.  Encrypt PLAIN in CBC mode using the key-encryption key.
    Use an IV of all zeros.

WRAP ALOGRITHM #3:  OAEP AND ENCRYPT

C.1  Key Checksum

No explicit ckecksum algoritm is needed.  The OAEP processing provides 
the necessary integrity.

C.2  Triple-DES Key Wrap

1.  Set odd parity for each of the DES key octets comprising 
    the content-encryption key, called CEK.
2.  Let CEKPAD = 0x18 || CEK || 0x0000000000000000000000.
3.  Generate a 160-bit random value, called RAND.
4.  Let H1 = SHA-1 ( RAND || 0x01 ).
5.  Let H2 = SHA-1 ( RAND || 0x02 ).
6.  Let MASK1 equal the most significant (first) 36 octets of H1 || H2.
7.  Let MKEY = CEKPAD XOR MASK1.
8.  Let MASK2 = SHA-1 ( MKEY ).
9.  Let MRAND = MASK2 XOR RAND.
10. Let MDATA = MRAND || MKEY.
11. Encrypt MDATA with the key-encryption key and CBC mode.  Use an IV
    with each octet equal to 0xA5.  The ciphertext is 56 octets long.

---

From: David Wagner <[email-masked]>
Date: Mon, 8 Feb 1999 17:26:59 -0800 (PST)

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

---

From: Russ Housley <[email-masked]>
Date: Tue, 09 Feb 1999 12:02:16 -0500

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