Subject: Why KEM?, RE: Charter Update

From: Mike Just <[email-masked]>
Date: Wed, 1 May 2002 13:14:03 -0400

It's not clear to me that there is consensus on this path (unfortunately,
there seemed to be no reaction on either side to this email) as reflected in
the latest version of the Charter.

I'd like to re-iterate Robert's concerns (from his e-mail of 04/19/2002) and
ask the fundamental question: Why are we even considering KEM when we
already have a sufficient solution with OAEP?

Mike 

-----Original Message-----
From: Housley, Russ [mailto:[email-masked]]
Sent: Wednesday, April 24, 2002 5:14 PM
To: [email-masked]
Subject: RE: Charter Update

Is the WG consensus that RSA-OAEP, RSA-KEM, and AES should be in separate, 
independent documents.  This would allow AES to be used with any of the key 
management techniques?

Russ

---

From: "Housley, Russ" <[email-masked]>
Date: Wed, 01 May 2002 13:21:30 -0400

Mike:

I think that I did respond to Robert's question.  At IETF 53, I gave
a presentation on this subject.  You can see the slides at
http://www.ietf.org/proceedings/02mar/slides/smime-1/index.html.

Russ

At 01:14 PM 5/1/2002 -0400, Mike Just wrote:

It's not clear to me
that there is consensus on this path (unfortunately, there seemed to be
no reaction on either side to this email) as reflected in the latest
version of the Charter.

I'd like to re-iterate Robert's concerns (from his e-mail of
04/19/2002) and ask the fundamental question: Why are we even considering
KEM when we already have a sufficient solution with OAEP?

Mike

-----Original Message-----

From: Housley, Russ
[mailto:[email-masked]]

To: [email-masked]

Is the WG consensus that RSA-OAEP, RSA-KEM, and AES should
be in separate,

independent documents.  This would allow AES to be used
with any of the key

management techniques?

Russ

---

From: Mike Just <[email-masked]>
Date: Wed, 1 May 2002 13:33:09 -0400

Thanks Russ.  I did manage to look at your slides when you first posted them
to the list on April 17th.  I found them very helpful.   However, I think
Robert has raised some good points (based on the issues claimed in your
slides) that question the motivation for even considering a move to KEM.
I've attached his email below for your convenience.  I think we have chosen
a very good direction already with OAEP and am not convinced that we need to
change this.  
 
Mike

---- Robert's email of 04/19/2002 ---

-----Original Message-----
From: Robert Zuccherato [mailto:[email-masked]]
Sent: Friday, April 19, 2002 10:46 AM
To: 'Housley, Russ'; [email-masked]
Subject: RE: Charter Update

Russ; 

Having not attended the Minneapolis meeting I must say that I was very
surprised by your recommendation to drop OAEP as the MUST implement key
transport mechanism with AES in favour of KEM.  It wasn't all that long ago
that you were attempting to get everyone (S/MIME, TLS, X9.44) to agree on
requiring OAEP with AES as a method of transitioning to OAEP from PKCS#1
v1.5.  Partly as a result of that effort, implementations of OAEP have
started to appear (e.g. OpenSSL) and transitions to OAEP can actually now
start to occur.  If we are going to introduce a new MUST algorithm, and thus
additional uncertainty about what to use and how to transition, we really
should have a good reason.

In your presentation you say that KEM has better security proofs.  That may
be, however, OAEP is still secure.  No actual weaknesses in it have been
found.  On RSA's website there is a description of recent results on OAEP
that says "... it makes little sense replacing OAEP with a "more secure"
encoding method, because if a CCA2 adversary is able to break RSAEP-OAEP,
then she will be able to break RSAEP equipped with any encoding method (if
maybe slightly less efficiently)."  (
http://www.rsasecurity.com/rsalabs/rsa_algorithm/oaep_security.html
<http://www.rsasecurity.com/rsalabs/rsa_algorithm/oaep_security.html> )
Thus, there is no need to introduce KEM for security reasons.

