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:BJUENEMAN(_at_)novell(_dot_)com]
Sent: Tuesday, February 02, 1999 4:55 PM
To: djohnson(_at_)certicom(_dot_)com; housley(_at_)spyrus(_dot_)com
Cc: cme(_at_)ACM(_dot_)ORG; berson(_at_)anagram(_dot_)com;
mjmarkowitz(_at_)attmail(_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;
denning(_at_)cs(_dot_)cosc(_dot_)georgetown(_dot_)edu;
smid(_at_)csmes(_dot_)ncsl(_dot_)nist(_dot_)gov; omura(_at_)cylink(_dot_)com;
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; Bob Jueneman; Tolga Acar;
merkle(_at_)parc(_dot_)xerox(_dot_)com;
BSnow(_at_)radium(_dot_)ncsc(_dot_)mil; Burt Kaliski; ekr(_at_)rtfm(_dot_)com;
jlinn(_at_)securitydynamics(_dot_)com; ams(_at_)terisa(_dot_)com; Ron Rivest;
balenson(_at_)tis(_dot_)com;
denny(_at_)tis(_dot_)com; acc(_at_)tycho(_dot_)ncsc(_dot_)mil;
jhs(_at_)tycho(_dot_)ncsc(_dot_)mil; desmedt(_at_)uwm(_dot_)edu;
smatyas(_at_)vnet(_dot_)ibm(_dot_)com
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
bjueneman(_at_)novell(_dot_)com
1-801-861-7387