Subject: [ietf-tls] Forward secrecy and performance (was AES ciphersuites)

From: David Hopwood <[email-masked]>
Date: Sun, 08 Oct 2000 05:09:19 +0100

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

Peter W wrote:
> On Wed, Oct 04, 2000 at 09:43:35PM -0700, Eric Rescorla wrote:
> > David Hopwood <[email-masked]> writes:
> > > Eric Rescorla wrote:
> > > > [email-masked] (Nelson Bolyard) writes:
> > > > > Advantages of my proposal include:
> > > > > a) giving both the client and server control (via negotiation) on
> > > > > the use (or not) of ephemera.  Clients can effectively require it
> > > > > if they choose.
> > >
> > > > No they can't.
> > >
> > > Yes they can, if the standard mandates that ephemeral keys with a
> > > specific maximum lifetime be used with that ciphersuite. (Obviously we
> > > can only talk about what is guaranteed for conforming implementations.)
> 
> And the whole point of ephemera was forward secrecy.

and later,
> ... the only issue is whether the group feels forward secrecy is important
> enough to change the protocol significantly.
> 
> If not, then there's no practical way of guaranteeing forward secrecy with
> RSA premaster secret exchange.

Ephemeral RSA with a maximum temporary key lifetime would work perfectly
well to guarantee forward secrecy, assuming it is negotiated, with minimal
change to the protocol. However, to see whether there is any point in
making that change, we first need to consider the performance of all the
existing key exchange algorithms, and a few variations on them.

Assume the following optimisations:
 - For DHE, the server chooses a subgroup of GF(p) of order q ~ 161 bits,
   where q and (p-1)/2q are both prime. The server uses short exponents
   between 0 and q-1.
 - For new DHE ciphersuites q is included in the server DH parameters.
   In that case the client can also use short exponents.
 - DSS signing and verification are optimised using well-known
   techniques (fixed base exponentiation with precomputation for signing,
   and simultaneous exponentiation for verification).
 - Server exponentials can be reused over several connections. The client
   always generates a new exponential for each connection.
 - RSA uses the Chinese Remainder Theorem for private key operations.
   The RSA public exponent is 3, and the modulus is the product of two
   512-bit primes.

Reusing DHE server exponentials (i.e. dh_Ys values) is safe provided that:
 - g generates a subgroup of prime order q, and (p-1)/2q has no small
   factors.
 - client certificate types that use static DH parameters (i.e.
   rsa_fixed_dh and dss_fixed_dh) are not included in
   CertificateRequest.certificate_types.

The first condition prevents an attacker from gaining information about
the private value of a reused exponential using small-subgroup attacks.
(Actually the attacker can still find the low-order bit of the private
value; that's compensated for by making q one bit longer than would
otherwise be necessary.)

The reason for disallowing client certificates with static DH parameters
when reusing exponentials, is that otherwise it would be possible to
negotiate the same pre-master secret more than once. (Forward secrecy is
not achieved anyway when using static DH client certificates. IMHO they
should be deprecated.)

A short maximum lifetime should be set for the server exponentials, in
order to avoid weakening the forward secrecy property. This maximum
lifetime should be in the spec (30 seconds should be more than sufficient
to get the performance advantages), rather than being left to the
discretion of server implementors.

Note that being able to solve the discrete log problem in a ~ 160-bit
prime order subgroup of GF(p) with p ~ 1024 bits would imply being able
to break DSA signature keys, so by making DHE_DHE_DSS_WITH_3DES_EDE_CBC_SHA
a mandatory ciphersuite, we are already assuming that this problem is
infeasible.

OK, now for the performance analysis.

For the server, computations that can be amortized over many connections
(e.g. exponential generation in ephemeral DH, and RSA key pair generation
in ephemeral RSA) are not included in the times below. The fact that some
operations can be done in advance to reduce latency is not taken into
account; only the total computational load per connection (this may
penalise DHE in situations where traffic is bursty; it has no effect on
RSA). On the client side, all public key computations are included.
Differences in the amount of data hashed or sent in the handshake would
not have a significant effect on performance.

All times are in milliseconds on a 233 Mhz Pentium II running NT 4.0,
measuring elapsed time with no other non-system processes running. Two
libraries were used: the default Windows build of Miracl (which has a
well-optimised x86 assembler bignum implementation), and OpenSSL.

On the assumption that TLS implementations will be heavily optimised, for
each operation I've taken the time from whichever of Miracl and OpenSSL
is fastest. I also tried Crypto++; it was consistently slower, but the
relative speeds of operations were in about the same ratio.

                                                      times (ms)
                                               Miracl  OpenSSL  fastest
RSAd   RSA private key operation (CRT)          46.21    44.6     44.6
RSAe   RSA public key operation (e = 3)          0.29     2.5      0.29
DHk    DH key agreement (short exponent)        25.70             25.70
DHlk   DH key agreement (long exponent)        151.73            151.73
DSAs   DSA signing                               9.22    23.4      9.22
DSAv   DSA verification                         31.10    29.0     29.0
ECDHk  ECDH key agreement
ECDSAs ECDSA signing
ECDSAv ECDSA verification

OpenSSL implements DH, but I'd have to write a benchmark program; there
isn't one provided. It looks from the RSAd and DSAv times as though its
performance for DH would be similar to Miracl.

Miracl also has an implementation of elliptic curves over GF(p) and
GF(2^m), but there's no point in giving times because the code isn't
optimised. An optimised implementation would be significantly faster
than ordinary DH.

Algorithm     FS?   Server ops    cost   Client ops              base  extra
                                                                _cost  _cost
ECDHE_ECDSA*  yes   ECDHa+ECDSAs     ?   2*ECDHk+(xc+2)*ECDSAv      ?      ?
DHE_DSS*      yes   DHk+DSAs      34.9   2*DHk+(xc+2)*DSAv      109.4   29.0
DHE_DSS       yes   DHk+DSAs      34.9   2*DHlk+(xc+2)*DSAv     361.5   29.0
RSA           no    RSAd          44.6   (xc+2)*RSAe              0.6    0.3
RSAE_DSS      yes   RSAd+DSAs     53.8   RSAe+(xc+2)*DSAv        58.3   29.0
DHE_RSA*      yes   DHk+RSAd      70.3   2*DHk+(xc+2)*RSAe       52.0    0.3
DHE_RSA       yes   DHk+RSAd      70.3   2*DHlk+(xc+2)*RSAe     304.0    0.3
RSAE_RSA      yes   2*RSAd        89.2   (xc+3)*RSAe              0.9    0.3

FS?     supports forward secrecy?
*       with group order in DH or ECDH server params (only possible for
        new ciphersuites)
