Subject: Re: [TLS] Short Ephermal Diffie-Hellman keys

From: Eric Rescorla <[email-masked]>
Date: Sun, 03 Jun 2007 08:07:10 -0700

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.

Is this common enough that it's worth changing the spec? It was
my understanding that we mostly encouraged people to use S-G primes
in any case.

-Ekr

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

---

From: Bodo Moeller <[email-masked]>
Date: Sun, 3 Jun 2007 18:52:18 +0200

> 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

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

---

From: Russ Housley <[email-masked]>
Date: Sun, 03 Jun 2007 13:21:36 -0400

>my understanding that we mostly encouraged people to use S-G primes

I think that FIPS 140 validated modules will use 3.  And then, one 
needs to know q to detect small subgroups.

Russ

---

From: Bodo Moeller <[email-masked]>
Date: Sun, 3 Jun 2007 21:47:31 +0200

>> [...]                                                    It was

> needs to know q to detect small subgroups.

You don't really have to check that other parties' public DH keys are
in the proper subgroup (that is, in the order-q subgroup) when using
*single-use* DH keys yourself.  There's nothing that could be gained
through small-subgroup attacks in this case, and thus no need to
check.

Of course, you do need q to efficiently perform DH operations in this
setting.  Since you don't need subgroup membership tests with them,
single-use DH keys are very practical.

Bodo

---

From: Russ Housley <[email-masked]>
Date: Sun, 03 Jun 2007 15:55:59 -0400

Thanks for the correction and clarification.

Russ

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 05 Jun 2007 19:09:10 +1200

Eric Rescorla <[email-masked]> writes:

>So, I'm no DH expert, but my understanding is that there are three common
>cases:
>
>Is this common enough that it's worth changing the spec? It was my
>understanding that we mostly encouraged people to use S-G primes in any case.

Use of S-G primes is mostly historical.  I use the Lim-Lee algorithm, which
both produces known-good (verifiable) DSA-style primes, and is extremely
efficient (far more so than anything that produces S-G primes).  Having an
ability to (optionally) specify DSA-style parameters would be a considerable
help.

(Actually I'd make them mandatory, but I suspect that'd get too many
complaints from existing users.  Mind you given the current low use of DH
compared to the near-universal RSA, it'd be nice to get implementors into good
habits early and require verifiable DSA-style parameters).

Peter.