Subject: [ietf-tls] RSA-OAEP in TLS (was Re: WG Last Call for "AES Ciphersuites for TLS")

From: David Hopwood <[email-masked]>
Date: Fri, 01 Jun 2001 16:14:54 +0100

Bodo Moeller wrote:
> On Thu, May 31, 2001 at 11:35:43AM -0400, Housley, Russ wrote:
> [...]
> > On the other hand, RSA-OAEP is being used in many areas. [...]
> > I am proposing a well studied, and reasonably well adopted technique as
> > the successor to PKCS#1 v1.5 for TLS.
> 
> RSA-OAEP is "well-studied" only as of the next CRYPTO conference.
> The original security argument was recently found to be flawed [1], a
> new proof relying on a stronger assumption was given later [2].

I suppose I'm being a bit pedantic here, but technically [2] does not
make a stronger assumption; it gives a looser reduction. Four things
need to be taken account when interpreting a security proof:
 - whether the proof is correct (not to be taken for granted!)
 - the strength of the assumptions,
 - the "model" in which the proof is set (standard, random oracle,
   generic group, etc.)
 - the tightness of the reduction from breaking the assumptions to
   breaking the scheme.

In addition, standards committees have a nasty habit of making changes
to schemes that have the effect of breaking the security proof.

However, I fully agree with the point that OAEP, at least until *very*
recently, has not been "well studied". In fact, it is a good case study
in the difficulties involved in verifying and interpreting security proofs.

> CRYPTO 2001 also has a paper "A Chosen Ciphertext Attack On RSA
> Optimal Asymmetric Encryption Padding (OAEP) as Standardized In PKCS #1"
> by James Manger.  I am not aware of any preprints of this one, or
> of the details of the attack.

Interesting. I've cc:d James Manger; perhaps he can give a brief
description.

> [1]  Victor Shoup: "OAEP Reconsidered". -- CRYPTO 2001, to appear.
>      Preprint available from <URL: http://shoup.net/papers/> and
>      <URL: http://eprint.iacr.org/2000/060/>.
> 
> [2]  Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval and Jacques Stern:
>      "RSA-OAEP is Secure Under the RSA Assumption" -- CRYPTO 2001, to appear.
>      Preprint available from <URL: http://eprint.iacr.org/2000/061/>.

-- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

---
You are currently subscribed to ietf-tls as: [email-masked]
To unsubscribe send a blank email to [email-masked]

---

From: Bodo Moeller <[email-masked]>
Date: Mon, 4 Jun 2001 00:53:53 +0200

> make a stronger assumption; it gives a looser reduction.

You are absolutely right.  For OAEP in general, [2] makes a stronger
assumption; but in the specific case of RSA-OAEP, this amounts to a
looser reduction for the same assumption.

[Nitpicking OD: Even more technically, in terms of exact security a
looser reduction implies a stronger assumption.]

[...]
> to schemes that have the effect of breaking the security proof.

Actually in some cases it were the inventors of the methods who
introduced such errors.  (E.g., see Marc Joye, Jean-Jacques
Quisquater, Moti Yung: "On the Power of Misbehaving Adversaries and
Security Analysis of the Original EPOC" -- CT-RSA 2001, LNCS 2020,
208--222.)

-- 
Bodo Möller <[email-masked]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036

---