Subject: [ietf-tls] AES, OAEP, and TLS

From: Win Treese <[email-masked]>
Date: Fri, 13 Jul 2001 14:36:54 -0400

[I tried to send this several days ago, but a conspiracy of mailer
failures kept it from appearing on the list. --WT]

Since I understood that NIST was encouraging the use of OAEP with AES
cryptosystems, I asked Tim Polk at NIST for some more
background. Here's what he said:

    The basic NIST position is that the standard PKCS #1 V1.5 padding can
    and should be improved upon.  As we transition to AES, we are already
    needing to support bigger keys, etc. so it makes sense to upgrade the
    padding at the same time.  We could probably argue forever about
    padding schemes, but OAEP presents a clear improvement that everyone
    should be able to support.

    The NIST strategy for RSA-based key management in AES ciphersuites
    will utilize OAEP padding.  We presume these cryptographic modules
    will be used to support a variety of protocols, so we want a padding
    technique that is secure for the broadest range of protocols.  The
    advantages of OAEP may not be relevant in some protocols, but it
    doesn't seem to present any problem in those protocols.

    We recognize that there is a cost, particularly when implementing new
    techniques in hardware.  However, many of these accelerators would
    need to be updated anyway to handle the larger key sizes that make
    sense now that we're using 128-bit and larger symmetric keys.

    NIST is also working to promote this position in the ANSI X9 standards
    community, in particular on the ANSI X9.44 RSA Key Management
    standard.  We would like to see standards in the IETF like TLS specify
    consistent ciphersuites as well.

Win Treese
Chair, TLS Working Group
[email-masked]

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

---

From: David Hopwood <[email-masked]>
Date: Fri, 20 Jul 2001 10:43:45 +0100

-----BEGIN PGP SIGNED MESSAGE-----

>     should be able to support.

In general, I'd strongly advise the people at NIST to read Victor Shoup's
paper [Sho01], and consider advocating Simple-RSA as another option to
RSA-OAEP. The main reason for that is that it provides non-malleability for
an arbitrarily long message, which is not achieved just by using RSA-OAEP to
encrypt a symmetric key. It's also simpler, and therefore probably less
vulnerable to the kind of implementation problems mentioned in James Manger's
recent paper [Man01]. The fact that the security reduction is 'tighter' is a
useful bonus, although the preceding two reasons are more important in
practice. I don't know Tim Polk's address; perhaps you could forward this
post to him.

However, that's almost beside the point for TLS: RFC 2246 already has an
effective and provably secure (see below) fix to PKCS #1 v1.5. Using that fix
was a good solution to Bleichenbacher's attack because it minimised
interoperability problems.

I've checked that the proof of Simple-RSA in [Sho01] can be applied almost
unchanged, treating the RSA key exchange as a Key Encapsulation Mechanism [*1].
This assumes that the computation of the handshake hashes can be modelled as
a random oracle, which is reasonable. The tightness of the reduction will be
worse than for Simple-RSA by a constant factor (for the single encryption
attack model), because the PKCS #1 v1.5 formatting and the non-random version
number mean that the block is not uniformly distributed on [0, n), but it will
still be better than the reduction given by the OAEP proof [*2].

(Incidentally, the nBound/q_D term in equation (8) of [Sho01] should be
q_D/nBound. This is such a strange error to make, that I think perhaps Shoup
may be checking whether anyone is actually paying attention to the detail of
security proofs.)

[*1] Technically, this doesn't prove non-malleability of the version number
     encrypted with the pre-master secret. There are good reasons to believe
     that that isn't a problem, and I was going to work the details more
     thoroughly before posting - but I'd better send this post now, given the
     limited time for the final call of the AES draft.

