Comments on CMS from Burt Kaliski

Russ Housley <> Thu, 28 January 1999 20:52 UTC

Received: from ( []) by (8.8.5/8.8.7a) with ESMTP id PAA08683 for <>; Thu, 28 Jan 1999 15:52:13 -0500 (EST)
Received: (from majordomo@localhost) by (8.8.8/8.8.5) id LAA02993 for ietf-smime-bks; Thu, 28 Jan 1999 11:50:28 -0800 (PST)
Received: from ( []) by (8.8.8/8.8.5) with ESMTP id LAA02986 for <>; Thu, 28 Jan 1999 11:50:24 -0800 (PST)
Received: from ([]) by (8.8.8/8.8.8) with SMTP id OAA28521 for <>; Thu, 28 Jan 1999 14:53:02 -0500
Message-Id: <4.1.19990128144545.009e2250@>
X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1
Date: Thu, 28 Jan 1999 14:46:48 -0500
From: Russ Housley <>
Subject: Comments on CMS from Burt Kaliski
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Precedence: bulk
List-Archive: <>
List-Unsubscribe: <>

Significant issues are raised in Burt Kaliski's note.


>From: Burt Kaliski <>
>To: "''" <>
>Cc: "Linn, John" <>
>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
> 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 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 - 
>> 20 Crosby Drive, Bedford, MA 01730 USA
>> +1 781 687 7057; fax: +1 781 687 7213;