Your presentation also lists some standards that already include KEM.
However, all of the ones that are listed except TLS also specify OAEP (ANSI
X9.44, IEEE P1363, ISO/IEC 18033-2, PKCS#1, S/MIME).  TLS, while it
specifies a variant of KEM, doesn't actually use anything that is compatible
with the KEM that S/MIME (and the other groups listed) would be using.  I
would also like to point out that XML Encryption has OAEP as a required key
transport method.  At this point it does seem like OAEP is starting to get
adopted by other groups and thus introducing KEM now seems to be
counterproductive.

It is true that with OAEP the message length is bounded.  However, for our
requirements here, is that really an issue?  

For these reasons I think we should reconsider your proposal to use RSA-KEM
instead of RSA-OAEP in draft-ietf-smime-aes-alg.

Robert Zuccherato 
Entrust, Inc. 

--------------------------------------------

-----Original Message-----
From: Housley, Russ [mailto:[email-masked]]
Sent: Wednesday, May 01, 2002 1:22 PM
To: Mike Just
Cc: [email-masked]
Subject: Re: Why KEM?, RE: Charter Update

Mike:

I think that I did respond to Robert's question.  At IETF 53, I gave a
presentation on this subject.  You can see the slides at
http://www.ietf.org/proceedings/02mar/slides/smime-1/index.html
<http://www.ietf.org/proceedings/02mar/slides/smime-1/index.html> .

Russ

Mike 

-----Original Message----- 
From: Housley, Russ [ mailto:[email-masked]
<mailto:[email-masked]> ] 
Sent: Wednesday, April 24, 2002 5:14 PM 
To: [email-masked] 
Subject: RE: Charter Update 

Russ

---

From: "Kaliski, Burt" <[email-masked]>
Date: Mon, 6 May 2002 14:20:22 -0400

Russ asked me to join this discussion to explain the motivation for KEM.
(Please cc: me on further messages on this thread as I'm not a subscriber to
the ietf-smime list.) 
RSA-KEM's primary advantages over RSA-OAEP are: 
1. RSA-KEM's security bounds are tighter. RSA-KEM has been proved (in the
random oracle model) to be very close in security to the RSA problem.
RSA-OAEP has been proved (in the same model) to offer security that grows in
proportion to the security of the RSA problem, but for typical RSA key sizes
the provable level of security is not very high. While no attacks faster
than solving the RSA problem are known against RSA-OAEP if it is properly
implemented, it would be better if faster attacks could be ruled out
explicitly. 
2. RSA-KEM fits better architecturally. RSA-KEM follows the model described
by Victor Shoup, which combines a public-key "encapsulation" operation with
a symmetric key operation, such as the AES KeyWrap. The same symmetric key
operation can be combined with different public-key methods (RSA,
Diffie-Hellman, elliptic curve). It can also be used for wrapping a
symmetric key with another symmetric key. Thus, in future versions of
S/MIME, AES content-encryption keys can all be wrapped with AES KeyWrap. The
only difference among the public key methods would be how the wrapping key
is derived. RSA-OAEP, in contrast, uses a different technique than other
public-key methods (OAEP formatting) for processing the symmetric keys. 
RSA-OAEP is still fine to use, but RSA-KEM is better. As part of continually
improving the infrastructure, I believe it is worthwhile to introduce
support for RSA-KEM as standards are updated. Since S/MIME implementations
are being upgraded to support AES, this is a convenient time to introduce a
more robust public-key method as well. 
-- Burt Kaliski
RSA Laboratories 
		From: Mike Just <[email-masked]>
		To: "'Housley, Russ'" <[email-masked]>
		Cc: [email-masked]
		Subject: RE: Why KEM?, RE: Charter Update
		Date: Wed, 1 May 2002 13:33:09 -0400 
		X-Mailer: Internet Mail Service (5.5.2653.19)
		
		Thanks Russ. I did manage to look at your slides when you
first posted them to the list on April 17th. I found them very helpful.
However, I think Robert has raised some good points (based on the issues
claimed in your slides) that question the motivation for even considering a
move to KEM. I've attached his email below for your convenience. I think we
have chosen a very good direction already with OAEP and am not convinced
that we need to change this. 
		
		Mike

		---- Robert's email of 04/19/2002 --- 
			-----Original Message----- 
			From: Robert Zuccherato
[<mailto:[email-masked]>] 
			Sent: Friday, April 19, 2002 10:46 AM 
			To: 'Housley, Russ'; [email-masked] 
			Subject: RE: Charter Update
			
			Russ; 
			
			Having not attended the Minneapolis meeting I must
say that I was very surprised by your recommendation to drop OAEP as the
MUST implement key transport mechanism with AES in favour of KEM. It wasn't
all that long ago that you were attempting to get everyone (S/MIME, TLS,
X9.44) to agree on requiring OAEP with AES as a method of transitioning to
OAEP from PKCS#1 v1.5. Partly as a result of that effort, implementations of
OAEP have started to appear (e.g. OpenSSL) and transitions to OAEP can
actually now start to occur. If we are going to introduce a new MUST
algorithm, and thus additional uncertainty about what to use and how to
transition, we really should have a good reason.
			
			In your presentation you say that KEM has better
