Comments on CMS from Burt Kaliski

Russ Housley <housley@spyrus.com> Thu, 28 January 1999 20:52 UTC

Received: from mail.proper.com (mail.proper.com [206.86.127.224]) by ietf.org (8.8.5/8.8.7a) with ESMTP id PAA08683 for <smime-archive@odin.ietf.org>; Thu, 28 Jan 1999 15:52:13 -0500 (EST)
Received: (from majordomo@localhost) by mail.proper.com (8.8.8/8.8.5) id LAA02993 for ietf-smime-bks; Thu, 28 Jan 1999 11:50:28 -0800 (PST)
Received: from thehub.knight-hub.com (root@thehub.knight-hub.com [205.177.16.3]) by mail.proper.com (8.8.8/8.8.5) with ESMTP id LAA02986 for <ietf-smime@imc.org>; Thu, 28 Jan 1999 11:50:24 -0800 (PST)
Received: from rhousley_laptop.spyrus.com ([205.177.169.194]) by thehub.knight-hub.com (8.8.8/8.8.8) with SMTP id OAA28521 for <ietf-smime@imc.org>; Thu, 28 Jan 1999 14:53:02 -0500
Message-Id: <4.1.19990128144545.009e2250@209.172.119.123>
X-Sender: rhousley#mail.spyrus.com@209.172.119.123
X-Mailer: QUALCOMM Windows Eudora Pro Version 4.1
Date: Thu, 28 Jan 1999 14:46:48 -0500
To: ietf-smime@imc.org
From: Russ Housley <housley@spyrus.com>
Subject: Comments on CMS from Burt Kaliski
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Sender: owner-ietf-smime@imc.org
Precedence: bulk
List-Archive: <http://www.imc.org/ietf-smime/mail-archive/>
List-Unsubscribe: <mailto:ietf-smime-request@imc.org?body=unsubscribe>

Significant issues are raised in Burt Kaliski's note.

Russ



>From: Burt Kaliski <burt@rsa.com>
>To: "'housley@spyrus.com'" <housley@spyrus.com>
>Cc: "Linn, John" <jlinn@rsa.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@rsa.com
>>