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

From: "Bob Jueneman" <[email-masked]>
Date: Fri, 26 Feb 1999 11:38:19 -0700

Russ:

You are correct, of course.  The question, then, is whether
we should just go to the OAEP-type wrapping and not have
to worry about changing IV's and how to convey them.
That would be my recommendation.

On a slightly different issue, several times I have strongly urged
that in order to avoid the problem of having N-squared algorithm
IDs for all of the various combinations of CEK and KEK algorithms,
key lengths, and other miscellaneous data, that we first wrap
the CEK in a descriptive ASN.1 structure that describes the 
the CEK algorithm/key, and then do the wrapping operation.

However, although I've raised this issue several times and indicated
our strong desire to solve the key wrapping issue once and for all,
you have neither incorporated the idea or argued against it,
so I don't know where you stand.

Obviously anyone who is processing certificates is going to have to 
have an ASN.1 decoder, and Dr. Acar, who wrote ours, assures 
me that the performance implications would be negligible compared to
almost any encryption operation.

Assuming that is the case, the only reason I could see for not doing 
it would be concern about the increase in wrapped key size,
or some lingering not-invented-here bias against ISO/ITU/X.500
mechanisms.  I certainly hope it isn't the later.

Is there anything in the existing protocol that is rigidly sensitive to 
the size of the wrapped key?  If so, then that is a problem that 
probably ought to be addressed.

If not, then I believe the architectural benefits would far outweigh
any increase in the size of the wrapped key.

Bob

>>> Russ Housley <[email-masked]> 02/26/99 10:51AM >>>
Bob:

You raise an interesting point, but I think it can be easily solved by a
random IV for the first encryption. Of course, this makes the result one
block longer.  And, we would need a different IV for each wrapping.

Russ

