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

From: "Don Johnson" <[email-masked]>
Date: Mon, 1 Feb 1999 10:29:14 -0500

Russ,

A few comments:
1. An integrity value of 16 bits is not enough to thwart a determined
attacker, especially if using a integrity verification oracle, that is,
toss values at it until success.
2. Given that TDES CBC is being done for messages, why not do two-pass TDES
CBC for the key wrapping (that is, do CBC over the key block and then do it
again)?  This avoids the need for code for a formatting method.  This forms
a block where every bit is dependent on every other bit.  A triple-DES key
is 168 bits of key; with parity bits, it is 192 bits.  Given a block of
384, this gives 192 bits for other stuff.  Put in some random bits, put in
a longer checksum, put in a length of the block,  put in other stuff,
depending on what attributes are desired.  The TDES blocksize being
64-bits, text attacks are not relevant as 2**32 blocks of key data will not
get encrypted under one set of TDES keys, and as it is random-appearing
data, is the best thing to encrypt anyway.

Don Johnson

Russ Housley <[email-masked]> on 01/31/99 06:17:38 PM

To:   [email-masked]
cc:   [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked] (bcc: Don
      Johnson/Certicom)
Subject:  A New Triple-DES Key Wrap Algorithm

All:

S/MIME 3 requires a function to encrypt one Triple-DES key in another.
Last March, I proposed an algorithm to wrap a Triple-DES content-encryption
key in a Triple-DES key-encryption key.  With a few minor modifications,
that algorithm was incorporated into the Cryptographic Message Syntax (CMS)
Internet-Draft.  Burt Kaliski recently discovered a flaw in that algorithm.
 In this message I propose a new algorithm.

Here is a summary of how S/MIME v3 will use the function.  The S/MIME v3
originator locally generates a random content-encryption Triple-DES key.
As the name implies, this key will be used to encrypt the message content.
Then, Diffie-Hellman is used to generate a pairwise Triple-DES key with
each message recipient, and the content-encryption key is encrypted under
the pairwise key.

The wrap algorithm is also used to support mail lists.  As setup, a
key-encryption key is distributed to a group of recipients.  Then, the
originator locally generates a random content-encryption Triple-DES key,
and the content-encryption key is encrypted under the pairwise key.  The
key-encryption key could be used for many messages to the group.

Please review the revised algorithm.  Once a key wrap algorithm is
selected, the S/MIME v3 specifications will be ready for review by the
Internet Engineering Steering Group (IESG).  Please do not propose
improvements that are covered by any issued or pending patents.

Thanks for your assistance,
  Russ

- - - - - - - - - -

The Triple-DES key wrap algorithm uses techniques similar to
Bellare-Rogaway Optimal Asymmetric Encryption Padding [OAEP].

X.1  Key Checksum

   The Fletcher checksum algorithm [FLETCHER] is used to provide an
   integrity check value.  The algorithm is:

   1.  Initialize two 16 bit integers, SUM1 and SUM2, to zero.
   2.  Loop through the octets of the content-encryption key, most
       significant (first) octet to least significant (last) octet.
       2a.  Create a 16 bit integer, called TEMP, by concatenating
            eight zero bits and the key octet.
       2b.  SUM1 = SUM1 + TEMP.
       2c.  SUM2 = SUM2 + SUM1.
   3.  Use SUM2 as the 16-bit checksum value.

X.2  Triple-DES Key Wrap

   1.  Adjust the parity bits for each of the three DES keys comprising the
       Triple-DES content-encryption key, call the parity adjusted key CEK.
   2.  Compute an integrity check value on CEK, called ICV, as described
above.
   3.  Let CEKICV = 0x18 || CEK || 0x00 || ICV.
   4.  Generate a 160-bit random value, called RAND.
   5.  Let H1 = SHA-1 ( RAND || 0x01 ).
   6.  Let H2 = SHA-1 ( RAND || 0x02 ).
   7.  Let MASK1 equal the most significant (first) 224 bits of H1 || H2.
   8.  Let MKEY = CEKICV XOR MASK1.
   9.  Let MASK2 = SHA-1 ( MKEY ).
  10.  Let MRAND = MASK2 XOR RAND.
  11.  Let MDATA = MRAND || MKEY.
  12.  Encrypt MDATA with the key-encryption key and CBC mode.  Use an IV
       with each octet equal to 0xA5.  The ciphertext is 384 bits long.

X.3  Triple-DES Key Unwrap

   The key unwrap algorithm is:

   1.  Decrypt the ciphertext using the key-encryption key and CBC mode.
Use
       an IV with each octet equal to 0xA5.
   2.  Decompose the plaintext result.  The most significant (first) 160
bits
       are MRAND, and the remaining 224 bits are MKEY.
   3.  Let MASK2 = SHA-1 ( MKEY ).
   4.  Let RAND = MASK2 XOR MRAND.
   5.  Let H1 = SHA-1 ( RAND || 0x01 ).
   6.  Let H2 = SHA-1 ( RAND || 0x02 ).
   7.  Let MASK1 equal the most significant (first) 224 bits of H1 || H2.
   8.  Let CEKICV = MASK1 XOR MKEY.
   9.  Decompose CEKICV.  The most significant (first) 8 bits are LENGTH,
the
       following 192 bits are CEK, the following 8 bits are PAD, and the
       remaining 16 bits are ICV1.
  10.  If LENGTH is not 0x18, then error.
  11.  If PAD is not 0x00, then error.
  12.  Compute an integrity check value on CEK, called ICV2, as described
above.
  13.  If ICV1 and ICV2 are not equal, then error.
  14.  Check for odd parity of each octet in each DES key that makes up the
       Triple-DES content-encryption key.  If any parity bit is incorrect,
       then error.

REFERENCES

   FLETCHER   Fletcher, J.  "An Arithmetic Checksum for Serial
              Transmissions", IEEE Transactions on Communication,
              Vol. COM-30, No. 1, pp. 247-252, January 1982.

   OAEP       Bellare-Rogaway Optimal Asymmetric Encryption Padding
              { What is the best reference? }

---

From: Russ Housley <[email-masked]>
Date: Mon, 01 Feb 1999 14:48:01 -0500

>toss values at it until success.

A slight restructuring could lead to 32 bits.  This would eliminate the
Length value and the Pad octet.  Any additional would lead to an additional
block.  This is already six blocks to protect three blocks of data.

>data, is the best thing to encrypt anyway.

Are you saying that the original formatting with double encryption would be
a cheaper way to resolve the problems raised by Burt kaliski?  Would the IV
for the second encryption be the ciphertext of the last block from the
first encryption pass?  If so, it needs to be carried somewhere.  Is
disclosure an issue?  Alternatively, can a differnt constant IV be used for
the second pass?

Thanks for the speedy review,
   Russ