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
Network Security Development
Novell, Inc.
122 East 1700 South
Provo, UT 84606
bjueneman(_at_)novell(_dot_)com
1-801-861-7387
Burt Kaliski <burt(_at_)RSA(_dot_)COM> 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: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