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

From: Burt Kaliski <[email-masked]>
Date: Wed, 3 Feb 1999 13:48:55 -0800

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]
> Subject: 	Re: A New Triple-DES Key Wrap Algorithm
> 
> 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
> 
> 
>

---

From: Dr Stephen Henson <[email-masked]>
Date: Thu, 04 Feb 1999 00:25:12 +0000

Apologies if I've missed the point here but...

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.

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: Carl Ellison <[email-masked]>
Date: Wed, 03 Feb 1999 21:38:04 -0800

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

>implemented with appropriate settings, resists the birthday attacks on the

Burt and Don,

	I'm not sure what Don intended, but I was reminded of one of Ron Rivest's 
papers (in Cryptologia) -- proposing bidirectional encryption when the 
system is easier to break in one direction than the other.

	In the case of CBC mode, one could encrypt a long block twice, as Don 
suggested, but index the blocks in reverse order the second time.  The IV 
could be 0 for both passes.

	I haven't tried analyzing this mode of operation yet, but it has a pleasant 
symmetry.

 - Carl

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