[*2] ... unless the pre-master secret is replaced by a random value when OAEP
     unpadding fails (i.e. the same method as used for PKCS #1), in which
     case the reduction for this variant of OAEP is as tight as Simple-RSA.

It's also necessary to consider the effect on the security of TLS against
compromise attacks - that is, in the situation where an attacker gets access
to the server, but can only make queries to a protected security module,
and the goal is to obtain enough information to impersonate the server
after access is lost. I haven't had time to study this in as much detail as
I'd like, but it appears that the choice of RSA-OAEP vs PKCS #1 v1.5 makes
no difference here, assuming the Gap RSA Assumption. (If the Gap RSA
Assumption is false, OTOH, then TLS's security against compromise attacks
is non-existant, and fixing that would require major changes.)

>     technique that is secure for the broadest range of protocols.

For new protocols, or for protocols where there is no good backward-
compatible fix to existing security problems, I agree entirely with
the second sentence above (except that I think Simple-RSA would better
satisfy that goal). If, OTOH, it is interpreted as meaning that existing
uses of RSA are to be replaced with RSA-OAEP (or any other scheme)
without looking carefully at the costs and benefits in each case, then
I would have to disagree, strongly.

>     The advantages of OAEP may not be relevant in some protocols, but it

It does present problems in many protocols (the first two of these don't
apply to TLS):

1. How do you encrypt messages that do not fit in one block? (Just replacing
   hybrid use of PKCS #1 v1.5 with OAEP is almost always the wrong answer.)

2. How do you negotiate the use of RSA-OAEP as opposed to whatever was used
   before? (This is *very easy* to get wrong. Adding a negotiation mechanism
   to a protocol that didn't previously have one is one of the most
   complicated and error-prone parts of protocol design. TLS's negotiation
   mechanism is has had more analysis than that of any other protocol I've
   seen, and it still has known security flaws, even though negotiation was
   designed into SSL 2.0 from the start.)

3. When a hardware security module is used, the 'padding' and 'unpadding'
   parts of OAEP should normally be implemented together with the RSA
   operation inside the module, but they *can* also be implemented outside
   the module. The latter would be implementable given existing hardware
   that doesn't directly support OAEP, but it might well be less secure in
   some situations, or require stronger assumptions than the standard RSA
   problem. So, should it be prohibited? (The answer requires a careful
   analysis of the whole protocol, which hasn't been done for TLS.)

4. The description of how to do OAEP 'unpadding' in PKCS #1 v2.0 and IEEE
   Std 1363-2000 does not give the best order of operations to avoid side
   channel attacks, so do you reference a standard that you know is not
   optimal?

   This is not academic; unless RSA-OAEP is very carefully implemented, in
   some entirely plausible situations a timing attack (or certain other
   kinds of side channel attack) against it can require fewer messages than
   a corresponding attack on PKCS #1 v1.5 [Man01].

   A description of how to implement the OAEP unpadding function that
   should be used instead of the one given by PKCS #1 v2 and 1363-2000, to
   minimise the possibility of this kind of attack, is given at the end of
   this post. (I've checked the details of this with James Manger.)

[...]
>     consistent ciphersuites as well.

Consistency certainly has some benefits. However, it's never one of the
primary goals of a security protocol: those are that the protocol is secure,
and that it works (in a broad sense, including being efficient and practical).
Consistency may help those goals indirectly by making it easier or cheaper
to implement some collection of protocols that use similar algorithms, but
if pursued for its own sake, it may also hinder them.

It is naïve to imagine that OAEP can act as a quick fix for any security
problem in a protocol using RSA, which is how some people seem to want to
apply it. If the effects are not analysed on a protocol-by-protocol basis,
serious errors *will* be made, and fixing them (if they are detected, and
if they get fixed) will add still more complexity.

[Sho01]  Victor Shoup,
         "A Proposal for an ISO Standard for Public Key Encryption
          (version 1.1),"
         Revised May 29, 2001.
         http://www.shoup.net/papers/

[Man01]  James Manger,
         "A Chosen Ciphertext Attack On RSA Optimal Asymmetric Encryption
          Padding (OAEP) as Standardized In PKCS #1,"
         To appear in Advances in Cryptology - Proceedings of CRYPTO 2001.

- -- 
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

- -----
OAEP unpadding, with compatible modifications to prevent side channel
attacks:

 1. If the length of P is greater than the length limitation, output
    "error" and stop. Otherwise, apply the hash function Hash to the
    parameters P to produce an octet string cHash of length hLen.
 2. Let oLen = floor(l/8) and seedLen = hLen. If oLen < seedLen + hLen + 1,
    output "error" and stop.
 3. Convert f to an octet string EM of length oLen + 1 with the primitive
    I2OSP. If the primitive outputs "error", output "error" and stop.
 4. Let X be the leftmost octet of EM, let maskedSeed be the next seedLen
    octets, and maskedDB the remaining octets.
 5. Apply the mask generation function G to the string maskedDB to
    produce an octet string seedMask of length seedLen octets.
 6. Let seed = maskedSeed xor seedMask.
 7. Apply the mask generation function G to the string seed to produce
    an octet string dbMask of length oLen - seedLen octets.
 8. Let DB = maskedDB xor dbMask.
 9. Let M' be all but the first hLen octets of DB.
10. Let T be the leftmost nonzero octet of M'.
11. If the first hLen octets of DB are not equal to cHash, or X != 00,
    or T != 01, then output "error" and stop.
12. Remove T and all octets to the left of it (which are all zero) from
    M' to produce an octet string M.
13. Output the message M.

NOTES
1--It is important that the implementation output the same error message
at the same time regardless of the cause of error in step 11.
2--The description of the decoding operation has been modified from that
in IEEE Std 1363-2000, to make it clearer how to implement decoding in
a way that avoids the attack described in [Man01]. This does not affect
compatibility; the differences only affect when errors are detected. In
particular, the previous description used the I2OSP primitive to
produce an octet string of length oLen, rather than oLen + 1. If an
implementation reveals whether the length of the message representative
is greater than oLen octets, then an opponent will be able to determine
whether the most significant octet of an RSA decryption is nonzero, which
may lead to an attack.
3--The error in step 3 cannot occur for RSA-OAEP, since in that case the
message representative will always be in the range [0, 2^(l+1)-1].
4--Step 1 may be precomputed, if P is known in advance.

---

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 20 Jul 2001 13:10:07 +0200

[...]
>    designed into SSL 2.0 from the start.)

Good point, and actually this *does* apply to TLS in some sense.

Assume that a TLS server implements a RSA-OAEP ciphersuite and that
TLS with RSA-OAEP were more secure than TLS with RSA-PKCS #1 v1.5
encryption (e.g. because the Bleichenbacher attack countermeasure is
not implemented correctly).  Then, unless the server uses independent
RSA keys for RSA-OAEP and RSA-PKCS #1 v1.5 encryption, RSA-OAEP
provides no security advantage whatsoever -- the attacker can simply
use PKCS #1 v1.5 ciphersuites for his attacks.  (Note that
Bleichenbacher's attack is not limited to PKCS #1 v1.5 *target*
ciphertexts, it just uses a PKCS #1 v1.5 oracle for *chosen*
ciphertexts).

Thus, adding RSA-OAEP ciphersuites is a nuisance not just to
implementors, but also to server operators, who will need an
additional key and certificate if adding OAEP is to make at least some
sense.

(In fact with the current set of ciphersuites, different keys should
already be used for RSA encryption and RSA signing -- I'm not sure if
anyone really does that.)

Why worry about RSA encryption that much, anyway?  The forward secure
ciphersuites, except export-crippled ones, use RSA only for
signatures.  As far as security is concerned, OAEP is advantegeous for
TLS only for servers that do not have an unpredictable PRNG.

-- 
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

---