Subject: A New Triple-DES Key Wrap Algorithm

From: Russ Housley <[email-masked]>
Date: Sun, 31 Jan 1999 18:17:38 -0500

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: "Don Johnson" <[email-masked]>
Date: Mon, 1 Feb 1999 15:22:54 -0500

Russ,

My comments imbedded in your note and prefixed with an *.
Don J.

Russ Housley <[email-masked]> on 02/01/99 02:48:01 PM

To:   Don Johnson/Certicom
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]
Subject:  Re: A New Triple-DES Key Wrap Algorithm

Don:

>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.

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.

* I like the length field, it allows for future flexibility if needed and
is a simple way to strengthen an integrity check.  It is best if the length
field is in a fixed location, that way there is no ambiguity, which as we
know is bad for security.

>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.

Are you saying that the original formatting with double encryption would be
a cheaper way to resolve the problems raised by Burt kaliski?

* I think so or something like that.  I think it would be cheaper in code
size as TDES CBC already needs to exist in the code.

Would the IV
for the second encryption be the ciphertext of the last block from the
first encryption pass?

* Yes.

If so, it needs to be carried somewhere.

* No, it does not, if a 64-bit random number is put first in the block,
this is due to self syncronizing property of CBC mode. Alternately, the
first block could be seen at a random IV.

Is disclosure an issue?

* Not sure what you mean by this.  Please explain more.  Disclosure of the
IV?  Disclosure of the text or key?  What?

Alternatively, can a differnt constant IV be used for
the second pass?

* If you use an IV of 0, the first block is damaged, if you do not care as
it is random, then you do not care.

Thanks for the speedy review,
   Russ

---

From: "Bob Jueneman" <[email-masked]>
Date: Tue, 02 Feb 1999 14:55:08 -0700

Russ,

For the benefit of those of us who weren't following the discussion all 
that closely, could you summarize your original submission (and the 
rationale behind it), and the attack which Burt Kalisky found against it?

BTW, that's an impressive cc-list -- almost a crypto who's who. I'd add 
Hugo Kwrazack and Yair Frankel, and certainly Don Coppersmith, 
but I don't have their current e-mail addresses.

Bob

Robert R. Jueneman
Security Architect
Network Security Development
Novell, Inc.
122 East 1700 South
Provo, UT 84606
[email-masked]
1-801-861-7387

>>> "Don Johnson" <[email-masked]> 02/01/99 01:22PM >>>
Russ,

To:   Don Johnson/Certicom

TDES
it
forms
not

Would the IV

* Yes.

Is disclosure an issue?

---

From: Bruce Schneier <[email-masked]>
Date: Tue, 02 Feb 1999 16:11:56 -0600

>but I don't have their current e-mail addresses.

It is an impressive list, but don't assume that just because someone is on
the 
list that they have analyzed the system.  Russ is looking for free
cryptanalysis,
and the best way to get that is to send email to everyone and hope that
someone
has nothing better to do that day.  It's a good way to have bad systems
broken,
but it is less effective at showing that good systems are actually good.

Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems     Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN  55419      Fax: 612-823-1590
           Free crypto newsletter.  See:  http://www.counterpane.com

---

From: "Bob Jueneman" <[email-masked]>
Date: Wed, 03 Feb 1999 17:12:33 -0700

Dear Burt --

Very interesting!

Ages ago, I tried to analyze the possibility of a compromise of 
Output Feedback Mode of an extremely long message, but I'd never 
considered the Birthday Attack against a very long CBC encrypted 
message when there was partially known plaintext. So this was eye-opening.

In order to make sure that I understand, let me try to generalize the requirements
and play them back to you for comment.

Ideally, we would like to use a common key wrapping envelop approach
that would be resistant to a broad class of these kinds of attacks, regardless 
of the KEK algorithm type (stream, block, or asymmetric), block size, or key length;
or of the CEK algorithm type, block size, or key length; assuming that there 
may be at least some partially known plaintext in the CEK key itself, in the CEK 
wrapping, or in any padding required because of the structure of the KEK 
algorithm or the CEK itself.

So it shouldn't matter if I am using triple-DES with inner or outer CBC, or RC4 with
112 bits, etc.  It would certainly be dumb, but because of export controls it might 
even be the case that a 2048 RSA key, wrapped in an ASN.1 encoded 
structure, might have to be encrypted in a 40 bit RC2.

The partially known plaintext in the completely general case might come from the salt
(if that were a public or semi-public IV); from the key structure itself, such as the 
parity bits in DES,  the leading byte in RSA, or any ASN.1 wrapper; or from any padding 
that might be required because of the nature of the KEK algorithm.

The length of the key that is being wrapped should be immaterial -- it might even be a 
very long one-time pad, so birthday attacks within the key itself should be considered
in addition to the possibility of birthday attacks against common blocks when the same 
CEK is wrapped multiple times using multiple KEKs.

And the size of salt and/or padding should not be fixed, as it might be necessary to 
deal with KEK algorithms of arbitrary structure, ranging from some 1-bit stream 
cipher such as DES CFB to perhaps a 256 bit AES block.  I wouldn't necessarily 
even assume that the internal blocks were multiples of 8 bits.

Although you only described the possibility of leakage due to known padding values,
I would assume there is also a potential risk due to the structure of the CEK itself, in
particular if the CEK is a natural language password, or if there is internal structure
such as in the case of DES parity bits or an ASN.1 encoded key structure.  We have even encountered a possible requirement that the CEK itself be digitally signed by
the key generation facility in order to support possible key escrow schemes,
with the entire complex key structure presumably being encrypted as an opaque string
by the KEK.  (This is likely to be the case where the application never gets to see 
the key in the clear or know anything about its structure, but only gets a handle to
the key blob.)

My initial thought to address this possibility would be to use a secret salt as the basis
for some internal whitening of the CEK structure itself, extending the salt as necessary
to deal with the length of the CEK, and then to continue that whitening to cover the 
padding information.  This of course assumes that the salt itself is a purely random 
bit string with no internal structure or partially known content, for otherwise the problem becomes circular.

I'm going to have to think a bit more about the inclusion of a key integrity check, but 
I would tend to be opposed. At first glance, at least, this seems similar to the French 
stop-value requirement, and instead of providing any additional form of protection 
it might tend to significantly weaken the key encryption. I would at least whiten the 
key integrity check along with everything else.