RSAE_X  ephemeral RSA with signatures and certs using X.
xc      the number of "extra" certificates in the certificate chain
        that need to be verified (the baseline assumes only the cert that
        directly certifies the server key needs to be verified, because
        the others will already be in the client's database). I.e. the
        total client load is base_cost + xc*extra_cost, but xc will
        normally be zero.

In summary, DHE_DSS is slightly faster than static RSA for the server,
and much faster than ephemeral RSA, when all applicable optimisations
are taken into account.

On the client side, DHE_DSS* takes about a tenth of a second on a
233 Mhz PII, so there is no client performance problem for things like
web browsing. For protocols where the client and server are peers,
DHE_RSA* seems a reasonable choice. For computationally challenged
clients, RSAE_RSA or ECDHE_ECDSA might be worth considering in future.

Conclusions:
 - There is no need to give up forward secrecy in order to have good
   performance. Therefore, newly defined ciphersuites should use
   key exchange algorithms that guarantee forward secrecy.

 - Assuming, then, that we don't add new static RSA ciphersuites,
   there is little point in adding RSAE_RSA either. It would be better
   just to use DHE_DSS or DHE_RSA instead, which are more efficient
   for the server.

- -- 
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: Eric Rescorla <[email-masked]>
Date: 08 Oct 2000 08:40:50 -0700

I'm not sure that your data leads to these conclusions.
>  There is no need to give up forward secrecy in order to have good

To a first order DSS certificates do not exist. Essentially
all existing servers have RSA certificates, so that's what
we've got to work with. Therefore all ephemeral schemes
will cost more than what people are currently doing.

How much? The choices we're faced with are DHE_RSA and RSAE_RSA,
right?  DHE_RSA imposes roughly a 50% additional performance load on
the server and RSAE_RSA of course imposes a 100% additional
performance load on the server.  This is not insignificant.

Remember that we're trying to replace existing infrastructure
here. Servers usually use RC4 because they're afraid of the
performance consequences of 3DES. There will already be resistance
to using Rijndael because it's slower than RC4. Confronting
server admins with a simultaneous slowdown in their public key
operations seems to me to be a good way to inhibit uptake.

>    just to use DHE_DSS or DHE_RSA instead, which are more efficient

Your argument seems to hinge on the client DH performance being
"fast enough" The rationale for using ephemeral RSA for PFS is to
reduce the load on really slow clients. Even the full 400 ms required
to do all long DH the client operations isn't really that noticeable
given typical Internet RTTs. [0]

However, this ignores a really slow client machine such as a Palm Pilot.
It's widely maintained that 1024-bit RSA operations on the Palm are
too slow to be useful (30s is often bandied about).

Now, if we assume that Palm performance is roughly proportional
to your test machine across the board, we can see that all four
DHE variants clock in at 45 s or above, which would be similarly 
unacceptable. By contrast, RSAE_RSAE performance would be clearly
acceptable.

Thus, we're basically forced to define some RSA variant for
any new cipher anyway. In my mind the question becomes why define
a DH variant? 

-Ekr

---

---

From: Pete Chown <[email-masked]>
Date: Tue, 10 Oct 2000 19:59:45 +0100

David, thank you for analysing the computational costs of the
different options.  That was what I wanted to do, and I don't know
when I would have got the time!

It sounds as though the consensus is for supporting at least one RSA
ciphersuite.  However, we don't want to lose forward secrecy if
possible.  It seems that if we implement it along the lines of the old
"export" ciphers we can achieve this.

Unfortunately, this means that we must go against the statement in
section 7.4.3 of RFC2246:

> It is not legal to send the server key exchange message for the
> following key exchange methods:
>
> ...
>
> RSA

I suggest, therefore, that this statement should be reversed for the
AES cipher suite.

Also, one thing I don't like about ephemeral RSA is that it is
tempting for servers to keep keys around for too long.  There is
effectively no overhead in generating a new DH key, so there is no
reason not to create a new one each time.  With RSA this is not the
case; there is a temptation just to keep using the same key, or to use
it for an unreasonably long time.  For this reason, I am proposing
including "key hygiene" requirements, even though historically these
have been left out of TLS RFCs.

Here is some suggested wording:

| When TLS_RSA_WITH_AES_128_SHA has been negotiated, servers MUST send
| a server key exchange message.  This is a specific exception to
| section 7.4.3 of RFC2246.  For the avoidance of doubt, section 7.4.3
| of RFC2246 MUST still be followed when no such exception has been
| created.
|
| The ephemeral RSA key supplied by the server in the server key
| exchange message MUST be regenerated with a frequency appropriate to
| the overall threat model, and SHOULD be regenerated at least every
| four hours.
|
| Servers MUST ensure that expired ephemeral RSA keys are destroyed
| securely, having regard to the overall threat model.

I would be very interested in feedback.  If you were one of the people
who asked for an RSA ciphersuite, does this proposal satisfy your
concerns?

My feeling is that the RSA ciphersuite issue is the last major problem
with the draft.  Hopefully I can produce one new draft and then we can
take it to last call -- or is this over optimistic?  :-)

At any rate, if you have any other issues with the current draft,
please could you let me know so I can address them at the same time as
the RSA ciphersuite problem.

-- 
Pete

---

---

From: Eric Rescorla <[email-masked]>
Date: 10 Oct 2000 12:12:53 -0700

> | of RFC2246 MUST still be followed when no such exception has been
No, I'm not comfortable with mandating ephemeral RSA. This doubles
the computational load on the server and there are circumstances where
the threat model simply doesn't warrant it.

> | the overall threat model, and SHOULD be regenerated at least every
It's senseless to have a MUST that actually doesn't require anything. 
I'd put this in "Security Considerations".

	Because forward secrecy depends on secrecy of the ephemeral keys,
	the ephemeral RSA key SHOULD be regenerated frequently. Although
	this specification does not require a specific lifetime, it is
	recommended that regeneration happen no less frequently than once
	an hour.

Given that 1024-bit RSA key generation takes less than 10s, I'm not
particularly bothered by once an hour.

-Ekr

---

---

From: Jeremey Barrett <[email-masked]>
Date: Tue, 10 Oct 2000 14:54:51 -0500

> who asked for an RSA ciphersuite, does this proposal satisfy your

Not really. I don't want to see ephemeral RSA mandated. My interest in
an RSA ciphersuite is for interoperability: there ought to be at least
_one_ ciphersuite which is mandated by the TLS spec and which can be
reasonably implemented in all environments. IMO, that ciphersuite
should be TLS_RSA_WITH_AES_128_SHA, with no mandate for ephemeral
RSA.

Regards,
Jeremey.
-- 
Jeremey Barrett [[email-masked], [email-masked]]
GnuPG fingerprint: 7BB2 E1F1 5559 3718 CE25 565A 8455 D60B 8FE8 B38F

---

---

From: "John Banes" <[email-masked]>
Date: Tue, 10 Oct 2000 13:54:53 -0700

According to the people running secure webservers that I've talked to,
TLS is already way too slow. I don't think that substantially slowing it
down even further is going to be acceptable.

In my opinion, the TLS_RSA_WITH_AES_128_SHA cipher suite needs to
operate without ephemeral keys of any kind. A completely separate cipher
suite should be defined that supports forward secrecy.

Regards,

John Banes
Microsoft Corp.

-----Original Message-----
From: Eric Rescorla [mailto:[email-masked]]
Sent: Tuesday, October 10, 2000 12:13 PM
To: IETF Transport Layer Security WG
Subject: [ietf-tls] Re: Forward secrecy and performance (was AES
ciphersuites)

	Because forward secrecy depends on secrecy of the ephemeral
keys,
	the ephemeral RSA key SHOULD be regenerated frequently. Although
	this specification does not require a specific lifetime, it is
	recommended that regeneration happen no less frequently than
once
	an hour.

-Ekr

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

---

---

From: [email-masked] (Nelson Bolyard)
Date: Tue, 10 Oct 2000 15:14:03 -0700

> John Banes wrote:
> 
> According to the people running secure webservers that I've talked to, TLS is
> already way too slow. I don't think that substantially slowing it down even
> further is going to be acceptable.
> 
> In my opinion, the TLS_RSA_WITH_AES_128_SHA cipher suite needs to operate
> without ephemeral keys of any kind. A completely separate cipher suite should
> be defined that supports forward secrecy.
> 
> Regards,
> 
> John Banes
> Microsoft Corp.

I concur, completely.

--
Nelson Bolyard               Sun / Netscape Alliance

---

---

From: Peter W <[email-masked]>
Date: Tue, 10 Oct 2000 19:15:03 -0400

So folks from the two largest vendors of SSL/TLS applications don't like 
ephemeral suites, even if the language is that keys SHOULD be replaced only
once an hour? That's too demanding? 

What I'm hearing, and maybe I'm too cynical, is MSFT and iPlanet suggesting
that they're more concerned about server performance than security.

What completely separate cipher suite do you propose? Are your companies
prepared to support new FS suites in both server and client applications?
Or the existing DH schemes that provide forward secrecy? How do we actually 
provide FS, short of telling everyone to use Mozilla[0] and Apache/mod_ssl/OpenSSL?

I'm afraid I'm not being very politic here, but ISTM that for the most 
important/vulnerable applications of TLS (i.e., https), MSFT and iPlanet/AOL
are *the* key players.[1] You want your server customers to have fast sites.
We want better security. At this point, even though my Apache install supports
DH ciphers (thanks to Stephen, Ralf, et. al.), I can't achieve PFS because
Navigator and IE don't support those ciphers. Outlining a new scheme does 
little good if its optional and MSFT/iPlanet/AOL choose to ignore it.

How do we, in the real world, make forward secrecy possible?

-Peter

[0] which might need to use OpenSSL instead of the iPlanet code to 
    provide forward secrecy

[1] In controlled environments, I imagine most folks who care are using things
    like the OpenSSL toolkit to build more secure systems, but most users are
    constrained to whatever MSFT/iPlanet/AOL offer them.

-- 
This fall, taxpaying American citizens will elect voting representatives to
the US Congress. Except for those in Washington, DC. http://www.dcvote.org/

