----------
From: Bob Jueneman[SMTP:BJUENEMAN(_at_)novell(_dot_)com]
Sent: Friday, February 26, 1999 1:38 PM
To: housley(_at_)spyrus(_dot_)com
Cc: cme(_at_)ACM(_dot_)ORG; berson(_at_)anagram(_dot_)com;
bschanni(_at_)BayNetworks(_dot_)com;
kent(_at_)bbn(_dot_)com; pcain(_at_)bbn(_dot_)com;
mhetzel(_at_)bell-labs(_dot_)com; brickell(_at_)certco(_dot_)com;
djohnson(_at_)certicom(_dot_)ca; schneier(_at_)counterpane(_dot_)com;
daw(_at_)cs(_dot_)berkeley(_dot_)edu;
denning(_at_)cs(_dot_)cosc(_dot_)georgetown(_dot_)edu;
smid(_at_)csmes(_dot_)ncsl(_dot_)nist(_dot_)gov;
omura(_at_)cylink(_dot_)com;
dickie(_at_)EMPIRE(_dot_)eclipse(_dot_)ncsc(_dot_)mil;
carlisle(_dot_)adams(_at_)entrust(_dot_)com; paulv(_at_)entrust(_dot_)com;
Blake(_dot_)greenlee(_at_)greenlee(_dot_)com; ietf-smime(_at_)imc(_dot_)org;
benaloh(_at_)microsoft(_dot_)com;
bfox(_at_)microsoft(_dot_)com; cjwagne(_at_)missi(_dot_)ncsc(_dot_)mil;
jis(_at_)mit(_dot_)edu; Tolga Acar;
merkle(_at_)parc(_dot_)xerox(_dot_)com;
BSnow(_at_)radium(_dot_)ncsc(_dot_)mil; burt(_at_)RSA(_dot_)COM;
ekr(_at_)rtfm(_dot_)com;
jlinn(_at_)securitydynamics(_dot_)com; ams(_at_)terisa(_dot_)com;
rivest(_at_)theory(_dot_)lcs(_dot_)mit(_dot_)edu;
balenson(_at_)tis(_dot_)com; denny(_at_)tis(_dot_)com;
acc(_at_)tycho(_dot_)ncsc(_dot_)mil; jhs(_at_)tycho(_dot_)ncsc(_dot_)mil;
smatyas(_at_)us(_dot_)ibm(_dot_)com; desmedt(_at_)uwm(_dot_)edu
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 <housley(_at_)spyrus(_dot_)com> 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 <housley(_at_)spyrus(_dot_)com> 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
bjueneman(_at_)novell(_dot_)com
1-801-861-7387