Bob

Robert R. Jueneman
Security Architect

>>> Burt Kaliski <[email-masked]> 02/03/99 02:48PM >>>
Dear Bob --

Let me address your question, and the general situation with triple-DES key
wrapping.

The high-level goal is to wrap an arbitrary length content encryption key
(CEK) with a symmetric key encryption key (KEK).

Wrapping single-block CEKs is straightforward and has an established
precedent, as in the wrapping of single-length DES keys by ECB mode
encryption. But there is no established precedent for wrapping
multiple-block CEKs, as far as I'm aware.

Russ proposed one method, which involved formatting the CEK into a package
of the form

  salt || CEK || ICV || pad

where salt is a random value, ICV is an integrity check on the CEK, and pad
one of a set of known padding values. The package is then encrypted with the
KEK in CBC mode.

My initial "attack" on this approach was based on the observation that since
the pad is known, there is known plaintext for the encryption with the KEK.
This leads to a potential vulnerability when many CEKs are wrapped with the
same KEK, due to the Birthday Paradox. After about 2^32 CEKs (for a 64-bit
block size) it is likely that a block of one wrapped CEK will match a block
of another CEK. If one of the blocks corresponds to the encryption of a
partially known value (e.g., a pad xored with some of the previous
ciphertext), then information about the other block will become known.

This is the same as the problem with 64-bit block ciphers in CBC mode for
message encryption -- after about 2^32 blocks, information about the
plaintext starts to leak.

A simple way to avoid the attack is to limit the number of keys that can be
wrapped with a given KEK. Indeed, S/MIME already limits the number in the
case of Diffie-Hellman-based KEKs, since each KEK is employed only once.
However, in the case of mailing lists, a KEK may be used many times.

But the essential issue is the precedent that S/MIME will set for wrapping
multiple-block CEKs in other systems. I'm concerned that we develop
something robust here, not something that works all right for S/MIME but is
hard to adapt to other systems.

Consider, for historical comparison, the password-based encryption methods
in PKCS #5 v1. They worked fine when DES and MD5 where the algorithms of
choice -- but there was no clear method for extending them to, say,
triple-DES and SHA1. PKCS #5 v2 is clearing up the situation, but in the
interim, there were quite a few alternate approaches, with varying degrees
of security and standarization.

My proposal to Russ was to consider the use of OAEP for processing CEKs
prior to encryption with a block cipher. Although OAEP was first developed
for asymmetric encryption, the construction is not limited to that purpose,
and indeed the security proofs should carry over nicely to wrapping with a
symmetric KEK. OAEP has a built-in integrity check and ensures that every
bit of output depends on every bit of input. It is also quite scalable, and
can accommodate CEKs of any length and arbitrary encryption algorithms.
Further, it builds on an exisiting primitive. One can view OAEP as a way of
preparing keys for wrapping with either symmetric or asymmetric techniques,
which simplifies implementation.

I'll suggest a few specific improvements Russ' OAEP proposal in a separate
message.

Don Johnson's proposal two-pass encryption with triple-DES-CBC is another
option. It has the advantage of not requiring a separate hash function, and,
implemented with appropriate settings, resists the birthday attacks on the
original method.

(BTW, I don't have any proprietary interest in promoting OAEP --- just like
to continue to deploy common primitives rather than defining new ones. HMAC
is another example of something that's gaining use because of its
robustness.)

-- Burt

> ----------
> From: 	Bob Jueneman[SMTP:[email-masked]] 
> Sent: 	Tuesday, February 02, 1999 4:55 PM
> To: 	[email-masked]; [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]; Bob Jueneman; Tolga Acar; [email-masked];
> [email-masked]; Burt Kaliski; [email-masked];
> [email-masked]; [email-masked]; Ron Rivest; [email-masked];
> [email-masked]; [email-masked]; [email-masked]; [email-masked];
> [email-masked]

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 5 Feb 1999 02:46:22 (NZDT)