---

---

From: [email-masked] (Nelson Bolyard)
Date: Tue, 10 Oct 2000 16:22:00 -0700

> How do we, in the real world, make forward secrecy possible?

IMO, John Banes already answered that question.

> > > A completely separate cipher suite should

By defining the cipher suites separately, the server administrator is given
the choice of whether or not he wishes to pay the price for the PFS, and
likewise, the client has the option of requiring, allowing, or disallowing  
the use of PFS.

---

---

From: Dr S N Henson <[email-masked]>
Date: Wed, 11 Oct 2000 01:27:28 +0100

> likewise, the client has the option of requiring, allowing, or disallowing

This assumes that the clients will actually support PFS and non PFS
suites. We could end up in the situation where only the non PFS
ciphersuite is implemented and we are back to the current situation
where there are no "browser TLS/SSL" ciphersuites supporting PFS.

Steve.
-- 
Dr Stephen N. Henson.   http://www.drh-consultancy.demon.co.uk/
Personal Email: [email-masked] 
Senior crypto engineer, Celo Communications: http://www.celocom.com/
Core developer of the   OpenSSL project: http://www.openssl.org/
Business Email: [email-masked] PGP key: via homepage.

---

---

From: David Hopwood <[email-masked]>
Date: Wed, 11 Oct 2000 03:46:39 +0100

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

Nelson Bolyard wrote:
> By defining the cipher suites separately, the server administrator is
> given the choice of whether or not he wishes to pay the price for the
> PFS, and likewise, the client has the option of requiring, allowing, or
> disallowing the use of PFS.

No, that's not sufficient. Suppose we assume that servers might have
either RSA or DSS certificates, and there's no simple way to require
them to switch.

In that case, for clients to be able to require PFS, all new servers
MUST be able to negotiate at least one PFS-only ciphersuite; i.e.
either one with RSA certification, or one with DSS certification [*].
The one with DSS certification should be TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA,
in order to interoperate with existing TLS clients and servers that wanted
to support PFS.

For servers to be able to require PFS, all new clients MUST be able to
negotiate *both* the RSA PFS-only ciphersuite, and
TLS_DHE_DSS_WITH_3DES_EDE_CBC_SHA [**].

Note that "MUST be able to negotiate" is stronger than saying that a
ciphersuite with PFS simply has to be implemented; the TLS 1.0 spec did
that, and it's had basically no effect.

If both clients and servers can require PFS, then it is not possible
for either a client or a server to disallow PFS (when talking to a peer
that implements the new spec), but that is exactly as it should be.

Clearly, it is not possible to say that all TLS 1.0 implementations
have to satisfy these requirements, because that would declare existing
implementations non-conformant. However, what we could do is effectively
define a "TLS 1.0 and a half", i.e. a specification such that if a
TLS implementation conforms to it, it will have done all it can to
facilitate the use of strong ciphersuites that provide forward secrecy.
Note that since any "TLS 1.0 and a half" implementations will have been
changed since the relaxation of the U.S. export restrictions, it is also
possible to define the spec so that if two such implementations
communicate, they are guaranteed to negotiate a non-export ciphersuite
[***].

An alternative would be to put this in the next version of TLS, but if
that's going to take a long time, I don't think there's any need to wait
for it. Two recent events have made it possible to significantly improve
the security and interoperability of TLS: the relaxation of the U.S.
export regs, and the expiry of the RSA patent. We should take advantage
of those events without further delay.

[*]   Technically, certificates can be marked as for RSA encryption
      only (i.e. they have a keyUsage extension with keyEncipherment
      but not digitalSignature set), in which case it's not possible to
      use either ephemeral RSA or ephemeral DH with them, and still
      conform to RFC 2246. However, I believe I'm correct in saying that
      in order to support export algorithms, almost all RSA certificates
      in practice support signing.

[**]  I argued in a previous post that having the client include more than
      key exchange algorithm in the client hello allows an adversary to
      attack the weakest of them. That argument is correct, but if it's not
      feasible to make servers switch to DSS certificates, we'll just have
      to put up with this, because PFS is more important.

[***] ... except that the attack described in
      http://www.imc.org/ietf-tls/mail-archive/msg01671.html and
      http://www.imc.org/ietf-tls/mail-archive/msg01677.html may still be
      possible. I'll have to think about whether it is possible to fix
      that at the same time. There may be an argument for bumping the
      TLS version number (without making any other significant changes)
      in order to fix it.

- -- 

---

---

From: Eric Rescorla <[email-masked]>
Date: 11 Oct 2000 07:35:55 -0700

> that, and it's had basically no effect.
Are you suggesting that all compliant clients must offer at all
times one of the PFS cipher suites? Regardless of user configuration?

-Ekr

---

---

From: Pete Chown <[email-masked]>
Date: Wed, 11 Oct 2000 22:36:55 +0100

> down even further is going to be acceptable.

I have been doing a bit of thinking about this...  I think that by
doing the forward secrecy ciphersuites right, we can actually speed
things up.

First of all, here is the ServerKeyExchange message, taken from
RFC2246, but simplified a bit:

struct {
    select (KeyExchangeAlgorithm) {
        case diffie_hellman:
            opaque dh_p<1..2^16-1>;
            opaque dh_g<1..2^16-1>;
            opaque dh_Ys<1..2^16-1>;

            digitally-signed struct {
                opaque sha_hash[20];
            };
        case rsa:
            opaque rsa_modulus<1..2^16-1>;
            opaque rsa_exponent<1..2^16-1>;

            digitally-signed struct {
                opaque md5_hash[16];
                opaque sha_hash[20];
            };
    };
} ServerKeyExchange;

Now, in each case, the signature is on the ephemeral key *only*.  If
the ephemeral key is only regenerated every four hours (as in my
original wording) this signature only needs to be calculated once.  So
ephemeral RSA will cost the server about the same as static RSA.

Now suppose we use ephemeral Diffie-Hellman.  The RSA signature on the
DH parameters will be precalculated.  (This assumes a slight change to
my original text which assumed a new DH secret each time.)  Now
because of the short exponent optimisation described by David Hopwood,
the DH agreement is faster than RSA decryption.  Static RSA has to do
one RSA decryption on the server.  EDH as described here only needs to
do one Diffie-Hellman agreement.  This should speed things up quite
significantly.

(I hope I've not missed something silly here!  :-)  )

-- 
Pete

---

---

From: Eric Rescorla <[email-masked]>
Date: 11 Oct 2000 14:47:27 -0700

Pete Chown <[email-masked]> writes:
> Now, in each case, the signature is on the ephemeral key *only*.
Huh?

See S 7.4.3 of RFC 2246:

       md5_hash
           MD5(ClientHello.random + ServerHello.random + ServerParams);

       sha_hash
           SHA(ClientHello.random + ServerHello.random + ServerParams);

Even if we changed TLS in the way you propose, it would introduce
active attacks. An attacker who had broken one ephemeral key could
then actively insert it into any connection by replaying the SKE.

> (I hope I've not missed something silly here!  :-)  )
I'm afraid that you have.

-Ekr

---

---

From: Dr S N Henson <[email-masked]>
Date: Thu, 12 Oct 2000 00:18:16 +0100

> > doing the forward secrecy ciphersuites right, we can actually speed
[description deleted]
> then actively insert it into any connection by replaying the SKE.

I've been thinking along similar lines wrt performance and
precomputation. The best I could come up with to avoid a replay attack
was to have some kind of timestamp and key lifetime protected by the
signature. So it would say something like the time the key was generated
and its lifetime. This would then rely on the client checking and
rejecting an expired key.

Steve.

---

---

From: Eric Rescorla <[email-masked]>
Date: 11 Oct 2000 16:47:27 -0700

> rejecting an expired key.
I hate using time in cryptographic protocols. This requires clocks
to be synchronized. As you know, this was a big problem with Kerberos.
Granted, we don't need such tight synchronization here, but I think it's
asking for trouble.

-Ekr

---

---

From: David Hopwood <[email-masked]>
Date: Thu, 12 Oct 2000 01:02:44 +0100

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

Pete Chown wrote:
[snip]
> original wording) this signature only needs to be calculated once.

No, the signature is also on the client and server random values, and
this is essential to prevent replay attacks. The same applies to
ephemeral DH.

> (I hope I've not missed something silly here!  :-)  )

Don't worry, I thought the same thing for a few minutes when I was
doing the performance analysis :-)

- -- 

---

---

From: Dr S N Henson <[email-masked]>
Date: Thu, 12 Oct 2000 13:12:38 +0100

> Granted, we don't need such tight synchronization here, but I think it's

I'm not too keen on using time myself. However if this can be used to
provide PFS with minimal performance penalty, and no one has any better
ideas, then I can live with it.

Steve.

---

---

From: Peter W <[email-masked]>
Date: Thu, 12 Oct 2000 09:00:29 -0400

> No, that's not sufficient.

> that, and it's had basically no effect.

I agree wholeheartedly. :-(

> However, what we could do is effectively

There are a few things I am concerned about re: PFS.
 1) what code is required to be present in a conformant app?
 2) what suites, if any, are required to be enabled "out of the box"?
 3) what suites, if any, may not be disabled by the app user?

