Re: [TLS] Short Ephermal Diffie-Hellman keys

[Bodo Moeller <[e-mail]>]

On Sun, Jun 03, 2007 at 08:07:10AM -0700, Eric Rescorla wrote:
> At Wed, 16 May 2007 00:43:51 +0200,
> Bodo Moeller wrote:

>> I'd suggest stating in the TLS specification that 'q' can only be
>> included in the ServerKeyExchange message for the case of prime-order
>> subgroups.  These are what you'd usually use, except sometimes if the
>> DH subgroup is nearly as large as 'p', which is a case where knowing
>> 'q' doesn't provide significant benefits anyhow.

> So, I'm no DH expert, but my understanding is that there are three
> common cases:
> 
> 1. Randomly generated p with no special structure
> 2. Sophie-Germain primes where q is about p/2.
> 3. DSA-style groups where q<<p.
> 
> Only in the last case does carrying around q offer much benefit.

This is almost true.  (The first case should be avoided: if you want
to avoid the cost of finding a Sophie-Germain prime, use a DSA-style
group instead.  There are other cases of special structure besides #2
and #3 that are safe to use, though, and where you might not be using
a prime order subgroup.)

In the strong-prime case (#2: q is a Sophie-Germain prime, p = 2q + 1
is a strong prime), you'd have to be shown q (or do a very expensive
test) to positively know that p is indeed a strong prime.  Once you
know this, you can save time by using short DH exponents in this case
just as in the DSA-style case.  So knowing q is useful for the client
in the strong-prime case too.


> Is this common enough that it's worth changing the spec?

It could very well become common.  With the protocol as it is now,
there isn't that much gained by using a DSA-style group because this
only helps the server, not the client.  And those client
implementations that don't care about spending five times or so
more time than necessary on the DH exchange could simply ignore the
extra information.


>                                                          It was
> my understanding that we mostly encouraged people to use S-G primes
> in any case.

There is no reason to recommend strong primes over other primes for
ephemeral DH.  They can be quite useful when using a *fixed* DH key
(because if you use a DSA-style group, you'd need a subgroup
membership test, which essentially means you'd lose the performance
advantage of using a fixed DH key -- and then the total cost of the DH
exchange with a DSA-style group might even be higher than with a
strong prime and short exponents).  But there is no need to use a
fixed DH key for an ephemeral DH key exchange: usually, this should be
avoided.

We don't have to encourage people to use strong primes for the
ephemeral DH key exchange.  Rather, we should encourage them to use
properly ephemeral DH -- i.e., not to reuse DH keys for more than a
single handshake.  If they do that, then they can gain a lot by using
DSA-style groups.

Bodo


_______________________________________________
TLS mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/tls