Re: [TLS] DH group validation

[Bodo Moeller <bmoeller at acm.org>]

On Sat, Oct 20, 2007 at 12:25:45PM -0700, Eric Rescorla wrote:

>> I am hoping that we can agree to (optionally?) include "q" into DH
>> parameters for the next version of the standard, allowing for more
>> meaningful quick "validation" on the one hand, and for efficiency
>> improvements on the other hand.  (Efficiency improvements since if you
>> have a 2048-bit p with a 224-bit q, the client has much less work to
>> do if it knows it only has to choose an exponent in the range (2, q-1)
>> and not a 2048-bit exponent.)  In this case, the client would look
>> at the size of q to see if it looks reasonably large, and presumably
>> also would check that q is at least one bit longer than q.

> I want to make sure I understand this:
> 
> 1. Is knowing the factorization important in this case? I'm not
>    really a DH expert, but this paper http://eprint.iacr.org/2004/099
>    seems to argue that if you're digesting ZZ, you don't need to
>    know the factorization of p-1. It looks like this may only be
>    true if the generator is random? Maybe Hugo can weigh in
>    here...

When above I say "q", I actually mean that q would be a prime, and
that the given DH generator would be the generator of an order-q
group.  This is something that the specification would have to
require.  We could make the specification more complex and allow other
configurations, but this looks pretty pointless to me: Instead, for
non-prime group order (or if you don't know the order), I figure you'd
simply omit q in the handshake message.

Groups of non-prime order can work too for DH.  I won't rehash (no pun
intended) the results of the Hashed Diffie-Hellman paper that you are
citing, but merely point out that it does *not* state that DH
exponents can be as short when *not* using a prime-order generator as
they can be when using a prime-order generator!  In fact, if the group
is not of prime order, this usually means that exponents do have to be
longer.  If you don't even know the group order, you'll have to use
longer exponents just in case.


> 2. This is an optimization only for the client, right? The server at
>    least potentially knows the factorization of p-1, so sending 
>    this information doesn't make the server any faster.

Certainly!  This is about information that the server sends to the
client, since in TLS any DH parameters are always provided by the
server.  If the server can send the information, then the server also
knows the information; and it can use it without having to know
whether the client is making use of it too: The server simply will
pick its private DH exponent from the positive integers below q if it
knows that the DH generator has order q, or even from a subset of
shorter integers as determined by the required security level (which
can be safely done assuming that, as required above, q is prime).

Bodo



_______________________________________________
TLS mailing list
TLS at lists.ietf.org
https://www1.ietf.org/mailman/listinfo/tls