An issue we can't even begin to address is software configuration, e.g. in
Navigator I can enable/disable certain SSL3 suites, but I cannot specify
the order of preference. I suspect that Microsoft, iPlanet, and AOL will
take measures to make PFS unlikely to be used. 

I'd love to see PFS at least meet criteria two: required to be enabled
in "out of the box" configurations. Criteria one is only sufficient if 
the app is well designed: can the users find the configuration? Does the
app give good error messages? [0]

As for server performance issues: how bad is it, really? John said that
he had heard second hand that "TLS" was "way too slow". What does that
mean? 25% slower than SSL/RSA? 250% slower? Which TLS suites? What is an 
acceptable penalty for FS? 

I'm encouraged by the recent talk about ways to achieve FS without big 
performance penalties. Goodness knows fast FS is better than slow FS.
Fast FS + good spec requirements sounds like a winning combination.

> of those events without further delay.

Yes, absolutely. The marketing folks love to boast SSL/TLS support as
if it were magic security pixie dust. Let's make sure it does its job well.

-Peter

[0] For instance, if I deliberately disable most ciphers in Navigator 4.75
and visit a site that I had been to before making the client changes, my
browser tells me "Netscape and this server cannot communicate securely 
because they have no common encryption algorithm(s)" -- I have most ciphers
disabled, but the browser doesn't suggest checking my configuration. Now
suppose the problem is that the server only supports PFS suites, and my
TLS 1.5 browser lacks the optional suites and has the others disabled by 
default. This would stop many, maybe most, users in their tracks. Get an
obscure error message trying amazon.com but bn.com works fine? Poor choice
of client defaults + poor error messages = enticement to not use PFS.

---

---

From: Eric Rescorla <[email-masked]>
Date: 12 Oct 2000 08:01:36 -0700

> I agree wholeheartedly. :-(
As far as I can tell, the reason that there has been no real
deployment of the PFS ciphersuite is that it's DSS/DHE, and there's
been no real CA support for DSA.

> acceptable penalty for FS? 
I can't speak for John, but I suspect he means that SSL is also too
slow already. Quite reasonable server machines get brought to their
knees by the introduction of SSL/TLS, even in the relatively fast RSA mode.

-Ekr

---

---

From: Eric Rescorla <[email-masked]>
Date: 12 Oct 2000 08:02:28 -0700

> ideas, then I can live with it.
I don't think I am. This seems to me to introduce a whole new set
of potential security risks. PFS is not the only desirable security
goal here. Protection against active attacks is also important.

-Ekr

---

---

From: Dr S N Henson <[email-masked]>
Date: Thu, 12 Oct 2000 18:58:32 +0100

> acceptable penalty for FS?

Well as has been indicated RSA FS doubles the number of server private
key operations so doubling the handshake time is a rough estimate.

This may not be tolerable in all situations but its similar to the
overhead used by the "magic certificates" which enabled 128 bits
connections in export browsers or those which perform client
authentication by doing two handshakes.

In any case if TLS is "way too slow" already then users may well not use
AES on those grounds and stick with RC4.

Steve.

---

---

From: Dr S N Henson <[email-masked]>
Date: Thu, 12 Oct 2000 19:13:16 +0100

> goal here. Protection against active attacks is also important.

Have you any specific attacks in mind?

We're already using time in TLS anyway with certificate verification,
which could be exploited if the server or client time can be manipulated
by an attacker.

Steve.

---

---

From: Eric Rescorla <[email-masked]>
Date: 12 Oct 2000 11:25:26 -0700

> authentication by doing two handshakes.
Only for Netscape. As you know, Microsoft went to great trouble to
optimize out this second handshake.

> AES on those grounds and stick with RC4.
I think you've hit the nail on the head here. It's already going to
be a stretch to get users to use AES instead of RC4. RSA performance
is much more relevant to SSL performance than symmetric performance,
so it will be an even harder sell to convince them to use AES if
it also doubles handshake cost.

-Ekr

---

---

From: Eric Rescorla <[email-masked]>
Date: 12 Oct 2000 11:28:10 -0700

> Have you any specific attacks in mind?
Only the one I already mentioned where you exploit the compromise 
of the ephemeral key. On the other hand, I haven't had time to analyze
it very carefully. 

> which could be exploited if the server or client time can be manipulated
Sure, but the certificate verification basically operates on a much
longer time scale. Most people can get their clocks right on a 
day/week timescale. Lots of people's clocks are off by a couple
of hours.

I'd also like to point out that a change of this magnitude would
likely result in recycling TLS at Proposed.

-Ekr

---

---

From: [email-masked] (Nelson Bolyard)
Date: Thu, 12 Oct 2000 14:11:44 -0700

> slow already. 

I also interpreted it that way.  The comparison isn't TLS vs SSL, it's
https vs http, I suspect.  

> Quite reasonable server machines get brought to their

Yes.  In my experience, the single largest factor limiting the deployment
of SSL/TLS today is the performance hit of https as opposed to http.

--
Nelson Bolyard               Sun / Netscape Alliance
Disclaimer:                  I speak for myself, not for Netscape

---

---

From: Ben Laurie <[email-masked]>
Date: Sun, 15 Oct 2000 13:44:40 +0100

> of SSL/TLS today is the performance hit of https as opposed to http.

I find these remarks hard to understand - from where I'm sitting,
performance doesn't limit the deployment of TLS - almost every site we
host uses it where needed, without any performance problems at all.

OK, you have to size your kit appropriately, but this isn't exactly
news, and for all except the largest sites, "appropriately" means
perfectly ordinary high end PCs.

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html

Coming to ApacheCon Europe 2000? http://apachecon.com/

---

---

From: Damien Miller <[email-masked]>
Date: Mon, 16 Oct 2000 08:31:12 +1100 (EST)

> host uses it where needed, without any performance problems at all.

It would be nice to use TLS everywhere, not just ``where needed''.

-d

-- 
| ``The power of accurate observation is  | Damien Miller <[email-masked]>
| commonly called cynicism by those who   | @Work <[email-masked]>
| have not got it'' - George Bernard Shaw | http://www.mindrot.org

---

---

From: Peter W <[email-masked]>
Date: Tue, 17 Oct 2000 01:32:12 -0400

> It would be nice to use TLS everywhere, not just ``where needed''.

Not everywhere. TLS does impose extra burdens, from the cost of
encryption to the inherently proxy-unfriendly nature of encrypted
communication. TLS should be used where privacy or authenticity[0] are
issues; otherwise, why bother?

I'm a bit confounded by this, too. Employees of two big SSL/TLS software
vendors have made vague statements about the cost of encryption. They have
not provided more detail to help us understand, for instance, how much
increased cost of encryption the market will tolerate. In fact, we have
messages appearing to suggest that *any* encryption cost is too much.

If that's where we stand, then I think it's even more important that the
official specs *require* reasonable PFS suites. By all means, performance
should be a consideration. But it seems we can't count on software vendors
-- even those writing server apps designed for very capable Pentium-III
and UltraSPARC boxes, likely with hardware accelerators -- to implement
strong suites of their own accord if there's any feeling that the stronger
suites might slow things down.

Back to why/when to use TLS: I haven't run into very many folks using TLS
simply for its authentication features, at least for HTTP. If this were
the case, then I would --in other channels-- press an idea I've had for a
while, about embedding crypto signatures inside HTML/XML documents to
provide authentication over speedy unencrypted channels.[0] Most TLS
implementations, especially what MSFT/SUN are dealing with, are used
mostly, if not entirely, for data privacy.[1] And there's no getting
around channel encryption for that. So let's do it right.

-Peter

[0] For simple document verification, something like PGP is ideal. No
extra per-transaction overhead, caches well, etc. Web docs could add
markup like this to enable seamless document signing:

<!-- // line added to hide crypto markers
--- BEGIN SIGNED MESSAGE ---
// line added to hide crypto markers -->
<p>HTML data that we signed (along with closest two comment lines).</p>
<!-- // line added to hide crypto markers
--- BEGIN SIGNATURE ---
...sig here...
--- END MESSAGE ---
// line added to hide crypto markers -->

Such that older browsers would render normally, and crypto-aware browsers
could verify the signature of various components on a page. Similarly, an
HTTP header could be used to tell a client where to find a detached
signature for the rare cases where an entire HTML doc is signed.

[1] Most. I said most. Yes, many folks are using client certificates. Yes,
some folks are using TLS as a means of verifying server identity. But most
are not.

---

---

From: Pete Chown <[email-masked]>
Date: Tue, 17 Oct 2000 10:17:38 +0100

I just wanted to reassure everyone that I haven't forgotten about the
draft and the ephemeral ciphersuite issue.  I have been having some
interesting offline discussions about efficiency; hopefully these will
lead to a way forward.

Peter W wrote:

> In fact, we have

If that is the case just make the *decryption* key 3 instead of the
encryption key!  That should speed things up a bit, while still making
the padlock light up...  :-)