At 10:50 AM 2/22/99 -0700, Bob Jueneman wrote:
>Russ,
>
>There is a possible attack on the double encryption wrap algorithm 
>that is a result of the constant IV construction. For that reason, I would
>strongly prefer the OAEP construction. Although it may look complicated
>because there are more steps, the number of line of code is really of no 
>consequence at all, but the execution time is important for performance.
>
>Also, I continue to insist that we should not invent n-squared algorithm 
>IDs for every possible combination of CEK algorithm and key length
>plus KEK algorithm and key length. Instead, I would _greatly_ prefer to 
>first wrap the CEK in a ASN.1 structure that defines the CEK algorithm 
>and key length, then whiten that structure with OAEP, encrypt the resulting
>string with the KEK algorithm, and then provide generic instructions as
>to how to decode the result, either by wrapping the entire wrapped key 
>blob in ASN.1 (preferably) or some other way.
>
>Here's the attack on the double-encryption wrapping:
>
>Although most exhaustive search engines divide up the search process
>across multiple machines in order to find a single key as quickly as possible
>(e.g., the series of RSA challenge ciphers), there is another approach
>based on the use of an associative memory that I wrote up back
>in the '70's but never published.  I call it my "vacuum-cleaner" attack.
>
>Assume for the sake or argument that there are lots and lots of keys
>that have been or will be used to encrypt a known plaintext or 
>stereotyped message.  (This is a standard assumption in cryptanalysis.) 
>Actually, the attack will succeed with a somewhat weaker condition --
>it isn't necessary to actually know the plaintext -- it is sufficient that
>the plaintext be unvarying.
>
>Let's also assume that each key is used for some interesting purpose --
>sufficiently interesting that it may not be necessary to crack each and every
>key -- just a few would be useful.  For example, if I were trying to carry on 
>a credit card attack, I don't have to find the key for Bill Gates' or 
>Donald Trump's credit card -- just about anyone's will do, and the more 
>the merrier.
>
>So for every new key that I have the engine try, I contrive to compare 
>the result of encrypting the known plaintext against millions of valid 
>ciphertexts that have been intercepted, looking for a match.  Assuming 
>an effectively inexhaustible supply of ciphertexts is available, this attack 
>multiplies the effectiveness of the key search engine by an order of a million
>or more, depending on the size of the associative memory that is available.
>
>(The use of an associative memory isn't essential -- it was just a gedanken
>experiment to speed up the comparison process without requiring sorting.)
>
>Two things should be noted.  First, this attack is independent of the KEK 
>encryption algorithm used, assuming a fixed block size.  In other words, 
>this would apply to single-DES, triple-DES, umpty-DES, 2048-bit RSA,
>or whatever, assuming a constant session key and constant padding.
>
>Second, the attack is also independent of the length or type of session 
>key that is used, except that the yield is a Birthday Problem function of the
>length of the key.  But given a fixed input, i.e., no random whitening or 
>changing IV, then two or more matching outputs must imply a matching
>session key.  
>
>This leads to a rather surprising result -- even if the KEK performs double 
>encryption using triple-DES (or any other algorithm without whitening)
>to wrap a 40 bit key, two matching session keys can be found with 
>approximately 50% probability after only 2^20 or a million or so session 
>keys have been generated.
>
>Perhaps more surprisingly, at least to people who haven't been down this path,
>changing session keys more rapidly may hurt more than it helps -- it just 
>exposes that many more keys to attack. Changing the session key often 
>in the middle of a session may help limit the ability of the attacker to 
>access the entire message, and hence limits the attacker's "take," but it 
>increases the chances that a potentially interesting fragment of text 
>may be exposed.
>
>I'm sure that someone would observe that sending even a million content 
>encryption key encrypted in a constant KEK would be extremely unlikely
>in an S/MIME context, but whether that would really be true would require
>a more subtle, protocol-dependent analysis than I would care to make,
>and in addition I very much want to standardize on one key wrapping 
>algorithm that is protocol independent, and not just for S/MIME.
>
>Obviously the above attack can be defeated by prepending some 
>additional randomness or by changing the IV. But is also what the OAEP
>approach does, and rather more elegantly.  By the time we have to add
>either a changing IV or some additional randomness (how much would be
>required would have to be decided) the length would probably be close
>to that required for OAEP, which is a much more general solution.
>
>In my mind, at least, some extra bytes in the wrapped key is no big deal,
>but I would like the efficiency to be a good as possible. Triple-DES is 
>expensive enough in terms of computational efficiency in software, 
>especially in terms of the initial key expansion, and doing it twice 
>would be worse yet.
>
>Because the new export regulations permit the use of double the key length 
>used for data encryption to be used for key encryption, we are going to be
>using triple-DES in encrypt-decrypt-encrypt mode with only two keys
(A-B-A) for
>key wrapping of all export-grade CEK keys.
>
>This can be optimized by saving the key expansion of the first encryption,
and 
>then reusing it for the final encryption.  This technique could
potentially be 
>extended to the double encryption wrapping algorithm, by saving the key  
>expansion used for all three steps, but in order to do that the 
>"double-triple-DES"
>algorithm would probably have to be a single algorithm that is invoked --
>it would be quite difficult to securely save state across two separate 
>encryption
>operations.
>
>So my preference, as I said earlier, would be to wrap the CEK in ASN.1, 
>whiten with OAEP, and then encrypt using whatever KEK algorithm and 
>key length is required, so we don't have to keep re-analyzing this problem 
>for every new CEK or KEK algorithm or key length.
>
>If we can define appropriate algorithm IDs, I'm willing and eager to adopt
such
>a standard for  _all_ wrapped keys generated and used within our Novell 
>International Cryptographic Infrastructure (NICI), even before S/MIME v3 
>progresses to a full standard.  I'd be willing to assign an algorithm OID 
>from the 
>Novell tree, or we could probably get one from PKCS if there would be any 
>problem getting one assigned by the IANA.
>
>Regards,
>
>Bob
>
>
>> Russ Housley <[email-masked]> 02/20/99 02:17PM >>>
>All:
>
>Right now, I am leaning toward the double encryption wrap algorithm.  I
>think it will be easy to implement, and it yeilds a shorter result that the
>OAEP method.  To convince myself that it was easy to implement, I did an
>implementation.  It took me about two hours while watching an old Jimmy
>Stewart movie.  Of course, I already have SHA-1 and Triple-DES CBC
>routines.  S/MIME v3 will require these algorithms for other capabilities
>besides key wrapping.
>
>If someone else is willing to do an implementation, I would like to compare
>results.  This will allow a test vector to be included with the algorithm
>description.
>
>Does anyone have any strong objections to the double encryption wrap
>algorithm being selected?
>
>Russ
>
>
>>WRAP ALOGRITHM #1:  DOUBLE ENCRYPTION
>>
>>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.
>>
>>Triple-DES Key Wrap
>>
>>1.  Set odd parity for each of the DES key octets comprising 
>>    the content-encryption key, call the result CEK.
>>2.  Compute a 8 octet key checksum value on CEK as described above,
>>    call the result ICV.
>>3.  Let CEKICV = CEK || ICV.
>>4.  Encrypt CEKICV in CBC mode using the key-encryption key.  Use
>>    an IV of 0xc302e3c1ad8bb738.
>>5.  Reverse the order of the ciphertext octets.  That is, the most
>>    significant (first) octet is swapped with the least significant
>>    (last) octet, and so on.  Call the result TEMP.
>>6.  Encrypt TEMP in CBC mode using the key-encryption key.  Use 
>>    an IV of 0x61a197e5b132e196.  The ciphertext is 32 octets long.
>
>Robert R. Jueneman
>Security Architect
>Network Security Development
>Novell, Inc.
>122 East 1700 South
>Provo, UT 84606
>[email-masked] 
>1-801-861-7387