[Note: Recipient list trimmed to those who've shown an interest so far]
 
Instead of using OAEP-type padding (which is rather complex to implement and 
results in data expansion), why not just encrypt the wrapped key twice?  This 
way, the outer encryption layer depends on every bit in the inner encryption 
layer, and that depends on the plaintext and MEK, so you never get lots of 
identical messages encrypted with different keys.  This is trivial to 
implement, requires no extra algorithms beside than the cipher used for the 
wrapping, and results in no data expansion.  Here's how it works:
 
  Notation: 
 
  P[] = plaintext blocks
  C1[], C2[] = ciphertext blocks encrypted once/twice
 
  Encryption:
 
  Encrypt P[ 0 ]...P[ n ] using the initial IV
  Encrypt C1[ 0 ]...C1[ n ] using the existing IV from the previous pass 
        (ie C1[ n ])
 
  Decryption:
 
  Decrypt C2[ 1 ]...C2[ n ] using C2[ 0 ] as the IV
  Decrypt C2[ 0 ] using C1[ n ] as the IV
  Decrypt C1[ 0 ]...C1[ n ] using the initial IV

Peter.

---

From: "Bob Jueneman" <[email-masked]>
Date: Thu, 04 Feb 1999 10:38:44 -0700

Stephen,

>>> Dr Stephen Henson <[email-masked]> 02/03/99 05:25PM >>>
Apologies if I've missed the point here but...

[RRJ] Me too, as I have not been following the S/MIME - CMS discussion in any
depth, but only seized on the issue of key wrapping as a general problem.
Within Novell's NICI architecture we do lots of key wrapping for purposes that
have nothing to do with S/MIME.  Once the discussion pointed out a potential
weakness in key wrapping generally (and this seems to be just one of a class
of problems that have been uncovered recently, including the SSL million-questions
attack.

Is there some specific need to use the same KEK for mailing lists
multiple times or could the same solution be used as in S-S DH? 

In other words make the use of a "salt" in the message compulsory and
use the mailing list key in place of the DH shared secret (ZZ). This
would then allow the same mailing list key to be used multiple times
because the KEK would be different with each salt.

[RRJ] Rules of thumb are inherently dangerous, but my own preference 
when a problem shows up is to reach for a bigger hammer and try to smash the
problem completely, rather than trying to finesse it. So I'd much rather have a 
generalized key wrapping scheme than one that is tied to S/MIME or even CMS
specifically.

Steve.
-- 
Dr Stephen N. Henson. UK based freelance Cryptographic Consultant. 
For info see homepage at http://www.drh-consultancy.demon.co.uk/ 
Email: [email-masked] 
NOTE NEW (13/12/98) PGP key: via homepage.

---

From: "Bob Jueneman" <[email-masked]>
Date: Thu, 04 Feb 1999 12:57:30 -0700

Peter,

The only [small] problem I have with your approach is performance,
as double encryption with triple-DES is relatively expensive, especially 
if you don't save and reuse the state after the three key expansions 
step in DES.  In addition, I would like to have a key wrapper format
that is completely independent of the KEK algorithm, soi that I can use
the same wrapper whether I use DES, RSA, elliptic curves, etc. And
I don't think you want to propose doing double encryption with an 
asymmetric cipher!

What I would suggest would be to replace your inner encryption 
with the equivalent of Output Feedback mode, but using SHA-1
as the encryption or whitening function, with a random nonce R serving 
as the starting seed for SHA-1.  

In other words, begin by computing SHA-1(R) of the random nonce, and 
call that W(1).  Then W(2) = SHA-1(W(1)), and W(n) = SHA-1(W(n-1)),
where n= length(keyblob + encryption block size)/160 rounded up to 
the next SHA-1 block boundary, so that any necessary padding is whitened
as well.

Then XOR the string of W(1)...W(n) with the keyblob KB(1)...KB(n) to 
produce the whitened plaintext of the keyblob, P(1)...P(n).

Finally, encrypt R || P(1)...P(n) using whatever KEK algorithm is desired.

Now the only question I have is whether the fact that the whitening 
does not involve the plaintext and is therefore known once the random
nonce has been decrypted can somehow be used to leak information,
given partially known plaintext in the keyblob. It would if the nonce weren't
secret, but in order to gain any information about the nonce would require
finding a ciphertext block that matches a specific block, corresponding to R, 
rather than merely finding any two matching blocks.

So I don't see an attack, regardless of the type of KEK encryption algorithm
used, including both symmetric and asymmetric algorithms. Does anyone else?

I do concede that this approach produces some data expansion -- at least 160 
bits for the random nonce, and perhaps some more for padding if the keyblob that
is being encrypted is not an exact multiple of the encryption block size.
Generally speaking, that is a tradeoff I would be willing to make.

Bob

>>> Peter Gutmann <[email-masked]> 02/05/99 02:46AM >>>

 
  Notation: 
 
  P[] = plaintext blocks
 
  Encryption:

  Decryption:

Peter.

---

From: Russ Housley <[email-masked]>
Date: Thu, 04 Feb 1999 16:18:03 -0500

Bob:

I do not mind if a group goes off and solves the most general problem, but
that is not the problem that I have.

In the S/MIME v3 environment and other environments that use the
Cryptographic Message Syntax (CMS), the KEK and CEK will always be
symmetric keys.  If we could come to closure on one symmetric key wrapping
another symmetric key, it would be very helpful to the S/MIME v3 effort.
In fact, wrapping one 3DES key in another 3DES key is the highest priority,
and wrapping one RC2 key in another RC2 128-bit key is the next highest
priority.

Russ

---

From: "Bob Jueneman" <[email-masked]>
Date: Thu, 04 Feb 1999 17:12:23 -0700

Fair enough, Russ.

The only problem is that I have never known a standard that didn't 
end up being picked up and used by another group, many times inappropriately,
because they didn't understand the context and limitations of the original effort.

Any comments on my proposed solution?

bob

>>> Russ Housley <[email-masked]> 02/04/99 02:18PM >>>
Bob:

Russ

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 6 Feb 1999 02:18:19 (NZDT)

[email-masked], [email-masked], [email-masked], [email-masked]

>The only [small] problem I have with your approach is performance, as double 
>encryption with triple-DES is relatively expensive, especially if you don't 
>save and reuse the state after the three key expansions step in DES.  In 
>addition, I would like to have a key wrapper format that is completely 
>independent of the KEK algorithm, soi that I can use the same wrapper whether 
>I use DES, RSA, elliptic curves, etc. And I don't think you want to propose 
>doing double encryption with an asymmetric cipher!
 
I chose it because two passes of whatever cipher was being used seemed the 
simplest way to do it.  There are many alternative to this, my immediate 
reaction when I saw the original analysis was to use the cipher to generate a 
pseudorandom stream, hash 128-bit chunks of it with SHA-1, and then XOR the 
20-byte blocks into the data to be encrypted, but it's a bit of an ad hoc 
approach and requires many applications of SHA-1 which are probably less 
efficient than the block cipher.  In any case I doubt that a handful of extra 
en/decryption operations for the two-pass crypt are going to add much 
overhead.  This is the same scheme suggested by Don Johnson, I wasn't sure 
initially whether we were talking about the same thing.                    
 
Historical note: I first used something like this for a sector-level 
encrypting disk device driver where there wasn't any room for storing the IV, 
so the encryption made two passes, the first to generate the IV and the second 
to perform the encryption.  The first pass used:
 
    P[ i ] ^= P[ i-K1 ] ^ P[ i-K2 ]
 
(K1 and K2 are appropriate constants), the second pass used the output as the 
IV.  This is a nice lightweight function (it's extremely efficient on a RISC 
CPU), the design was by Colin Plumb and was inspired by the (then brand-new) 
SHA.  In the KEK case you don't need this since the data is so short that two 
applications of the block cipher will carry virtually no overhead.
 
Peter.

---

From: [email-masked]
Date: Fri, 5 Feb 1999 15:01:42 +0000

I don't think we should be overly concerned about performance or code size. 

We are primarily talking about user orientated clients where another x hundred 
milliseconds is not going to be a significant problem and Microsoft seem to be 
doing their best to ensure that we have oodles of RAM available if needed.

When one considers the ever increasing speed of processors, what is not 
lightning fast now probably will be tomorrow and, perhaps more importantly, the 
processors used to attack the messages encrypted today definitely will be much, 
much faster in the future.

Our primary goal should be security, with ease of implementation next.

Bartley O'Malley
Citibank NA
Lewisham House
25 Molesworth Street
London
SE13 7EX
England

Tel +44-171-500-6473
Fax +44-171-500-8880

----Original Message-----
From: owner-ietf-smime(a)imc.org 
Sent: Saturday, February 06, 1999 7:18 AM
To: BJUENEMAN(a)novell.com; ietf-smime(a)imc.org
Cc: pgut001(a)cs.aucKland.ac.nz
Subject: Re: A New Triple-DES Key Wrap Algorithm

[email-masked], [email-masked], [email-masked], 
[email-masked]

 

 
Peter.

 << File: UnXhrds.txt >>

---

From: "Bob Jueneman" <[email-masked]>
Date: Mon, 08 Feb 1999 15:38:01 -0700

Russ, nice job of synthesizing various inputs into a standard format.

However, I continue to think we have two problems that have to 
be addressed. One is cryptographic, and one is architectural.

The cryptographic problem is one of not wanting to leak any
information in the case of many, many wrappings of the same CEK,
or in the case of a single KEK being used to wrap many, many CEKs;
where an observation of two matching ciphertexts might reveal information
about the plaintext if the cipher text includes any form of stereotyped of
constant information, e.g., parity bits or padding.

The architectural problem is to try to avoid the forthcoming problem of 
needing N-squared algorithm IDs in order to handle the various combinations
of key encryption keys and content encryption keys of different types that
are likely to be developed over the coming years.  

Although S/MIME may only be interested in some small number of algorithm
types today, there are lots of places where wrapped keys may be required 
in addition to S/MIME, and as a security architect I don't want to have 
to keep reinventing (and recoding) key wrapping techniques.

For this reason, I will offer my comments inline on the algorithms that you have 
proposed, and then propose a new Generalized Key Wrapping Algorithm
that attempts to take the best features of each of the three approaches you 
have described, and apply them in a more generalized way.

In addition, I've tried to explicitly state the security criteria, as I agree with 
Don Johnson.  Reasonable men can still differ, but if they don't have a common 
understanding and agreement as to the requirements, differences are almost
guaranteed.

= = = = = = = = = = 

WRAP ALGORITHM #1:  DOUBLE ENCRYPTION

A.1  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.

[RRJ]  I'm really not convinced of the necessity for a key checksum, although
I certainly have not followed all of the previous discussion.  If someone were 
trying to attack the key distribution mechanism, then the key checksum
could act as an oracle. I would _much_ prefer to checksum the entire result,
i.e., the final encrypted  key, than to checksum the CEK itself.  Is there some 
strong justification for this that I've missed, such as the French stop-code
requirement?

A.2  Triple-DES Key Wrap

1.  Set odd parity for each of the DES key octets comprising 
    the content-encryption key.
2.  Compute a 8 octet key checksum value on the content-encryption
    key as described above.
3.  Concatenate the key checksum value and the content-encryption key.
    The result is four 8 octet blocks: B1, B2, B3, and B4.
4.  Encrypt in CBC mode the four blocks using the key-encryption key.
    Use an IV of all zeros.
5.  Reverse the order of the four ciphertext blocks.  The resulting
    order is B4, B3, B2, and B1.

[RRJ] Rather than merely interchange the order of the four blocks, I believe 
that the entire string should be reversed, byte for byte. (I'd really like
to do it bit by bit, but the code would be a little awkward.) Preserving the
original block boundaries might possibly allow some clever attacks. I also
don't see the need for the final reversal.  

6.  Encrypt the four blocks a second time.  Encrypt in CBC mode 
    using the key-encryption key.  Use an IV of all zeros.

[RRJ]  I would prefer to use something other than 0 for the IV.
Ideally, the IV should be variable for each KEK, in order to make
a chosen plaintext attack that much more difficult. If a varying IV is
too difficult from a protocol standpoint, then at least avoid any kind of 
repeating structure -- use pi, or the square root of 2, or something
random.  And use two different IVs for the different steps.
Tom Berson is absolutely right -- avoid structure and 
symmetry at all cost!

[RRJ]  But my primary objection to this approach is the expense incurred by the 
second encryption pass. Even though a triple-DES operation may be quite
fast compared to say an RSA encryption, cycles are cycles, and
deliberately causing additional key management overhead that could be
avoided is unacceptable.

WRAP ALGORITHM #2:  MASK AND ENCRYPT

B.1  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.

B.2  Triple-DES Key Wrap

1.  Set odd parity for each of the DES key octets comprising 
    the content-encryption key.
2.  Compute a 8 octet key checksum value on the content-encryption
    key as described above.
3.  Generate an 8 octet random number: RAND.
4.  Let H1 = SHA-1 ( RAND ).
5.  Let H2 = SHA-1 ( H1 ).
6.  Let MASK equal the most significant (first) 32 octets of H1 || H2.

[RRJ] H2 is in some sense "more random" than H1, since it includes 
the mixing effect of the previous SHA-1.  If RAND were less than perfectly
random, i.e., subject to some kind of bias, H1 might remove most, but perhaps
not all of the bias, but if SHA-1 is any good at all, H2 should be much
less likely to leak information. For that reason, and since CBC introduces 
error propagation in the forward direction, MASK should equal the most 
significant (first) 32 octets of H2 || H1.

7.  Let KEYICV equal the content-encryption key concatenated with
    the key checksum value.

[RRJ] For the reason given above, forward error propagation, the KEYICV should
be formed by taking the key checksum concatenated with (followed by)
the CEK.  But I would greatly prefer not to have a key checksum at all, 
in which case MASK would only be 24 octets long, assuming a "naked" 
triple-DES CEK.

8.  Let PLAIN = RAND || ( KEYICV XOR MASK ).

[RRJ] The disadvantage of this approach, as compared to approach 3
(OAEP), is that the RAND is not whitened. Therefore, if there is any weakness
in RAND, it may be possible to derive some information from any block that has a
matching ciphertext.

9.  Encrypt PLAIN in CBC mode using the key-encryption key.
    Use an IV of all zeros.

WRAP ALGORITHM #3:  OAEP AND ENCRYPT

C.1  Key Checksum

No explicit checksum algorism is needed.  The OAEP processing provides 
the necessary integrity.

C.2  Triple-DES Key Wrap

1.  Set odd parity for each of the DES key octets comprising 
    the content-encryption key, called CEK.
2.  Let CEKPAD = 0x18 || CEK || 0x0000000000000000000000.
3.  Generate a 160-bit random value, called RAND.
4.  Let H1 = SHA-1 ( RAND || 0x01 ).
5.  Let H2 = SHA-1 ( RAND || 0x02 ).
6.  Let MASK1 equal the most significant (first) 36 octets of H1 || H2.

[RRJ]  I would prefer that a stronger function than this be used.
As it stands, the input to the two SHA-1 routines differ by only
two bits.  Use the approach of scheme 2 as modified above, i.e.,
Let H1 = SHA-1 ( RAND ),  H2 = SHA-1 ( H1 ) , 
MASK1 equal the most significant (first) 36 octets of H2 || H1.

7.  Let MKEY = CEKPAD XOR MASK1.
8.  Let MASK2 = SHA-1 ( MKEY ).
9.  Let MRAND = MASK2 XOR RAND.
10. Let MDATA = MRAND || MKEY.
11. Encrypt MDATA with the key-encryption key and CBC mode.  Use an IV
    with each octet equal to 0xA5.  The ciphertext is 56 octets long.

[RRJ]  Again, there is absolutely no reason to deliberately introduce
structure and symmetry in the IV.  If possible, use a real IV that varies 
for each KEK, in order to make a chosen plaintext attack that much 
more difficult.  At a minimum, use a pseudo-random constant with no 
apparent structure.

[RRJ]  If these problems were fixed, I believe that Approach 3 would be my 
favorite of those above, because it seems to be the most secure 
without introducing an unnecessary second encryption step.

However, I believe we can do better yet. Here is my recommended approach, 
one that tries to take advantage of all of the tweaks included above.

======================

GENERALIZED KEY WRAPPING ALGORITHM (Version 1)

Criteria:

1.	Explicitly define the type of Content Encryption Key and 
algorithm to be used in a manner that is independent of the KEK 
algorithm type, for example by a ASN.1 structure and designated 
algorithm ID, to avoid the N-squared proliferation of algorithm IDs 
for various combinations of KEK and CEK types.

2.	The Key Wrapping algorithm must be secure against 
a number of recently discovered attacks or threats; in particular it 
should be possible to securely encrypt a huge (>2^32) number of 
CEKs in a single KEK, and vice versa to encrypt a single CEK in a 
huge number of KEKs, without any significant possibility of information 
leakage that might be caused by a birthday attack, i.e., two pieces of 
matching cipher text revealing something about the plaintext. 
 
3.	In particular, the key wrapping format should not contain 
any stereotyped or common information in the plaintext, whether in 
the form of key parity bits, encryption padding bits, or other constant 
information. Instead, some form of encryption or whitening should be 
used to hide or mask such common information. The whitening must 
be unique for each wrapped key. 

4.	The key wrapping technique should be secure according 
to these criteria, regardless of whether the algorithm is a symmetric 
or an asymmetric one.  In particular, the key wrapping should be as 
good as OAEP when used with an asymmetric key.  (Since I don't 
consider myself to be very strong in this area, I'll leave it up to the 
crypto-mathematicians to tell me whether I have achieved this goal.)

TO ENCRYPT:

1.	Generate a random Content Encryption Key of an appropriate 
key length.  Fix up parity bits and/or any other constraints imposed by 
the CEK algorithm.  

2.	Wrap the key plus any other required parameters in a descriptive 
ASN.1 structure which includes the CEK algorithm ID, with the resulting 
string called CEKWRAP.  The ASN.1 structure and the various algorithm 
IDs are TBD.

3.	Add encryption padding bits (zeroes), if and as required by the 
algorithm by computing  CEKPAD = CEKWRAP || paddingBits

4.	Let LCEK = the length of CEKWRAP in bytes, a 16 bit unsigned integer

5.	Compute the maximum length of CEKWRAP plus padding:
                    LCEKPAD = LCEK + maximumAlgorithmPadding

6.	Compute the length of CEKPAD in SHA-1 blocks: 
                    LCEKSHA= floor(LCEKPAD/20) + 1

7.	Generate a 160-bit random nonce, RAND 

8.	Generate a sequence of LCEKSHA SHA-1 blocks: 
                    R(0) = RAND, 
                    R(1)=SHA-1(R(0)), ..., R(LCEKSHA)=SHA-1(R(LCEKSHA-1))

9.	Generate MASK1 = R(1) || R(2) ||...||R(LCEKSHA)

10.	Generate the whitened CEK plus padding by computing 
                    CEKWH = MASK1 XOR (CEKPAD)

11.	Whiten the RAND:     MRAND = SHA-1(CEKWH) XOR RAND 

12.	Whiten the length:      MLCEK = LCEK XOR MRAND, using the most 
significant 16 bits of MRAND            

13.	Generate the string to be encrypted, including the length of the 
whitened key:    MDATA = MRAND || MLCEK || CEKPAD

14.	Encrypt MDATA using the chosen Key Encryption Key KEK 
and the key encryption algorithm. If the algorithm requires an IV, use the 
first n bits (as specified by the algorithm) of SHA-1 of the UTF-8 encoding of  
"Generalized Key Wrapping Algorithm, version 1", repeated as necessary 
if n>160 bits (as it might be for AES).

TO DECRYPT:

1.	Decrypt MDATA using the KEK and appropriate algorithm

2.	Extract MRAND (20 bytes)

3.	Extract MLCEK (2 bytes)

4.	Compute LCEK = MRAND XOR MLCEK (most significant 16 bits)

5.	Extract CEKPAD

6.	Extract CEKWH from CEKPAD by taking the first LCEK bytes

7.	Compute  RAND = MRAND XOR SHA-1(CEKWH)

8.	Regenerate MASK1 as before, based on the extracted RAND.

9.	Extract CEKWRAP by taking the first LCEK from CEKWH XOR MASK1

10.	Unwrap the CEKWRAP ASN.1 structure if and as required, 
extracting the CEK and algorithm type, plus any other required parameters.

Regards,

Bob

Robert R. Jueneman
Security Architect

---

From: "Snow, Brian D." <[email-masked]>
Date: Wed, 10 Feb 99 10:54:00 PST

Gents,

     Just a minor side observation;
     
     Yes, zero is easy to get right in a standard; but not as easy
 to TEST if an implementation is correct during debug stage...
a fixed non-symmetric pattern detects early-on big-endian vrs little-endian
problems and other such problems encountered by developers.
However, other tests nail that down as well, so no big deal.

This is not a request for a change, just a side-observation.

Brian Snow

 ----------
From: Carl Ellison
To: Russ Housley
Cc: Bob Jueneman; ietf-smime; cme; berson; bschanni; kent; pcain; mhetzel; 
brickell; djohnson; schneier; daw; denning; smid; omura; carlisle.adams; 
paulv; Blake.greenlee; benaloh; bfox; cjwagne; jis; TACAR.PRV-7.PROVO; 
merkle; BSnow; burt; ekr; jlinn; ams; rivest; balenson; denny; acc; jhs; 
dickie; smatyas; desmedt
Subject: Re: A New Triple-DES Key Wrap Algorithm
Date: Tuesday, February 09, 1999 11:26PM

 -----BEGIN PGP SIGNED MESSAGE-----

At 11:31 AM 2/9/99 -0500, Russ Housley wrote:
>[RH] Two different IVs is easy.  The zero IVs were suggested by Carl
Ellison.

That's because one constant IV is as good as another, IMHO, and zero is a
lot easier to get right in a standard.

 -----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.5.3

iQCVAwUBNsE0uxN3Wx8QwqUtAQG+oQP8D8foR8OQ/R7/ryV1rXfsKindHItavGlN
p18kDFpgsrS2yl9HrGdGSwf+t3vEvfLVNGGHEYg96F6QgsBSoo83ZgEDm5na25hk
fJfp8xipoApdPTKw8czwigoOAcujhx73T34JzgRIllWeLbH1mK77HgAiFH6oy4K0
Cn1u9Yc7Tmc=
=7Mu2
 -----END PGP SIGNATURE-----

+------------------------------------------------------------------+
|Carl M. Ellison         [email-masked]     http://www.pobox.com/~cme |
|    PGP: 08FF BA05 599B 49D2  23C6 6FFD 36BA D342                 |
+--Officer, officer, arrest that man. He's whistling a dirty song.-+

---

From: "Bob Jueneman" <[email-masked]>
Date: Tue, 16 Feb 1999 18:19:54 -0700

Good enough, although I think there are potential cryptographic 
advantages to reversing the byte order as well.

Bob

>>> Russ Housley <[email-masked]> 02/15/99 07:57AM >>>
Swapping the bytes and swapping the blocks would have the same impact as
far as I can tell.  Swapping bytes is probably easier to code, so I accpt
this improvement.

Russ

/15/99 +0000, Peter Gutmann wrote:
>Russ Housley <[email-masked]> writes:
> 
>>5.  Reverse the order of the four ciphertext blocks.
> 
>Wouldn't it be better to reverse the bytes rather than the blocks?  This
makes 
>the result independant of the block size of the algorithm (so it'll work with 
>CFB mode as well), and it's rather easier to code than shuffling chunks of 
>memory around.
> 
>Peter.
>

---

From: "Bob Jueneman" <[email-masked]>
Date: Tue, 16 Feb 1999 18:53:37 -0700

David,

The reason why I got interested in this subject at all was that I realized that within
Novell's cryptographic architecture we wrap all sorts of keys, and when a possible 
attack was pointed out I became concerned.

I understand Russ Housley's point about wanting to solve this problem for S/MIME --
that is his charter, and he wants to deliver a product.  Admirable dedication.  And I 
certainly agree with you that there are other, probably more effective ways to 
compromise S/MIME. than by mailing a billion keys around!

But as a vendor, I don't want to have to solve the key wrapping problem one way 
for S/MIME, plus N other ways for the next N protocols to come along.

Believe me, it is very tough to get the attention of the real experts in this area,
and so once the problem was raised, I think we should solve it as best we can, 
once and for all. The S/MIME spec will then make a convenient point of reference
for something that was done right.

For that reason, then, I would tend to dismiss any and all arguments about whether
some particular attack might or might not be feasible in an S/MIME context -- that type of
subtlety is exceedingly hard to get right, and besides I want a more general purpose 
solution.

Although Steve Kent's argument about the cost of changing keys often is quite valid,
your argument about wanting to refresh your KEKs more often is NOT necessarily 
the way to improve security. It depends upon the threat.

Most approaches to brute force attacks try to speed up the number of key search 
operations that can be done simultaneously or in parallel, e.g., the recent success 
at the RSA conference of the EFF's Deep Crack engine in combination with lots of 
distributed computers, all working on the same challenge cipher.

But there is another approach, which I call the vacuum cleaner technique, where you 
don't target any specific key, but rather you suck up million or billions of keys and 
process all of them simultaneously. With this approach, for every new key that is 
tried, either singly or in parallel, the attacker looks at billions of ciphertexts to see 
if the result of encrypting a chosen plaintext with a given key matches any one of the 
ciphertexts that have been collected. (This assumes a chosen plaintext attack is 
feasible, which is the usual conservative assumption.)  In other words, don't look for 
a needle in a haystack -- take the entire haystack.

After all, if I am trying to steal credit card numbers, I don't care much whose credit card it is --
I'm not trying to target Bill Gates or Donald Trump specifically -- I'll settle for yours or 
almost anybody else's.

In this scenario, increasing the number of KEKs that are used actually _increases_ 
my chances of success, for it gives me that many more ciphertext examples to look at,
assuming that success is measured in terms of how many keys are cracked in a
given amount of time, rather than how long it takes to crack a specific key.

Bob

>>> David Wagner <[email-masked]> 02/15/99 03:42PM >>>
> David:
> 
> I had the same reaction to the 4 billion wrapped keys; however, there are
> two reasons why we should address this issue.  First, when mail list keys
> are used, the same KEK is used to encrypt CEKs for every message sent to
> the mail list.  Depending on the activity on the mail list ad the
> cryptoperiod of the KEK, the 4 billion wrapped keys might actually happen,
> especially if severs ever communicated with each other using this facility.

Ok.  I certainly support a conservative approach!

But I must say, my feeling is that if you ever encrypt 2^32 session keys
under the same KEK, "birthday"-style weaknesses will be in the noise:
you'll be in far-deeper trouble, because that KEK will start to look like
an awfully fat target.
In this scenario, I don't think the adversary is going to bother attacking
the crypto (especially when this only divulges partial information about
two session keys).
Instead, he'll go after your KEK by other means (bribe your cleaning service
to Trojan your computer, suck signal off the power lines, send a TEMPEST
van in your direction, break in to your computer, social engineer his way
into your secure facility, take a job at your company as a janitor, etc.)

The right defense is to refresh your KEK's more frequently.  (For instance,
IPSEC expires keys based not just on time but also on # of blocks encrypted.)
I'd argue that this is just prudent cryptographic hygiene.  And once you do
this, the cryptanalytic attacks go away.

Taking this up a level, my initial reaction is that ietf-smime is optimizing
for the wrong quantity.

Maximizing the number of session keys you can encrypt under the same KEK
is a second-order concern.  It seems much more important to try really hard
to reduce the risk that someone finds a subtle bug in your protocol.

(And, if what I've heard is correct, subtle protocol properties are exactly
the reason ietf-smime is devoting so much effort to key wrapping techniques.)

If you accept this, then the complicated constructions proposed earlier
may be exactly the wrong way to go; simplicity is arguably the most crucial
quantity to optimize for.
(And some provable security results can't hurt, either.)

(Of course, simplicity is only a heuristic.  For instance, Boyko's recent
results on all-or-nothing transforms look very promising, and deserve more
investigation.  Even though the construction is not quite as simple as e.g.
encrypt-and-MAC, provable security results are a great way to reduce the
risk of subtle protocol failures.
[One warning is that the proofs depend on the "random oracle" model and
thus do not necessarily transfer to real-world scenarios -- but they are
still very useful as validation that the basic approach is likely to be
sound.])

>  Second, given more time a cryptanalyst might find a better attack.  I do
> not like to start a standard's life with known flaws.

Yes.  This is a very good point, and normally this would be a very telling
criticism.  There's a saying: "attacks always get better".

However, I feel that this case is different.  Remember, Kaliski's attack
(did I get the author right?) meets the proven lower bounds on security
very closely.  I would argue that in fact the existence of the attack
should reassure us that the proofs of security were on the right track,
rather than raising concerns that better attacks might be "out there".

> I hope that others on this list will respond to your proposal.

Me too...  As a newbie to ietf-smime, I would definitely welcome feedback
(and/or criticism: even "you have no clue, go away!")...

---

From: "Don Johnson" <[email-masked]>
Date: Tue, 16 Feb 1999 21:37:09 -0500

Just for the record, text attacks such as Burt mentioned were discussed by
Coppersmith, Johnson and Matyas in their paper on CBCM mode of Triple DES
as a justification for considering it in ANSI X9.  They might have been
known before that, but the ref in the HAC is to that paper, so I know of no
earlier ref.

Don J.

"Bob Jueneman" <[email-masked]> on 02/16/99 08:53:37 PM

To:   [email-masked], [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] (bcc: Don Johnson/Certicom)
Subject:  Re: A New Triple-DES Key Wrap Algorithm

David,

The reason why I got interested in this subject at all was that I realized
that within
Novell's cryptographic architecture we wrap all sorts of keys, and when a
possible
attack was pointed out I became concerned.

I understand Russ Housley's point about wanting to solve this problem for
S/MIME --
that is his charter, and he wants to deliver a product.  Admirable
dedication.  And I
certainly agree with you that there are other, probably more effective ways
to
compromise S/MIME. than by mailing a billion keys around!

But as a vendor, I don't want to have to solve the key wrapping problem one
way
for S/MIME, plus N other ways for the next N protocols to come along.

Believe me, it is very tough to get the attention of the real experts in
this area,
and so once the problem was raised, I think we should solve it as best we
can,
once and for all. The S/MIME spec will then make a convenient point of
reference
for something that was done right.

For that reason, then, I would tend to dismiss any and all arguments about
whether
some particular attack might or might not be feasible in an S/MIME context
-- that type of
subtlety is exceedingly hard to get right, and besides I want a more
general purpose
solution.

Although Steve Kent's argument about the cost of changing keys often is
quite valid,
your argument about wanting to refresh your KEKs more often is NOT
necessarily
the way to improve security. It depends upon the threat.

Most approaches to brute force attacks try to speed up the number of key
search
operations that can be done simultaneously or in parallel, e.g., the recent
success
at the RSA conference of the EFF's Deep Crack engine in combination with
lots of
distributed computers, all working on the same challenge cipher.

But there is another approach, which I call the vacuum cleaner technique,
where you
don't target any specific key, but rather you suck up million or billions
of keys and
process all of them simultaneously. With this approach, for every new key
that is
tried, either singly or in parallel, the attacker looks at billions of
ciphertexts to see
if the result of encrypting a chosen plaintext with a given key matches any
one of the
ciphertexts that have been collected. (This assumes a chosen plaintext
attack is
feasible, which is the usual conservative assumption.)  In other words,
don't look for
a needle in a haystack -- take the entire haystack.

After all, if I am trying to steal credit card numbers, I don't care much
whose credit card it is --
I'm not trying to target Bill Gates or Donald Trump specifically -- I'll
settle for yours or
almost anybody else's.

In this scenario, increasing the number of KEKs that are used actually
_increases_
my chances of success, for it gives me that many more ciphertext examples
to look at,
assuming that success is measured in terms of how many keys are cracked in
a
given amount of time, rather than how long it takes to crack a specific
key.

Bob

Instead, he'll go after your KEK by other means (bribe your cleaning
service

The right defense is to refresh your KEK's more frequently.  (For instance,
IPSEC expires keys based not just on time but also on # of blocks
encrypted.)
I'd argue that this is just prudent cryptographic hygiene.  And once you do
this, the cryptanalytic attacks go away.

Taking this up a level, my initial reaction is that ietf-smime is
optimizing
for the wrong quantity.

(And, if what I've heard is correct, subtle protocol properties are exactly
the reason ietf-smime is devoting so much effort to key wrapping
techniques.)

---

From: Burt Kaliski <[email-masked]>
Date: Thu, 18 Feb 1999 07:34:00 -0800

Regarding Russ's question:

> Has the double-encryption approach that we are considering been analyzed
> as
> an AONT?  If so, how does it stack up when compared to OAEP?
> 
I'm not aware of any similar analysis on double-encryption, though it would
be an interesting (and not necessarily easy) research exercise. I've asked
Victor Boyko if he's interested in taking a look.

Responding to Bob Jueneman's earlier suggestion:

	In other words make the use of a "salt" in the message compulsory
and
	use the mailing list key in place of the DH shared secret (ZZ). This
	would then allow the same mailing list key to be used multiple times
	because the KEK would be different with each salt.

I think this is architecturally a nice approach, since with static-static
Diffie-Hellman, ZZ is a shared key between two users, and KEKs are derived
from it. The goal is to use a KEK only once in either setting.

-- Burt

---

From: Burt Kaliski <[email-masked]>
Date: Thu, 18 Feb 1999 07:25:12 -0800

Right, the 2^32 limitation for a 64-bit block cipher in CBC mode is not a
new result, though I'm not sure how far back it goes. I've merely made the
observation that due to those limitations, it may not be appropriate to
encrypt a message containing a key and fixed padding in CBC mode. Encrypting
an appropriate function of the message (e.g. OAEP) or encrypting twice is
better.

-- Burt

> ----------
> From: 	Don Johnson[SMTP:[email-masked]]
> Sent: 	Tuesday, February 16, 1999 9:37 PM
> To: 	Bob Jueneman
> 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]

