Re: A New Triple-DES Key Wrap Algorithm

[Russ Housley <[e-mail]>]

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 <[e-mail]> 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
>[e-mail]
>1-801-861-7387