---

From: Russ Housley <[email-masked]>
Date: Thu, 04 Mar 1999 09:08:40 -0500

>That would be my recommendation.

I think that OAEP has the same issue.  Each time a key is wrapped, a
different random number must be used.  This is the same a generating a new
IV for the first encryption.

>so I don't know where you stand.

I think I was clear on this point in an earlier posting.  My first priority
is to finish S/MIME v3.  If the general key wrapping problem is solved at
the same time, fine.  The S/MIME v3 structure includes an
AlgorithmIdentifier for the key wrapping algorithm, so if a secure solution
is included in the documents today, it can be aougmented with a general
solution when it is fully vetted.

>mechanisms.  I certainly hope it isn't the later.

In general, ASN.1 is a good tool.  However, Burt Kaliski's attack against
the original key wrap algorithm was due to known structure in the
plaintext.  ASN.1 intruduces significant structure.  While ASN.1 or some
other encoding might be part of the general key wrap solution, I am will
avoid it in the near term.

>probably ought to be addressed.

No.  However, every user is concerned with overhead.  Since the
content-encryption key is wrapped once for each recipient, I am sensitive
to the multiplier.

Russ

---

From: Russ Housley <[email-masked]>
Date: Thu, 04 Mar 1999 11:51:57 -0500

All:

I greatly appreciate the work that everyone has put into the open debate on
key wrapping.

The 44th IETF meeting is coming up rapidly, and I would like to close this
debate prior to the meeting.  To that end, I selected the double-encryption
algorithm.  An updated CMS document has not been posted yet, so I have
attached the text associated with key wrapping.

Based on the discussion on this list, I believe that the double-encryption
algorithm meet the security requirements, and it is easily implemented with
building blocks that are otherwise needed to implement CMS.

I will gladly facilitate the further discussion of the general wrapping
algorithm if the participants are interested.  I do not think that
discussion should occur on the IETF S/MIME Working Group mail list, but I
will arrange for a separate list to be created if you want to pursue the
general wrap algorithm.

Russ

= = = = = = = = = =