---

From: Paul Van Oorschot <[email-masked]>
Date: Fri, 26 Feb 1999 13:43:43 -0500

Russ - if at all possible, please use a standard technique (e.g. OAEP per
one of the emerging standards) rather than inventing a new customized
scheme.  

Paul.

> Sent: 	Friday, February 26, 1999 1: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]; Tolga Acar;
> [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]
> 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
> >>
> >>Triple-DES Key Wrap
> >>    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

---

From: "Don Johnson" <[email-masked]>
Date: Fri, 26 Feb 1999 14:19:35 -0500

Russ,

Using a random IV for each encryption helps ensure that each block is
encrypted with the same strength, so my previous concerns about weaknesses
at the ends goes away.

Don Johnson

Russ Housley <[email-masked]> on 02/26/99 12:51:44 PM

To:   "Bob Jueneman" <[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], "Tolga Acar"
      <[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:  Re: A New Triple-DES Key Wrap Algorithm

Bob:

Russ

At 10:50 AM 2/22/99 -0700, Bob Jueneman wrote:
>that is a result of the constant IV construction. For that reason, I would
resulting
possible
>it isn't necessary to actually know the plaintext -- it is sufficient that
every
>key -- just a few would be useful.  For example, if I were trying to carry
on
attack
million
available.
gedanken
the
double
path,
>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
(A-B-A) for
>This can be optimized by saving the key expansion of the first encryption,
and
potentially be
>key length is required, so we don't have to keep re-analyzing this problem
>If we can define appropriate algorithm IDs, I'm willing and eager to adopt
such
the
compare

---

From: "Don Johnson" <[email-masked]>
Date: Fri, 26 Feb 1999 14:25:13 -0500

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" <[email-masked]> on 02/26/99 01:38:19 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], "Tolga Acar" <[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:  Re: A New Triple-DES Key Wrap Algorithm

Russ:

Bob

Bob:

Russ

resulting
possible
every
on
attack
million
available.
gedanken
the
double
path,
(A-B-A) for
and
potentially be
such
the
compare

---

From: Kevin Kingdon <[email-masked]>
Date: Fri, 26 Feb 1999 11:57:22 -0800

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:[email-masked]]
		Sent:	Friday, February 26, 1999 11:25 AM
		To:	Bob Jueneman
		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]; Tolga Acar; [email-masked]; [email-masked]; Burt
