RE: A New Triple-DES Key Wrap Algorithm

["Tolga Acar" <[e-mail]>]

I don't see how a random/different IV suddenly makes it all work, because it is away from being a general solution to the problem. And the problem is twofold, and more general than encrypting a DES key with TripleDES.

1. Diffusion:
Transition of the known plaintext patterns to the ciphertext in block ciphers. A very similar problem exists in image processing where the image is processed block-by-block and then you see the so-called blocking effects. The known-plaintext and birthday attack utilizes this deficiency in block-ciphers. Thus, the analysis should be done on the whole message rather than on blocks; or do "overlapped" processing on block boundaries (which isn't suitable for encryption purpose).

Another way of looking at this aould be to consider the message as the input "block", not necessarily partitioned into sub-blocks to accomodate the requirements of the underlying cipher. Longer the input message (say, ASN.1 encoded key), harder the birthday attacks. So, simply isolate the underlying block cipher details from the key wrapping, i.e., make the input size = block size. 

OAEP is a solution to this problem: a variable block-size algorithm in which it is hard to find the input unless all of the output is known. It adds "integrity" to the message - like a digital signature with message recovery.

Besides, I don't see why the key encryption algorithm has to be a block cipher, let alone a cipher requiring an IV.


2. Block encryption:
Why are we concerned so much about the known plaintext patterns in key wrapping, and not in any (data) encryption where known patterns in the plaintext may be far more common. Isn't it prudent to use OAEP (maybe with different parameters) in regular encryption?

- Tolga


>>> Burt Kaliski <[e-mail]> 3/1/99 12:35:06 >>>
Recall that OAEP (in general) has two arguments: message and parameters.

OAEP provides confidentiality to the message and integrity to the
parameters. It also binds the parameters and the message cryptographically.
It the parameters are modified, the OAEP decoding operation will detect the
change.

The set of parameters can be null, or it may contain information about the
message such as key type in the case that the message is the key.

Thus the conflict between ASN.1 and confidentiality is easily resolved: let
the message be the secret key, and let the parameters specify the type of
key, length, usage, etc. with ASN.1. This is one of the nice features of
OAEP: it is easy to carry non-confidential attributes about a message.

-- Burt 

> ----------
> From: 	Don Johnson[SMTP:[e-mail]] 
> Sent: 	Friday, February 26, 1999 4:46 PM
> To: 	Kevin Kingdon
> Cc: 	Bob Jueneman; [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail]; Tolga Acar;
> [e-mail]; [e-mail]; Burt Kaliski; [e-mail];
> [e-mail]; [e-mail]; Ron Rivest; [e-mail];
> [e-mail]; [e-mail]; [e-mail]; [e-mail];
> [e-mail] 
> Subject: 	RE: A New Triple-DES Key Wrap Algorithm
> 
> Kevin,
> 
> Here is what I am saying, I do not think it is not controversial.
> 
> 1. For any confidentiality method, such as encryption, adding in known
> quantities: A) does not keep them confidential, as they are known, and B)
> may give an adversary a toehold he would not otherwise have, for example,
> with encryption he will know some plaintext and resulting ciphertext (in
> the worst case some blocks of known plaintext/ciphertext).
> 
> 2. For that reason, I resist adding in known data to data that is intended
> to be kept confidential.  It is not forbidden to add in known data, I just
> want to believe that the cost/benefit tradeoff makes it worthwhile.  And I
> try to keep down the amount of known data if possible.
> 
> Don Johnson
> 
> 
> 
> 
> 
> Kevin Kingdon <[e-mail]> on 02/26/99 02:57:22 PM
> 
> To:   Don Johnson/Certicom, Bob Jueneman <[e-mail]>
> cc:   [e-mail], [e-mail], [e-mail],
>       [e-mail], [e-mail], [e-mail],
>       [e-mail], [e-mail], [e-mail],
>       [e-mail], [e-mail],
>       [e-mail], [e-mail],
>       [e-mail], [e-mail],
>       [e-mail], [e-mail],
>       [e-mail], [e-mail],
>       [e-mail], [e-mail], [e-mail],
>       [e-mail], Tolga Acar <[e-mail]>,
>       [e-mail], [e-mail], Burt Kaliski
>       <[e-mail]>, [e-mail], [e-mail],
>       [e-mail], Ron Rivest <[e-mail]>,
>       [e-mail], [e-mail], [e-mail],
>       [e-mail], [e-mail], [e-mail] 
> Subject:  RE: A New Triple-DES Key Wrap Algorithm
> 
> 
> 
> 
> Don,
> 
> Are you saying that the input (plaintext) to an encryption operation must
> not be structured? I thought that was what encryption was all about -
> hiding
> the structure / information content of the plaintext. In any case, doesn't
> using OAEP as a part of an encryption scheme mask the plaintext structure
> just in case the encryption primitive is vulnerable to attacks that take
> advantage of that structure?
> 
> Kevin
>           -----Original Message-----
>           From:     Don Johnson [mailto:[e-mail]] 
>           Sent:     Friday, February 26, 1999 11:25 AM
>           To:  Bob Jueneman
>           Cc:  [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail];
> [e-mail];
> [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail];
> [e-mail]; Tolga Acar; [e-mail]; [e-mail];
> Burt
> Kaliski; [e-mail]; [e-mail]; [e-mail]; Ron
> Rivest; [e-mail]; [e-mail]; [e-mail];
> [e-mail]; [e-mail]; [e-mail] 
>           Subject:  Re: A New Triple-DES Key Wrap Algorithm
> 
>           Bob, Russ,
> 
>           ASN.1 is very structured and can be considered to have many
> known values.
>           As such, strictly from an info theory viewpoint, use of
> ASN.1 and
>           confidentiality are are in opposition.  This does not mean
> it should be
>           forbidden, just that we would want to have very strong
> assurances about the
>           properties provided by the encryption to use ASN.1 or
> similar highly
>           structured formats.
> 
>           Don Johnson
> 
> 
> 
> 
> 
>           "Bob Jueneman" <[e-mail]> on 02/26/99 01:38:19
> PM
> 
>           To:   [e-mail] 
>           cc:   [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], [e-mail], [e-mail],
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], [e-mail],
>                 [e-mail], [e-mail],
>                 [e-mail],
> [e-mail],
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], "Tolga Acar"
> <[e-mail]>,
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail], [e-mail],
> [e-mail],
>                 [e-mail] (bcc: Don Johnson/Certicom)
>           Subject:  Re: A New Triple-DES Key Wrap Algorithm
> 
> 
> 
> 
>           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 <[e-mail]> 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 <[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
> 
> 
> 
> 
> 
> 
> 
>