security proofs. That may be, however, OAEP is still secure. No actual
weaknesses in it have been found. On RSA's website there is a description of
recent results on OAEP that says "... it makes little sense replacing OAEP
with a "more secure" encoding method, because if a CCA2 adversary is able to
break RSAEP-OAEP, then she will be able to break RSAEP equipped with any
encoding method (if maybe slightly less efficiently)."
(<http://www.rsasecurity.com/rsalabs/rsa_algorithm/oaep_security.html>)
Thus, there is no need to introduce KEM for security reasons.
			
			Your presentation also lists some standards that
already include KEM. However, all of the ones that are listed except TLS
also specify OAEP (ANSI X9.44, IEEE P1363, ISO/IEC 18033-2, PKCS#1, S/MIME).
TLS, while it specifies a variant of KEM, doesn't actually use anything that
is compatible with the KEM that S/MIME (and the other groups listed) would
be using. I would also like to point out that XML Encryption has OAEP as a
required key transport method. At this point it does seem like OAEP is
starting to get adopted by other groups and thus introducing KEM now seems
to be counterproductive.
			
			It is true that with OAEP the message length is
bounded. However, for our requirements here, is that really an issue? 
			
			For these reasons I think we should reconsider your
proposal to use RSA-KEM instead of RSA-OAEP in draft-ietf-smime-aes-alg.
			
			Robert Zuccherato 
			Entrust, Inc. 
		
			-----Original Message----- 
			From: Housley, Russ
[<mailto:[email-masked]>] 
			Sent: Wednesday, May 01, 2002 1:22 PM 
			To: Mike Just 
			Cc: [email-masked] 
			Subject: Re: Why KEM?, RE: Charter Update
			
			Mike:
			
			I think that I did respond to Robert's question. At
IETF 53, I gave a presentation on this subject. You can see the slides at
<http://www.ietf.org/proceedings/02mar/slides/smime-1/index.html>.
			
			Russ

			
				It's not clear to me that there is consensus
on this path (unfortunately, there seemed to be no reaction on either side
to this email) as reflected in the latest version of the Charter. 
				I'd like to re-iterate Robert's concerns
(from his e-mail of 04/19/2002) and ask the fundamental question: Why are we
even considering KEM when we already have a sufficient solution with OAEP? 
				Mike 
				-----Original Message----- 
				From: Housley, Russ
[<mailto:[email-masked]>] 
				Sent: Wednesday, April 24, 2002 5:14 PM 
				To: [email-masked] 
				Subject: RE: Charter Update 

				Is the WG consensus that RSA-OAEP, RSA-KEM,
and AES should be in separate, 
				independent documents. This would allow AES
to be used with any of the key 
				management techniques? 
				
				Russ

---

From: Robert Zuccherato <[email-masked]>
Date: Tue, 7 May 2002 16:17:53 -0400

Burt;

I agree that those are definitely advantages of KEM over OAEP.  However, a
number of standards (1363, PKCS#1, etc.) have already specified OAEP and
some people have already implemented it.  S/MIME is currently on the -04
version of a draft that mandates OAEP with AES. Thus, without a demonstrated
weakness with OAEP I still don't see a reason to change.  I don't see the
tighter bounds for KEM and the better architectural fit as being worth the
trouble of starting to specify a new encryption padding method.  Doing so
will necessarily cause additional interoperability and implementation
issues.  We already have an adequate replacement for PKCS #1 v1.5, why do we
need another one?

	Robert.

> From: Kaliski, Burt [mailto:[email-masked]]
> Sent: Monday, May 06, 2002 2:20 PM
> To: [email-masked]'
> Cc: Housley, Russ; Kaliski, Burt

---

From: "Kaliski, Burt" <[email-masked]>
Date: Wed, 8 May 2002 11:30:59 -0400

Rob,
 
I agree that RSA-OAEP is adequate, and I realize it's hard to argue for
something "better" when what's there is good enough already.
 
In several standards efforts I'm involved in (NESSIE, ISO 18033, ANSI X9F1),
and in the research community, a preference is emerging for RSA-KEM over
RSA-OAEP. Over time, formal standards bodies may therefore give preference
to RSA-KEM (while still acknowledging RSA-OAEP and perhaps even PKCS #1 v1.5
encryption for compatibility). Eventually, this will lead to a stronger
motivation to add RSA-KEM to S/MIME and other protocols. The issue here is
whether to do so sooner rather than later.
 
By the way, RSA has no proprietary interest in RSA-KEM, nor am I aware of
any patents claimed by others at this point.
 
-- Burt

-----Original Message-----
From: Robert Zuccherato [mailto:[email-masked]]
Sent: Tuesday, May 07, 2002 4:18 PM
To: Kaliski, Burt; [email-masked]'
Cc: Housley, Russ
Subject: RE: Why KEM?, RE: Charter Update

Burt; 

        Robert.