Kaliski; [email-masked]; [email-masked]; [email-masked]; Ron
Rivest; [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]; [email-masked]
		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" <[email-masked]> on 02/26/99 01:38:19
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], "Tolga Acar"
<[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:  Re: A New Triple-DES Key Wrap Algorithm

		Russ:

		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

		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

		resulting
		possible
		every
		on
		attack
		million
		available.
		gedanken
		the
		double
		path,
		(A-B-A) for
		and
		potentially be
		such
		the
		compare

---

From: "Don Johnson" <[email-masked]>
Date: Fri, 26 Feb 1999 16:46:34 -0500

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 <[email-masked]> on 02/26/99 02:57:22 PM

To:   Don Johnson/Certicom, Bob Jueneman <[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], Tolga Acar <[email-masked]>,
      [email-masked], [email-masked], Burt Kaliski
      <[email-masked]>, [email-masked], [email-masked],
      [email-masked], Ron Rivest <[email-masked]>,
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked]
Subject:  RE: A New Triple-DES Key Wrap Algorithm

Don,

not be structured? I thought that was what encryption was all about -
hiding

Kevin
          -----Original Message-----

          Bob, Russ,

          Don Johnson

          To:   [email-masked]

          Russ:

          Bob

          Bob:

          Russ

          resulting
          possible
          every
          on
          attack
          million
          available.
          gedanken
          the
          double
          path,
          (A-B-A) for
          and
          potentially be
          such
          the
          compare