> ... an idea I've had for a
> provide authentication over speedy unencrypted channels.

Have you seen XML-DSIG?  I think the W3C draft for this is currently
in last call.  I don't agree with all the design decisions, but it
looks as though it would achieve what you want (with XHTML at least).

-- 
Pete

---

---

From: David Hopwood <[email-masked]>
Date: Wed, 18 Oct 2000 05:45:45 +0100

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

David Hopwood wrote:
> this is essential to prevent replay attacks.

Actually, it's not essential.

The reason why the client and server random values needed to be in the
input to the server's signature for the export ciphersuites, was that
only the signing key could be relied on to be secure. I.e. if an attacker
broke a short ephemeral public key by factoring or computing discrete logs,
and signatures were not tied to a specific session, then the attacker
would have been able to replay a signature in order to impersonate the
server (or do a MITM attack).

This only applies to *breaking* an ephemeral key, though, not compromising
it. If the server is compromised, an attacker will normally get the
private signature key as well (but see the caveat below). In that case,
the attacker will be able to do impersonation or MITM attacks anyway,
and forward secrecy can't prevent this.

When the ephemeral keys are as long as the signature key, we can rely on
them not to be broken, so signing each ephemeral key once is perfectly
sufficient, and it doesn't matter if signatures are replayed. The checks
on the Finished hashes are enough to prevent other attacks.

There is a caveat: consider servers that use protected hardware to
hold the private signature key. For the existing ciphersuites, if an
attacker breaks into such a server by exploiting a software bug, say,
he/she will not be able to get at the private key.

[This assumes that it isn't possible for the attacker to do a chosen
ciphertext attack against the hardware device to recover the key -
which would be possible if the device can perform raw RSA private key
operations, for example, or if it does PKCS #1 v1.5 encryption without
protection against Bleichenbacher's attack *in the hardware itself*.]

If the client and server random values are not included in the server's
signature, then depending on the interface to the hardware device, the
attacker might be able to submit his own public key to it, and get back
a signed key that will be sufficient to impersonate the server. New
hardware or upgraded firmware could easily fix this by generating the
ephemeral keys and signing them internally. However, there might still
be an attack against existing hardware that is not possible with the
current ciphersuites. If so, it could be fixed by changing the padding
method used for signatures, in such a way that a new-style signature
cannot be generated by an "old" device without firmware changes (for
example the padding could be changed to PSS). If the hardware just does
raw RSA, this will not work, but as discussed above, in that case an
attacker who compromises the server will be able to get the private key
anyway.

(Some of the above is speculation, because I'm not entirely sure what
the interfaces to nCipher's stuff and the other SSL/TLS hardware
accelerators look like - perhaps someone from those companies could give
more details?)

If the random values are not included in the server signature, all of
the ephemeral keys need to be at least as secure as the original server
key. Secure random number generation might be an issue here, but in
practice, I think the time between generating ephemeral key pairs (an
hour?) is easily long enough to be able to collect enough entropy for a
secure key.

Version rollback also needs to be analysed taking into account this
change, but that's complicated issue (not least because of the bugs in
various implementations) that I'll leave for another post.

Here are the performance figures for all ciphersuites, with the random
values not signed. "URSA" means Unbalanced RSA (a.k.a. Shamir's
"RSA for Paranoids"), which I'll also describe in a separate post.

Algorithm    FS?   Server ops   cost    Client ops              base  extra
                                                               _cost  _cost
URSA         no    URSAd        13.1    URSAe+(xc+1)*RSAe        1.0    0.3
URSAE_RSA    yes   URSAd        13.1    URSAe+(xc+2)*RSAe        1.3    0.3
URSAE_DSS    yes   URSAd        13.1    URSAe+(xc+2)*DSAv       58.7   29.0
DHE_RSA      yes   DHk          25.7    2*DHk+(xc+2)*RSAe       52.0    0.3
DHE_DSS      yes   DHk          25.7    2*DHk+(xc+2)*DSAv      109.4   29.0
RSA          no    RSAd         44.6    (xc+2)*RSAe              0.6    0.3
RSAE_RSA     yes   RSAd         44.6    (xc+3)*RSAe              0.9    0.3
RSAE_DSS     yes   RSAd         44.6    RSAe+(xc+2)*DSAv        58.3   29.0

I.e. the [U]RSAE_RSA ciphersuites with forward secrecy have the same
server-side performance as [U]RSA without forward secrecy (neglecting
the cost of generating and signing ephemeral keys, because that is only
done once per hour or whatever), and they only require one extra RSA
verification by the client. Obviously this greatly strengthens the case
for only defining new ciphersuites with forward secrecy. It also means
that there is a good argument for trying to make sure that when a new
client and a new server communicate, they will *always* negotiate a
ciphersuite with forward secrecy.

- -- 

---

---

From: Holger Reif <[email-masked]>
Date: Wed, 18 Oct 2000 12:51:15 +0200

> // line added to hide crypto markers -->

This has been suggested already and is (still?) known as S-HTTP. You
can probably find references at www.terisa.com.

Please note however that S-HTTP never took of, due to lack of browser
support. Furthermore, this is *transport layer security* WG and not 
about application layer.
 
> signature for the rare cases where an entire HTML doc is signed.

At least this would provide perfect backward compatibility.
BTW I remember a similiar, working solution for PGP signed HTML pages,
sorry that I can't provide you with the reference.

Rgeards
-- 
Holger Reif                  Tel.: +49 361 74707-0
SmartRing GmbH               Fax.: +49 361 7470720
Europaplatz 5               [email-masked]
D-99091 Erfurt                  WWW.Smarttrust.com

---

---

From: Eric Rescorla <[email-masked]>
Date: 18 Oct 2000 07:36:07 -0700

> can probably find references at www.terisa.com.
Actually, S-HTTP is much more along the lines of an S/MIME wrapper.
(see RFC 2660/2661). It is not transparently compatible and was never
intended to be.

> support
Quite so.

-Ekr

---

---

From: Eric Rescorla <[email-masked]>
Date: 18 Oct 2000 07:51:35 -0700

> Actually, it's not essential.
It is if you wish to prevent replay of signed ephemeral keys.
Your argument below is simply that that's not important. I believe this
is wrong.

1. Consider the case where the keys aren't the same length. (The
generalized version of the export case). This becomes very desirable
if the length of the signing key isn't a performance problem. In this
situation, the ephemeral key might be within the realm of breakability
while the signing key is not.

2. Consider the case where the cipher suites aren't the same and the
attacker has a computationally expensive attack on the ephemeral key.

In either of these two cases, it's quite believable that the ephemeral
keys are weaker than the signing key and that the server would wish
to enforce a changeover.

On a more philosophical level, what you propose has the critical flaw
that it fails to enforce the server's control over the ephemeral key. 
This is a form of defense in depth that I'd rather like to retain.

-Ekr

---

---

From: Dr S N Henson <[email-masked]>
Date: Wed, 18 Oct 2000 19:02:55 +0100

