[Security] TLS Certificates Verification

Eric Rescorla ekr at rtfm.com
Wed Aug 20 11:54:12 CDT 2008

On Wed, Aug 20, 2008 at 9:38 AM, Jonathan Schleifer
<js-xmpp-security at webkeks.org> wrote:
> "Eric Rescorla" <ekr at rtfm.com> wrote:
>> I must be missing something here:
>> 1. Key generation in DSA-based systems is just as fast as ephemeral
>>     DH key generation, as long as you use a pregenerated group.
>> 2. Key generation in RSA-based systems is slower, but still a matter
>>     of a second or two on any reasonably modern system.
> Oh, generating an OTR key takes a few seconds here, on my 450 MHz
> NetBSD box it even took about an hour, because /dev/random is used
> there. So waiting an hour on some systems is ok for the user? I really
> don't think so…
>> If you're going to use public key cryptography, you need to generate
>> public keys.
> That's why I'm AGAINST using public keys, we could use secrets, like it
> can be done with ESessions.

I fear you're a little confused about the cryptographic situation here.

In order to have a secure connection between Alice and Bob, they need
to establish a shared secret with between 80-256 bits of secret entropy.
There are two ways to do this:

1. Exchange an 80-256 bit symmetric key.
2. Use public key cryptography (which includes RSA, DH, etc.)

Since, as you've so forcefully articulated, nobody is going to exchange an
80-256 bit symmetric key, that leaves public key cryptography.

Now, it's possible to use the exchange of a short value to authenticate a
public key exchange. This is what ESessions does with SAS and what
SRP does. However, in both cases, you are doing public key:
in ESessions you are doing Diffie-Hellman and in SRP you're doing
something very similar to Diffie-Hellman.

Now, as to the cost of generating keys:

- The primary cost of generating RSA keys is to generate two primes of
  half the size of the modulus, i.e., two 512-bit primes for a 1024-bit modulus.
  This is fairly expensive because you need to test each candidate prime.
  This cost cannot be amortized and must be paid once for each RSA key you
  generate. This is why the classic approach is to generate a single RSA key
  that you use for the long term.

- The cost of generating keys for DH or DSA is split into two parts:
  + The cost of generating a group (this is the expensive part).
  + The cost of generating a key in the group.
  Luckily, everyone can share the same group, and if we agree to do that then
  key generation is very fast, much faster than RSA key generation. This is why
  people prefer ephemeral Diffie-Hellman when they want to provide a new key
  pair for each connection.

In any case, it's quite possible to have long-term keys which are fast
to generate:
use DSA from a pre-generated group.

Now, it's absolutely true that *once you have established a single connection*,
you can save the secret entropy and do new connections without incurring an
public key cost, but you still have to do the initial public key
exchange. I know
TLS has this feature, but it's not clear to me that ESessions does.

In any case, no, I don't believe ESessions allows you to remove the cost of
generating asymmetric keys (unless you're willing to exchange a large secret).
As far as I know, that's not possible (although there are techniques for pushing
the load to one side or the other).


More information about the Security mailing list