---

From: "Bob Jueneman" <[email-masked]>
Date: Fri, 26 Feb 1999 15:26:27 -0700

Don,  I quite agree.  But regardless of whether we use 
double encryption or OAEP, the masking should completely 
obfuscate any structure that ASN.1 would impose.

Bob

>>> "Don Johnson" <[email-masked]> 02/26/99 12:25PM >>>
Bob, Russ,

Don Johnson

To:   [email-masked] 

Russ:

Bob

Bob:

Russ

resulting
possible
every
on
attack
million
available.
gedanken
the
double
path,
(A-B-A) for
and
potentially be
such
the
compare

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 27 Feb 1999 14:05:35 (NZDT)

>I have a pseudo-random number generator that I am working on for a different
>project.  I put a 0x484848...484848 seed into it and generated the IVs.  Since
>no one has ever looked at that design I will get some new ones from a better
>source.
 
The issue isn't the quality of the numbers, it's a question of verifiability -
the numbers should be from a source which anyone can check, eg hex digits of
pi, e, sqrt( 2 ), whatever.  This is why algorithms like the MDx's and SHA use
well-known, verifiable values.
 
Peter.

---

From: Burt Kaliski <[email-masked]>
Date: Mon, 1 Mar 1999 11:35:06 -0800

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 

> Sent: 	Friday, February 26, 1999 4:46 PM
> To: 	Kevin Kingdon
> Cc: 	Bob Jueneman; [email-masked]; [email-masked]; [email-masked];
> [email-masked]; [email-masked]; Burt Kaliski; [email-masked];
> [email-masked];

---

From: "Tolga Acar" <[email-masked]>
Date: Mon, 01 Mar 1999 14:39:08 -0700

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 <[email-masked]> 3/1/99 12:35:06 >>>

-- Burt