> protection against Bleichenbacher's attack *in the hardware itself*.]

My understanding of the Bleichenbacher's attack is that one cannot
recover the private key but rather can persuade a vulnerable server to
ultimately (after a few million operations) reveal a premaster secret.

Steve.

---

---

From: David Hopwood <[email-masked]>
Date: Thu, 19 Oct 2000 00:38:42 +0100

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

> ultimately (after a few million operations) reveal a premaster secret.

I stand corrected.

However, note that if the attacker has enough time to be able to decrypt
all primes less than B, before his access to the server is terminated,
he will still be able to decrypt ciphertexts that are B-smooth (i.e. can
be expressed as a product of those primes).

Anyway, we need to know what how hardware interfaces are typically defined,
before concluding what the effect would be on their security.

- -- 

---

---

From: David Hopwood <[email-masked]>
Date: Thu, 19 Oct 2000 00:27:08 +0100

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

[Note: below RSAE_RSA refers to the version of ephemeral RSA where the
random values are included in the signature, and RSAE_RSA* refers to
the version where they are not.]

Eric Rescorla wrote:
> 1. Consider the case where the keys aren't the same length.

In that case the security would be limited to that of the shorter key.
So don't do that.

> (The generalized version of the export case). This becomes very
> desirable if the length of the signing key isn't a performance problem.
> In this situation, the ephemeral key might be within the realm of
> breakability while the signing key is not.

There are two key exchange methods that it's meaningful to compare the
RSAE_RSA* method with:

 - If you compare it to RSAE_RSA with an ephemeral encryption key
   length of k1, and a signature key length of k2 > k1, then the
   server load for that will be RSAd_k1 + RSAs_k2 per connection.
   Choose the corresponding RSAE_RSA* key size to be k2 for both the
   ephemeral and signing keys; then the server load will be RSAd_k2
   (equal to RSAs_k2) per connection, i.e. more efficient *and* more
   secure.

 - If you compare it to static RSA with an encryption key length
   of k, then the server load will be RSAd_k per connection.

   Choose the RSAE_RSA* key size to be k for both the ephemeral
   and signing keys; then it will be equally efficient on the server
   side, will require one extra RSA verification on the client side,
   and will be more secure because it provides forward secrecy.

It does not make sense to compare RSAE_RSA* with a hypothetical key
exchange method where signatures cannot be replayed, but that does
not incur the cost of a signature per connection, because no such
method has been proposed.

[Actually Pete Chown and I also discussed an alternative based
on one-time signatures as well as RSA, but I think we rejected that,
on complexity grounds and because it might be subject to a patent
that doesn't expire until 2008.]

Just to make this clearer: in the proposed RSAE_RSA* scheme the
signature key and the ephemeral keys are all the same length, and
that length is chosen according to the same criteria that would be
used to choose a signature key length in RSAE_RSA.

> attacker has a computationally expensive attack on the ephemeral key.

I assume you're referring to the case where the encryption and
signature algorithms are different.

The RSAE_DSS suites aren't very interesting; I only included them in
the performance analysis for completeness. If we use RSAE_RSA*, the
signatures and the encryption will have effectively the same security,
because they use the same trapdoor function with the same key length.
(Technically that depends on using encryption and signature padding
methods that both have security proven to be tightly reducible to the
RSA Problem, under comparable assumptions. OAEP and PSS would be
suitable methods.)

URSAE_RSA is a bit more complicated, but I'll discuss that separately.

> keys are weaker than the signing key and that the server would wish

I think I've addressed both of these objections, but here's another one:

3. A server administrator's opinion of the security provided by a given
   key length could change, in which case he/she might want to increase
   the length of ephemeral keys, without getting a new signature key
   certificate.

This is also invalid for the same reason as 1. If the ephemeral key
length is chosen to the same as the signature key length, then
increasing it will not help. All ciphersuites have a key length that
has to be chosen large enough to resist attacks within the validity
period of the certificate.

> that it fails to enforce the server's control over the ephemeral key.

Once a server has deleted an ephemeral private key, it cannot be
recovered by compromise of the server. Breaking it without compromising
the server is as hard as breaking the signature key would be. There is
no flaw here.

> This is a form of defense in depth that I'd rather like to retain.

I'm all for defense in depth, but I don't think you've presented a valid
argument that RSAE_RSA* is any weaker in that regard.

- -- 

---

---

From: Eric Rescorla <[email-masked]>
Date: 18 Oct 2000 20:17:25 -0700

> the server is as hard as breaking the signature key would be. There is
I should have spoken more clearly. The server's control over the 
client's use of the ephemeral key.

If the ephemeral key is compromised, the server can't stop people
using it in RSAE_RSA*. The system is permanently open to active
attack, even if the static key is secure. This is not the case in
RSAE_RSA. If you can't imagine situations in which the ephemeral key
can be compromised while the static key is not, then I maintain that
you're not very imaginative. 

Consider, for instance, the case where you're dealing with hardware
whose signature interface REQUIRES the data to be passed in on an
I/O channel (this applies to pretty much every piece of cryptographic
hardware that I know of). If you had such a piece of hardware that
also kept the static key securely on the card, then compromising
the server would permit compromise of the ephemeral key, but not of
the static authentication key.

-Ekr

---

---

From: David Hopwood <[email-masked]>
Date: Thu, 19 Oct 2000 04:05:34 +0100

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

Eric Rescorla wrote:

> client's use of the ephemeral key. If the ephemeral key is compromised,
> the server can't stop people using it in RSAE_RSA*. The system is
> permanently open to active attack, even if the static key is secure.

The system depends on the ephemeral keys being as secure as the
static key. I already made that quite clear, and while not trivial,
I believe it can be readily achieved in practice.

> This is not the case in

> hardware that I know of).

It's pretty annoying to be called "not imaginative" enough to think
of a case that I already covered in detail in the same article in
which I suggested the scheme.

If the hardware signs any input with RSA PKCS #1 v1.5 type 0 using
MD5 and SHA-1 (whether the hashes are done inside or outside the
hardware), then as I stated in that article, a possible solution is
to change the encoding scheme, for example to PSS (since a PSS-encoded
signature will not be a valid PKCS #1 v1.5 type 0 signature with the
same key, or vice versa).

I also pointed out that this will not work if the hardware acts as
a raw RSA decryption/signing oracle, and asked for information,
preferably from people who know directly, on whether that is actually
the case for real-world implementations of SSL/TLS accelerators.
(Note that if the hardware does act as a raw RSA oracle, it may be
possible for an attacker who breaks into a server to gain sufficient
information to decrypt a non-negligable proportion of ciphertexts
even after their access to the hardware is cut off.)

Of course, firmware would need to be modified in order to support
the new ciphersuites, but I don't see any way to avoid that when
introducing a new key exchange algorithm.

- -- 

---

---

From: Eric Rescorla <[email-masked]>
Date: 18 Oct 2000 23:15:40 -0700

> I believe it can be readily achieved in practice.
However, this isn't required AT ALL with previous ephemeral schemes.
Those schemes AREN'T brittle against compromise of a single ephemeral
key. I consider this a significant drawback in your scheme.

> which I suggested the scheme.
Sorry about that. I rush-added the example right before sending the
message and heading out to dinner and didn't bother to reedit the
previous text. Moreover, I admit it's not much of an example. My
apologies.

That said, your entire point appears to be to demonstrate that PFS
doesn't create additional CPU cost and thus we should require it in
all cases. However, you're only able to achieve this goal by
sacrificing security. You may not consider that sacrifice to be
substantial, but it's not zero, and I think that reasonable people
can differ on how substantial it is.

To recap:
1. You give up PFS because you can't afford to create a new key every
   time as you would with DH.
2. You create the additional restriction that the ephemeral key must
   be controlled every bit as tightly as the static key because if it's
   ever compromised, the whole game is up. The static key must be revoked
   as well.

Basically, you've created something which is better than static RSA but
worse than true PFS.

Personally, I'd far rather see two cipher suites, one with PFS (presumably
DHE_RSA with a modification to permit the client to use a short exponent)
and one without (static RSA). Then, those who DO care about PFS can have
it, at a performance cost but more securely than RSAE_RSA. Those who
don't could choose not to.

I understand that you'd like to require PFS, but I don't think that's 
reasonable to do in a protocol standard, particulary since you've managed
to do it by sacrificing PFS.
		       
-Ekr

---

---

From: Eric Rescorla <[email-masked]>
Date: 19 Oct 2000 00:35:38 -0700

>    ever compromised, the whole game is up. The static key must be revoked
Note that this second objection doesn't apply as strongly if you have some
sort of expiry time in the signed RSA key, as suggested by Steve Henson.
In that case, the window of compromise only lasts as long as the key
is valid. On the other hand, you introduce a requirement for at aleat
somewhat synchronized clocks into he protocol.

-Ekr

---

---

From: David Hopwood <[email-masked]>
Date: Thu, 19 Oct 2000 22:02:05 +0100

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

> same key, or vice versa).

Correction: there is an attack on this if the hashes are done outside
the hardware (at least for 1024-bit keys) - see [*] below.

> even after their access to the hardware is cut off.)

I should have said here, "to sign a non-negligable proportion of inputs".
Also, this is true even if the oracle only accepts inputs of length
up to 288 bits (i.e. the length of concatenated MD5 and SHA-1 hashes).

Let Psi(x, B) be the number of integers <= x that are B-smooth (i.e.
do not have a prime factor > B).
Then according to [Ste85], Psi(x, B)/x ~= u^-u, where u = log(x)/log(B).

Let H(m) = MD5(m) || SHA-1(m). An output of H can be modelled as a
random integer < 2^288. So if B = 2^25, for example, then the
probability of a hash being B-smooth is roughly 2^-40.6. The attacker
breaks into the server, and finds { C^d mod n : C < B and C is prime }.
Access to the server is then lost. The attacker now waits for a client
to send the client_random, then hashes an expected 2^40.6 values
H(client_random || server_random || rsa_public) (where the private
key to rsa_public is known), to find one where the hash is B-smooth.
If the hash is product[i = 1..k](C_i^t_i), then its PKCS #1 type 0
signature is product[i = 1..k]((C_i^d)^t_i), and the attacker can use
this to impersonate the server using either the RSAE or RSA_EXPORT
ciphersuites. Note that the value of B can be traded against the
number of hash computations needed.

[*] The reason why switching to PSS for RSAE_RSA* only works if
hashing is done internally, is that otherwise we can use the same
technique as above with B = 2^288 to find a B-smooth PSS input of
length just under 1024 bits, and forge a PSS signature given access
to the PKCS #1 type 0 signing oracle.

IOW, roughly speaking, hardware that does hashing internally will
resist a compromised-server impersonation attack, and hardware where
hashing is done externally will not adequately resist it. This
applies whether or not the RSAE_RSA* ciphersuite is added.

[Ste85] N. M. Stephens,
        "Lenstra's Factorisation Method Based on Elliptic Curves,"
        Advances in Cryptology - Proceedings of CRYPTO '85.

- -- 

---

---

From: David Hopwood <[email-masked]>
Date: Wed, 25 Oct 2000 09:19:52 +0100

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

> However, this isn't required AT ALL with previous ephemeral schemes.

No, it isn't, but so what?

The main point of dispute seems to be whether it is realistic to expect
that the ephemeral keys can be kept as secure as the static key.
Consider two types of implementation:

  "Monolithic server" - the server is implemented as a single component
  (usually software), and compromising it can be expected to reveal
  all of its secret data.

  "Split server" - the server is split into inner and outer layers;
  the inner layer (usually hardware) is designed to be more resistant
  to compromise. The outer layer (usually software) never gets direct
  access to the private key.

In the monolithic server case, I think it's definitely realistic to
expect that the ephemeral keys can be kept as secure as the static
key. In the split server case, it is more complicated, but it's also
complicated for the existing ciphersuites, because chosen-signature
attacks against PKCS #1 type 0, attacks against the RNG, etc. need to
be considered.

> key. I consider this a significant drawback in your scheme.

I think this is an exaggeration of the differences between the schemes.
Do you consider the existing ciphersuites "brittle" because they are
vulnerable to compromise of a single key (the long-term signing or
encryption key)?

Let's look at the reasons why a key might be compromised in more detail:

1. Key generation
   a. random number generation
      The RNG needs to have sufficient entropy when the server starts
      to guarantee that all the ephemeral keys generated while that
      process instance is running are unpredictable.

      For a monolithic server:
         The RNG must initially have enough entropy to generate the
         long-term key pair, before the server is started for the
         first time (if it does not then the other ciphersuites will
         also be vulnerable). Assume that a one-way hash of the
         random state is periodically saved, and if the server crashes
         (or is shut down), this saved state is used to provide part
         of the entropy on restarting. The potential problem is that
         the entropy input might cease to be sufficiently random,
         *after* the long-term key has been generated. However, as
         long as the RNG behaves like a cryptographically secure
         pseudo-random number generator in that case [*], and as long
         as the state remains secret, an attacker will still not be
         able to predict any of its output.
         In order to get at the RNG state (either in memory, or the
         saved state), an attacker would have to compromise the
         server. If he does that, then for a monolithic server, he
         would also be able to get the long-term signing key.

         [*] The RNG needs to be secure according to the criteria in
             [KSWH98] or [Gut00]. For example, /dev/random or Yarrow
             would suffice.

      For a split server:
         The RNG state should be held securely by the inner layer of
         the server, and this RNG has to be designed so that it
         cannot be predicted even if the outer layer is controlled
         by an attacker. This is quite difficult, but it's equally as
         difficult and as necessary for the existing ciphersuites
         (predicting a value of k used in DSA signing allows finding
         the private key, for instance).

   b. weak keys
      If a small but non-negligable proportion of RSA key pairs
      generated by a particular method were weak, then the
      probability of this happening for at least one key that
      allows server impersonation, would be greater for RSAE_RSA*.

      However, for randomly generated 512-bit or larger primes, and
      either random large e or constant e, there does not appear
      to be any class of weak RSA moduli that occur with
      non-negligable probability (see [RS98], and note that the
      "Time-to-First-Solution Principle" given in that paper is
      exactly the right model for analysing security when there are
      a large number of target keys).

2. Key use
   a. side channel attacks
      Since the RSAE and DHE ciphersuites have an on-line signature
      operation, a timing or other side channel attack against
      RSAE_RSA* would presumably also be applicable to the long-term
      key in those ciphersuites (RSA decryption and signing are
      effectively the same operation as far as side-channel attacks
      are concerned).
      Countermeasures against timing attacks are well-known (e.g.
      blinding, or making decryption take the same time for all
      inputs).
   b. chosen-ciphertext attacks
      Using OAEP would completely prevent these; the combination of
      replacing invalid PKCS #1 blocks with a random value, and the
      fact that the premaster_secret is only used after being hashed,
      also appears to prevent them.
   c. attacks against the RSA Problem
      These would apply equally to the other RSA ciphersuites. Note
      that the problem parameters (distribution of p, q, and e) are
      the same for the ephemeral keys as they would be for signing
      keys in RSAE_RSA.
   d. hardware or software faults (see [BDL97])
      These would apply equally to other ciphersuites. (The attack
      against CRT-based RSA operations in [BDL97] can be applied
      to RSAE_RSA* and RSAE_RSA, and is easy to protect against in
      both cases.)

3. Key storage and deletion
   Ephemeral keys never need to be stored on stable media (it is
   always acceptable to lose the current key if the server crashes).

   For a monolithic server, the current ephemeral key, the next
   ephemeral key that is being generated, the signing key, and any
   intermediate results for signing or encryption should all be
   stored in locked physical memory, so that they cannot be swapped
   to disk. In that case, deleting them is not difficult.

   For a split server, the inner layer must generate and sign
   ephemeral keys internally, and only give access to an encryption
   oracle for the current ephemeral key. (It's desirable for the
   encryption to be done in hardware anyway for performance reasons.)
   I.e. at any given time it has to store up to three keys securely
   (including the one being generated) instead of one, which I don't
   see as being a big problem. Existing SSL/TLS accelerators would
   require at least firmware changes in order to support the new
   ciphersuites, though.

   Since certificates do not specify which ciphersuites they can
   be used with, we also need to make sure that current implementations
   of the inner layer of a split server do not allow forging a signature
   on an ephemeral key for RSAE_RSA*, if they would not have done
   for the existing ciphersuites.
   That will be true provided:
    - the encoding method for RSAE_RSA* signatures is PSS,
    - the inner layer only gives access to a signing oracle for
      PKCS #1 type 0 with MD5 and SHA-1 hashing done internally.

   If hashing is not done internally, there is a practical attack
   when the outer layer is compromised, that allows impersonating
   the server. However, not doing hashing internally is an extremely
   bad idea, and allows a similar attack much easier than factoring
   on the existing ciphersuites.

4. Deliberate key compromise
   a. insider attacks
      Insiders are no different from any other attacker who
      compromises the server, except that they may also have
      physical access. This doesn't appear to introduce any new
      problems that don't also apply to the existing ciphersuites.
   b. legal attack
      Some countries (e.g. the UK) have laws that can compel someone
      to disclose a key needed to decrypt information, if it is
      still available. If a server administrator is asked to do
      this for an ephemeral key, then:
       - if the key has been deleted, then it obviously isn't possible
         to disclose it. In that case all the administrator could
         do is provide the plaintext, if it has been retained or
         can be reconstructed.
       - if the key has not been deleted, the server administrator
         could say that it is an authentication key that allows
         impersonating the server, and therefore that he/she
         wants to give the session key instead. One way of doing
         that is for whoever was intercepting the session to give
         the administrator a copy of the handshake messages, and
         the ephemeral key can then be used to decrypt the
         ClientKeyExchange message. The UK "RIP Act" and the
         accompanying code of practice is supposed to be drafted
         to allow things like this, although realistically, it
         would probably only be practical to intercept sessions
         with prior arrangement with the server administrator,
         since ephemeral keys will be deleted too quickly otherwise.

Have I missed anything?

[snip]
> sacrificing security.

If I thought it was sacrificing security, I wouldn't be suggesting it.

> You may not consider that sacrifice to be

You appear to be thinking of a model where as each session terminates,
it immediately becomes impossible to recover its keys. That isn't achieved
by the DHE ciphersuites, because the session cache holds master secrets
for up to a day (if the "suggestion" in section F.1.4 of RFC 2246 is
followed):

# An upper limit of 24 hours is suggested for
# session ID lifetimes, since an attacker who obtains a master_secret
# may be able to impersonate the compromised party until the
# corresponding session ID is retired.

The server can choose a shorter limit, of course, or it can return
a zero-length session ID, meaning that the session cannot be resumed.
I doubt many servers do the latter in practice (for HTTP, in particular,
it would kill performance [*]). There is currently no way for the
client to make any request for, or to require a shorter maximum
lifetime for master secrets.

[*] less so if HTTP 1.1 is used, but then the client would have to
    keep connections open for longer than would normally be desirable.

Also, if an attacker notices a particularly interesting session, it can
break into the server while the session is still in progress, and get
the master secret that way. Note that renegotiating session keys
without doing a full handshake does not ensure forward secrecy for the
part of the session before the renegotiation, which is significant
for applications that use long-lived sessions.

These problems could be fixed by applying a one-way hash to the master
secret as it is stored in the cache, and every time it is subsequently
used. However, I think that could only be done in the next TLS version
(since the client and server have to agree on whether the master secret
will be hashed). For SSL 3.0/TLS 1.0, the extent to which the DHE
ciphersuites provide forward secrecy depends on the expiry time of the
session cache. Technically, a server could even cache master secrets
indefinitely and still conform to the spec.

>    ever compromised, the whole game is up. The static key must be
>    revoked as well.

Yes, at any given time two keys (and possibly another that is being
generated) have to be controlled tightly instead of one.

>From another article:
>> is valid. On the other hand, you introduce a requirement for at least
>> somewhat synchronized clocks into the protocol.

I'd have no objection to putting an expiry time in the signature, as a
second line of defense (for example to make sure that if a flaw were
found in the protocol, the validity time of signatures on all ephemeral
keys signed up to that point would be limited, as long as a client's
clock cannot be forced to an earlier time). This is quite different
from relying completely on synchronised clocks for security, as, say,
Kerberos does.

Note that we already rely on clients having a clock, and it not being
totally wrong (e.g. if a clock gets reset to 1970 or 1980, which might
be quite a common failure mode in battery-operated devices, for instance,
then certificates will not verify).

> Basically, you've created something which is better than static RSA but

Exactly the same could be said of the DHE ciphersuites, since they don't
provide what I think you mean by "true PFS" either (see above).

> and one without (static RSA).

> Then, those who DO care about PFS can have

The only possible advantage in using ciphersuites that don't provide
forward secrecy, would be performance. If forward secrecy can be achieved
without significant performance penalty (I don't consider the extra RSA
verification by the client to be significant), then there is no reason
why it shouldn't be required.

> reasonable to do in a protocol standard,

Why not?

> particulary since you've managed to do it by sacrificing PFS.

The strictest possible version of forward secrecy could only be
achieved by not storing master secrets at all after the handshake,
and applying a one-way hash to all the secret information associated
with a connection *each time a block is sent*. (Even this assumes that
the data doesn't exist in plaintext on the server, but that's beyond
the scope of a transport-layer security protocol.)

In practice, forward secrecy is always time limited, i.e. the most
it can guarantee that if an attacker compromises the server at time T,
it will not be able to recover data sent before time T - X. It's just
a matter of how long X is.

The TLS 1.0 spec is very lax about requiring sensitive secrets to
be deleted quickly; it's not possible to pin down a guaranteed value
for X at all. I would be strongly in favour of making the changes
necessary to guarantee a reasonable upper bound on X (some of which
can only be done in the next TLS version).

The practical reason for wanting X to be as small as possible is
to limit the damage done by a compromise. While an attacker is
actually controlling the server, he/she can get the keys for all
connections that are active during that time. So if a compromise
lasts, say, 20 minutes, then reducing X from 10 minutes to 10 seconds
is not going to improve security by a substantial amount - the attacker
still gets 20 minutes + 10 seconds' worth of data, as opposed to
30 minutes.

Also, we want forward secrecy to be practical for small clients.
You've done a good job of convincing me of the need to use RSA, both
for performance on small clients, and because that's what HTTPS
servers currently have certificates for. So, RSAE_RSA*, or something
very much like it, is what we need for a common-case ciphersuite.

[BDL97]  Dan Boneh, Richard A. DeMillo, Richard J. Lipton,
         "On the Importance of Checking Cryptographic Protocols
          for Faults,"
         Advances in Cryptology - Proceedings of EUROCRYPT '97.

[RS98]   R. Rivest, R. Silverman,
         "Are 'Strong' Primes Needed for RSA?"
         December 1, 1998 (also RSA Laboratories tech note, August 1, 2000).
         http://www.rsalabs.com/technotes/
         (the PDF version has some minor font problems)

[KSWH98] J. Kelsey, B. Schneier, D. Wagner, C. Hall,
         "Cryptanalytic Attacks on Pseudorandom Number Generators,"
         Fast Software Encryption, Fifth International Workshop
         Proceedings (March 1998), Springer-Verlag, 1998, pp. 168-188.
         http://www.counterpane.com/pseudorandom_number.html

[Gut00]  Peter Gutmann,
         "Software Generation of Practically Strong Random Numbers"
         (updated June 2000),
         Original version presented at the 1998 Usenix Security
         Symposium.
         http://www.cryptoengines.com/~peter/06_random.pdf

- -- 

---

---

From: Dr S N Henson <[email-masked]>
Date: Wed, 25 Oct 2000 13:24:36 +0100

> attacks against PKCS #1 type 0, attacks against the RNG, etc. need to

I may be missing something here but I'm not sure where the "type 0
attacks" fits into this. I presume "type 0" refers to PKCS#1 v1.5 block
type 0. TLS always uses block type 1 (see RFC 2246 8.1.1).

>    require at least firmware changes in order to support the new

Here I think is the problem. Current servers may well allow unrestricted
signing with the servers private key and it may use some standard such
as PKCS#11 for this operation which doesn't AFAIK currently have a
mechanism that can be restricted in this way. Getting a new mechanism
standardised and getting hardware vendors to support it (assuming their
harware can) is likely to be time consuming.

As I believe you have mentioned, unrestricted signing would allow an
attack on the server to sign a bogus public key and then use it to
perform "man in the middle" attacks on the server until its certificate
expired (or was revoked if the clients actually checked revocation).

I'd also say that many servers would want to use more than just one key
for all ephemeral cipher suites. I know of some that have a "pool" of
ephemeral keys and use one at random. This would place additional
demands on the server crypto hardware.

Steve.

---