Re: [TLS] STRAW POLL: Size of the Minimum FF DHE group

[Watson Ladd <[e-mail]>]

On Tue, Nov 4, 2014 at 5:23 PM, Viktor Dukhovni <[e-mail]> wrote:
> On Tue, Nov 04, 2014 at 12:49:21PM -0500, Sean Turner wrote:
>
>> The draft currently includes a minimum group size of 2432 but the WG also
>> discussed 2048.  Groups smaller than 2048 were discounted for a standards
>> track document as too weak for use but might be documented in a separate
>> "historic" draft.  To help us reach consensus on this point, please reply
>> to this email indicating whether you favor a "2048" or "2432" minimum
>> group size.  Note we're also looking to specify the smallest number of
>> options for groups as is acceptable - i.e., we're not looking at specifying
>> both 2048 and 2432.
>>
>> Background: Regardless of whether you agree with what follows or not, the
>> following has been put forward as the rationale. We don't need comments
>> on the rationale, we're just providing it for background.
>
> Has any consideration been given to the question of how much of a
> barrier to the use of Forward-Secrecy larger key sizes might pose?
>
> If using DHE imposes a sufficient performance cost, sites might
> choose to disable (P)FS, and stick with RSA key exchange.

They could also adopt ECC if performance is a concern.

>
> I take it the new DHE $\mathbb{Z}^*_p$ subgroups will be cyclic
> with prime order $q$, where $q$ is a much shorter prime (twice the
> desired security level bits as with the various DSA groups).  If
> so, how much of a performance advantage does this provide relative
> to using generic $F_p$ groups for which the order of the generator
> is not known (as with DHE in TLS today)?

They are not of that form, but rather q=(p-1)/2. However, short
exponents can still be used to accelerate DHE: this is independent of
the group's order. This cannot be done with signature keys.

>
> Basically, what's the expected ratio of DH-per-second between the
> two proposed field sizes, and between the 2048-bit group and $F_p$
> with $q = (p-1)/2$ and $p$ a 2048-bit Sophie-Germain prime.  Is
> the "new" 2432 as fast or faster than the "old" 2048?

Slower, by a quadratic factor assuming standard algorithms for bignum
arithmetic. No acceleration of either is possible, and for good
reason: SNFS uses the same characteristics as we would use to optimize
arithmetic.

>
> Choices of parameters are a trade-off.  With unlimited CPU/network
> we could go with 16k-bit primes.  It is difficult to make such a
> trade-off without some knowledge of the relative costs/benefits.

ECC is the best choice by a wide margin here.

>
> What is our lowest estimated cost to the adversary of breaking
> 2048-bit DH with purpose-built hardware?

Significantly worse than 2048-bit RSA, due to being able to reuse the
relations and build a large factor base that will accelerate the
finding of additional discrete logs.

>
> What is the cost to the defender of using 2432 vs. 2048?
>
> --
>         Viktor.
>
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin