ietf-smime
[Top] [All Lists]

Comments on CMS from Burt Kaliski

1999-01-28 12:50:28
Significant issues are raised in Burt Kaliski's note.

Russ



From: Burt Kaliski <burt(_at_)rsa(_dot_)com>
To: "'housley(_at_)spyrus(_dot_)com'" <housley(_at_)spyrus(_dot_)com>
Cc: "Linn, John" <jlinn(_at_)rsa(_dot_)com>
Subject: Comments on CMS
Date: Mon, 25 Jan 1999 13:53:00 -0800
X-Mailer: Internet Mail Service (5.5.2232.9)

Dear Russ --

Here are some comments on
http://search.ietf.org/internet-drafts/draft-ietf-smime-cms-10.txt. Feel
free to forward this to the S/MIME discussion list.

Some general points:

* RFC 2437 can now be referenced rather than RFC 2313 for PKCS #1. As a
result Section 12.2.2 no longer needs to give the SHA-1 extension to PKCS
#1 RSA signatures, as it's supported by RFC 2437. 

* Section 12.3.2.1 should be more explicit about how RSA encryption is
employed for key wrapping (i.e., that the message to be encrypted with
RSAES-PKCS1-v1_5 is the key). It should also state whether parity changes
are required on DES keys, similar to Section 12.6.2.

* It would be helpful to state in step 1 of Section 12.6.2 what parity
setting is assumed for DES. Is it necessary to set parity? This is not
required when wrapping a DES key with an RSA key.

Regarding the key wrapping algorithm itself, one problem I see is that the
parts of the CEK are encrypted essentially independently of each other.
Although there is chaining through CBC mode, an opponent learns
plaintext-ciphertext pairs for the underlying encryption algorithm. The
opponent can thus detect collisions in the plaintext space.

Specifically, consider what happens when wrapping a triple-DES CEK with
some symmetric algorithm. There will be five blocks to be encrypted under
a KEK with the symmetric algorithm. With chaining, this will be done as

  A = Encrypt (IV xor (salt || key<0..3>))
  B = Encrypt (A xor key<4..11>)
  C = Encrypt (B xor key<12..19>)
  D = Encrypt (C xor (key<20..23> || keycheck<0..3>))
  E = Encrypt (D xor (keycheck<4..7> || 04 04 04 04))

where key<0..23> is the triple-DES CEK and ABCDE is the wrapped CEK. An
opponent will see ABCDE and knows IV.

Now suppose that many CEKs are wrapped with the same KEK. (The CEKs need not
be different.) With high probability, there will be a collision between
blocks of wrapped CEKs after about 2^32 encryptions. Let ABCDE and
A*B*C*D*E* be the two wrapped CEKs, let key and key* be the two CEKs, and
suppose A = E* (i.e., the first block of one wrapped CEK equals the last
block of the other wrapped CEK). Since Encrypt is a permutation, the
opponent knows that

  IV xor (salt || key<0..3>) = D* xor (keycheck*<4..7> || 04 04 04 04)

Although salt and keycheck* are unknown, the opponent can solve for
key<0..3>:

  key<0..3> = IV<4..7> xor D*<4..7> xor 04 04 04 04

Through collisions in other blocks, the opponent can solve for other parts
of CEKs and for the difference between parts of CEKs. If the same CEK is
wrapped many times with the KEK, the opponent may gather enough
information to solve for the entire CEK. If different CEKs are wrapped
with the same KEK, an opponent may learn information about the
relationship between the CEKs. If the opponent has somehow obtained one
CEK encrypted with a KEK (perhaps by being a legitimate recipient of a
message encrypted with that CEK), the opponent may then be able to solve
for the other CEK.

The main problem is that all these attacks require only about 2^32 wrapped
CEKs, which is probably not enough for many applications, particularly given
the 2^112 security level intended by the use of triple-DES.

One way to avoid this problem is to limit the number of times a KEK can be
employed so that the probability of collision remains small. However, in
practice this can be burdensome. A partial solution is to make the padding
random rather than 04 04 04 04, but this only addresses the first attack
outlined above, not other attacks that find relationships between parts of
CEKs.

A potential improvement is an OAEP-like construction, where the CEK is
formatted as in PKCS #1 EME-OAEP (section 9.1.1 of RFC 2437), then
encrypted with the KEK. I suppose the key expansion would be larger in
such an approach than in what is proposed in the Internet-Draft, but it
would also build on the same formatting for wrapping with RSA keys, and
avoid the attacks just described. The CEK parts would not be encrypted
separately of one another, but as a whole, having been mixed together
first with OAEP.

-- Burt

Burt Kaliski, Chief Scientist
RSA Laboratories - http://www.rsa.com 
20 Crosby Drive, Bedford, MA 01730 USA
+1 781 687 7057; fax: +1 781 687 7213; burt(_at_)rsa(_dot_)com



<Prev in Thread] Current Thread [Next in Thread>
  • Comments on CMS from Burt Kaliski, Russ Housley <=