12.6  Triple-DES and RC2 Key Wrap Algorithms

   CMS implementations must include encryption of a Triple-DES content-
   encryption key with a Triple-DES key-encryption key using the
   algorithm specified in Sections 12.6.2 and 12.6.3.  CMS
   implementations should include encryption of a RC2 content-encryption
   key with a RC2 key-encryption key using the algorithm specified in
   Sections 12.6.4 and 12.6.5.  Triple-DES and RC2 content-encryption
   keys are encrypted in Cipher Block Chaining (CBC) mode [MODES].

   Key Transport algorithms allow for the content-encryption key to be
   directly encrypted; however, key agreement and symmetric key-
   encryption key algorithms encrypt the content-encryption key with a
   second symmetric encryption algorithm.  This section describes how
   the Triple-DES or RC2 content-encryption key is formatted and
   encrypted.

   Key agreement algorithms generate a pairwise key-encryption key, and
   a key wrap algorithm is used to encrypt the content-encryption key
   with the pairwise key-encryption key.  Similarly, a key wrap
   algorithm is used to encrypt the content-encryption key in a
   previously distributed key-encryption key.

   The key-encryption key is generated by the key agreement algorithm or
   distributed out of band.  For key agreement of RC2 key-encryption
   keys, 128 bits must be generated as input to the key expansion
   process used to compute the RC2 effective key [RC2].

   The same algorithm identifier is used for both 2-key and 3-key
   Triple-DES.  When the length of the content-encryption key to be
   wrapped is a 2-key Triple-DES key, a third key with the same value as
   the first key is created.  Thus, all Triple-DES content-encryption
   keys are wrapped like 3-key Triple-DES keys.

12.6.1  Key Checksum

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

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

12.6.2  Triple-DES Key Wrap

   The Triple-DES key wrap algorithm encrypts a Triple-DES content-
   encryption key with a Triple-DES key-encryption key.  The Triple-DES
   key wrap algorithm is:

   1.  Set odd parity for each of the DES key octets comprising
       the content-encryption key, call the result CEK.
   2.  Compute an 8 octet key checksum value on CEK as described above
       in Section 12.6.1, call the result ICV.
   3.  Let CEKICV = CEK || ICV.
   4.  Generate 8 octets at random, call the result IV.
   5.  Encrypt CEKICV in CBC mode using the key-encryption key.  Use
       the random value generated in the previous step as the
       initialization vector (IV).  Call the ciphertext TEMP1.
   6.  Let TEMP2 = IV || TEMP1.
   7.  Reverse the order of the octets in TEMP2.  That is, the most
       significant (first) octet is swapped with the least significant
       (last) octet, and so on.  Call the result TEMP3.
   8.  Encrypt TEMP3 in CBC mode using the key-encryption key.  Use
       an initialization vector (IV) of 0x4adda22c79e82105.
       The ciphertext is 40 octets long.

   Note:  When the same content-encryption key is wrapped in different
   key-encryption keys, a fresh initialization vector (IV) must be
   generated for each invocation of the key wrap algorithm.

12.6.3  Triple-DES Key Unwrap

   The Triple-DES key unwrap algorithm decrypts a Triple-DES content-
   encryption key using a Triple-DES key-encryption key.  The Triple-DES
   key unwrap algorithm is:

   1.  If the wrapped content-encryption key is not 40 octets, then
       error.
   2.  Decrypt the wrapped content-encryption key in CBC mode using
       the key-encryption key.  Use an initialization vector (IV)
       of 0x4adda22c79e82105.  Call the output TEMP3.
   3.  Reverse the order of the octets in TEMP3.  That is, the most
       significant (first) octet is swapped with the least significant
       (last) octet, and so on.  Call the result TEMP2.
   4.  Decompose the TEMP2 into IV and TEMP1.  IV is the most
       significant (first) 8 octets, and TEMP1 is the least significant
       (last) 32 octets.
   5.  Decrypt TEMP1 in CBC mode using the key-encryption key.  Use
       the IV value from the previous step as the initialization vector.
       Call the ciphertext CEKICV.
   6.  Decompose the CEKICV into CEK and ICV. CEK is the most significant
       (first) 24 octets, and ICV is the least significant (last) 8 octets.
   7.  Compute an 8 octet key checksum value on CEK as described above
       in Section 12.6.1.  If the computed key checksum value does not
       match the decrypted key checksum value, ICV, then error.
   8.  Check for odd parity each of the DES key octets comprising CEK.
       If parity is incorrect, then there is an error.
   9. Use CEK as the content-encryption key.

12.6.4  RC2 Key Wrap

   The RC2 key wrap algorithm encrypts a RC2 content-encryption key with a 
   RC2 key-encryption key.  The RC2 key wrap algorithm is:

   1.  Let the content-encryption key be called CEK, and let the length
       of the content-encryption key in octets be called LENGTH.
   2.  Compute an 8 octet key checksum value on CEK as described above
       in Section 12.6.1, call the result ICV.
   3.  Let CEKICV = LENGTH || CEK || ICV.  LENGTH is a single octet.
   4.  Let CEKICVPAD = CEKICV || PAD.  If the length of CEKICV is a
       multiple of 8, the PAD has a length of zero.  If the length of
       CEKICV is not a multiple of 8, then PAD contains the fewest
       number of random octets to make CEKICVPAD a multiple of 8.
   5.  Generate 8 octets at random, call the result IV.
   5.  Encrypt CEKICVPAD in CBC mode using the key-encryption key.
       Use the random value generated in the previous step as the
       initialization vector (IV).  Call the ciphertext TEMP1.
   6.  Let TEMP2 = IV || TEMP1.
   7.  Reverse the order of the octets in TEMP2.  That is, the most
       significant (first) octet is swapped with the least significant
       (last) octet, and so on.  Call the result TEMP3.
   8.  Encrypt TEMP3 in CBC mode using the key-encryption key.  Use
       an initialization vector (IV) of 0x4adda22c79e82105.

   Note:  When the same content-encryption key is wrapped in different
   key-encryption keys, a fresh initialization vector (IV) must be
   generated for each invocation of the key wrap algorithm.

12.6.5  RC2 Key Unwrap

   The RC2 key unwrap algorithm decrypts a RC2 content-encryption key
   using a RC2 key-encryption key.  The RC2 key unwrap algorithm is:

   1.  If the wrapped content-encryption key is not a multiple of 8
       octets, then error.
   2.  Decrypt the wrapped content-encryption key in CBC mode using
       the key-encryption key.  Use an initialization vector (IV)
       of 0x4adda22c79e82105.  Call the output TEMP3.
   3.  Reverse the order of the octets in TEMP3.  That is, the most
       significant (first) octet is swapped with the least significant
       (last) octet, and so on.  Call the result TEMP2.
   4.  Decompose the TEMP2 into IV and TEMP1.  IV is the most
       significant (first) 8 octets, and TEMP1 is the remaining octets.
   5.  Decrypt TEMP1 in CBC mode using the key-encryption key.  Use
       the IV value from the previous step as the initialization vector.
       Call the ciphertext CEKICVPAD.
   6.  Decompose the CEKICVPAD into LENGTH, CEK, ICV, and PAD.  LENGTH is
       the most significant (first) octet.  CEK is the following LENGTH
       octets.  ICV is the following 8 octets.  PAD is the remaining
       octets, if any.
   7.  If PAD is more than 7 octets, then error.
   8.  Compute an 8 octet key checksum value on CEK as described above
       in Section 12.6.1.  If the computed key checksum value does not
       match the decrypted key checksum value, ICV, then error.
   9.  Use CEK as the content-encryption key.

Security Considerations

   Section 12.6 specifies key wrap algorithms used to encrypt a Triple-
   DES [3DES] content-encryption key with a Triple-DES key-encryption
   key or to encrypt a RC2 [RC2] content-encryption key with a RC2 key-
   encryption key.  The key wrap algorithms make use of CBC mode
   [MODES].  These key wrap algorithms have been reviewed for use with
   Triple and RC2.  They have not been reviewed for use with other
   cryptographic modes or other encryption algorithms.  Therefore, if a
   CMS implementation wishes to support ciphers in addition to Triple-
   DES or RC2, then additional key wrap algorithms need to be defined to
   support the additional ciphers.