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

From: Sean Turner <[email-masked]>
Date: Tue, 4 Nov 2014 12:49:21 -0500

Hi!

At the TLS Interim meeting in Paris, the WG discussed the FF DHE draft (https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-ff-dhe/).  The chairs would like to poll the WG on one of the issues in the draft namely the size of the minimum group.

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.

1) 3DES has a 112-bit work factor and is still considered acceptable in TLS 1.2 and the DLOG keying material shouldn’t be any weaker than the symmetric cipher.

2) There is some disagreement about the work factor for the DLOG keys - e.g., NIST says 112-bit work factor correlates to 2048-bit DLOG keys but ECRYPT-II says 112-bit work factor correlates to 2432-bit DLOG keys (see references in draft).

3) The other point made about 2048-bit DLOG is that it’s a power of 2 and there’s parity with the public key sizes.

Cheers,
j&s

---

From: Martin Thomson <[email-masked]>
Date: Tue, 4 Nov 2014 09:56:48 -0800

> 3) The other point made about 2048-bit DLOG is that it’s a power of 2 and there’s parity with the public key sizes.

I don't find the power of 2 thing particularly compelling when the
next point is 3072.  What might be more compelling is support for an
assertion that 2048 is more likely to cause the extension to be used
over the current arbitrary groups.

Otherwise, I'm all for having stronger keys.  2432 is an odd choice,
2560 might have been easier to understand, but more is better, right?

---

From: Yoav Nir <[email-masked]>
Date: Tue, 4 Nov 2014 20:55:02 +0200

2048

I have very little use for FF DHE, but matching the strength of the certificates that are in use (and RSA 2048 is overwhelmingly more popular at this point than ECDSA or RSA with greater values). 

Yoav

> On Nov 4, 2014, at 7:49 PM, Sean Turner <[email-masked]> wrote:
> 
> Hi!
> 
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 04 Nov 2014 19:56:31 +0100

2048

Manuel.

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 4 Nov 2014 11:05:03 -0800

2048 to match the strength of the (likely) certificates in use.

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 4 Nov 2014 19:09:29 +0000

>2048 to match the strength of the (likely) certificates in use.

+1  (and that doesn’t mean 2049 :)

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 4 Nov 2014 14:14:47 -0500 (EST)

----- Original Message -----
[...]
> 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.
> 
> 1) 3DES has a 112-bit work factor and is still considered acceptable in TLS
> 1.2 and the DLOG keying material shouldn’t be any weaker than the symmetric
> cipher.
> 
> 2) There is some disagreement about the work factor for the DLOG keys - e.g.,
> NIST says 112-bit work factor correlates to 2048-bit DLOG keys but ECRYPT-II
> says 112-bit work factor correlates to 2432-bit DLOG keys (see references in
> draft).
> 
> 3) The other point made about 2048-bit DLOG is that it’s a power of 2 and
> there’s parity with the public key sizes.

I vote for 2432. Since we have two conflicting advices (NIST and ECRYPT), IMO
the best is to go with the most conservative one (especially given that this
draft is going to be fully deployed years from now).

regards,
Nikos

---

From: Stephen Checkoway <[email-masked]>
Date: Tue, 4 Nov 2014 12:20:40 -0700

> draft is going to be fully deployed years from now).

Going with ECRYPT-II's recommendation of 2432 as it is the more conservative advice gets my vote.

-- 
Stephen Checkoway

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 04 Nov 2014 14:22:49 -0500

> 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 d…

as the original author who selected 2432, i still think 2432 is the most
reasonable choice based on ECRYPT's assessments.

	--dkg

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 4 Nov 2014 14:24:35 -0500 (EST)

----- Original Message -----
> 2048 to match the strength of the (likely) certificates in use.

That's not a good argument. If in 4 years the 2048-bit certificates
are broken, we can simply reissue stronger ones with no damage to past
sessions. If the 2048-bit DH can be broken, all the past sessions could
be read.

The DH parameters relate more to the security of the encryption function,
rather than the certificate's.

regards,
Nikos

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 04 Nov 2014 11:51:12 -0800

> 3) The other point made about 2048-bit DLOG is that it’s a power of 2 and there’s parity with the public key sizes.

An interesting question is if 2432 is optimal to accommodate wide words 
/ vector arithmetic.

2^9 * 5 = 2560  (5 512-bit units, or 10 128-bit units)
2^7 * 19 = 2432 (128 bit units)

Besides, there is a benefit to pick a round number. For example, RSA 
2048 is much faster than 2432 in openssl master today on x86.

So, while I am OK with a stronger size, 2432 looks like sub-optimal, so 
of these two I would select RSA 2048.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 4 Nov 2014 13:37:55 -0800

> sessions. If the 2048-bit DH can be broken, all the past sessions could

I'm actually not a big fan of the argument from alignment:

A strong ephemeral exchange protects session confidentiality from some
future break or brute forcing (if that's even feasible), outside of
the window where an active attack (impersonation or hijacking) based
on a break might be possible.  If keys are properly ephemeral, an
attacker only has while the session is active (or resumptions of the
session).

A strong authentication key protects a session from MitM attacks at
the time of session creation.  Authentication keys also have an
applicability window, which is limited by the expiration of the
associated certificate (plus the relevant clock skew under the
NTP-style attacks).

There's an argument to be had for stronger ephemeral keys on this basis.

In the end, I don't care particularly.  I'd like to know if anyone
making arguments for either side feels so strongly that they would
strongly object to either.  If we're just assembling preferences, then
it's hard to see a way we can reach consensus on whether number A is
better than number B.

p.s., Clearly 2^521-1 is the best number.  It's not even clear that
there is any point arguing about the minor placings.

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 5 Nov 2014 01:23:14 +0000

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.
> 
> 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.

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)?

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?

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.

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

What is the cost to the defender of using 2432 vs. 2048?

-- 
	Viktor.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Nov 2014 18:19:03 -0800

> choose to disable (P)FS, and stick with RSA key exchange.

They could also adopt ECC if performance is a concern.

> 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.

> 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.

> trade-off without some knowledge of the relative costs/benefits.

ECC is the best choice by a wide margin here.

> 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.

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

---

From: Russ Housley <[email-masked]>
Date: Tue, 4 Nov 2014 22:15:00 -0500

I support inclusion of 2048-bit FF DHE kays.

Russ

---

From: Bodo Moeller <[email-masked]>
Date: Wed, 5 Nov 2014 11:00:48 +0100

Sean Turner <[email-masked]>:

> To help us reach consensus on this point, please reply to this email
> indicating whether you favor a “2048" or “2432” minimum group size.

2048.

In applications where you're concerned that a 2048-bit DH group might be
too small, you most certainly should not be using 112-bit or 128-bit
symmetric encryption keys for your connections in the first place: as soon
as there a multiple connections that an attacker may be interested in
(which must be assumed for TLS), a k-bit symmetric key won't give you
"k-bit security" in any meaningful sense anyway.

(Apparently this important issue isn't well-understood, but
see draft-ietf-tls-negotiated-ff-dhe-02's reference [ENISA] for some
discussion; or see
http://www.ietf.org/mail-archive/web/cfrg/current/msg04935.html etc.)

Conversely, if 128-bit symmetric encryption is well above your required
security level, having to use a 2432-bit group instead of a 2048-bit group
would be unreasonable overhead.

Bodo

---

From: Hanno Böck <[email-masked]>
Date: Wed, 5 Nov 2014 11:43:14 +0100

I find it a bit odd to have this question without any numbers on
benchmarks.

I am usually in the "give me more bits"-camp, but I don't see anything
even close to breaking 2048 bit dh. Ultimately, I think it's reasonable
to assume that this will only fall when quantum computers will rise.
But then all EC will fail earlier, so we'll have other things to worry
than DH group size.

If using 24xx or 25xx will significantly hinder adoption of fixed
groups due to performance constraints I'd vote for 2048. But I feel I
don't have the numbers to judge.

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 05 Nov 2014 12:23:16 +0100

> reason: SNFS uses the same characteristics as we would use to optimize
Unless I'm mistaken, if textbook multiplication is used, it's rather cubic:
multiplication is quadratic, and the length of the exponent, which is roughly
the number of multiplications, is linear in the size of the group.

Which gives a 67% performance penalty for 2432 compared to 2048

Now, for this size, Karatsuba is probably the best multiplication algorithm,
which is about n^1.58, so a total of n^2.58 for exponentiation, which gives a
performance penalty of 58% with this algorithm.

Manuel.

---

From: Bodo Moeller <[email-masked]>
Date: Wed, 5 Nov 2014 12:56:43 +0100

Viktor Dukhovni <[email-masked]>:

> with prime order $q$, where $q$ is a much shorter prime

Wrong, see draft-ietf-tls-negotiated-ff-dhe-02.  The new groups have prime
group order q = (p-1)/2.

Manuel Pégourié-Gonnard <[email-masked]>:

multiplication is quadratic, and the length of the exponent, which is
> roughly

No, because you can still use short exponents. If you're doing that,
draft-ietf-tls-negotiated-ff-dhe-02 recommends (at least) 224 bits [*] for
the exponent when using the 2432-bit modulus.

Bodo

[*] Minor editing issue: it actually says that you can use exponents in the
[2,2^224] range, but also says that you "should choose a secret key of at
least 224 bits". Since there's no discussion of leading zeros in the
document (I think), the latter could be read as requiring a [2^223, ...]
range.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 05 Nov 2014 13:17:17 +0100

On 05/11/2014 12:56, Bodo Moeller wrote:
>> roughly the number of multiplications, is linear in the size of the group.
>> 
Right, thanks for pointing that out. For some reason I assumed the short
exponent would be longer for the 2432-bit group than for the 2048-bit, but of
course this is stupid because both target the 112-bit security level, and the
question is which FF size corresponds to that level.

Manuel.

---

From: Hubert Kario <[email-masked]>
Date: Wed, 05 Nov 2014 13:20:23 +0100

On Tuesday 04 November 2014 12:49:21 Sean Turner wrote:
> Hi!
> 
> At the TLS Interim meeting in Paris, the WG discussed the FF DHE draft
> (https://datatracker.ietf.org/doc/draft-ietf-tls-negotiated-ff-dhe/).  The
> chairs would like to poll the WG on one of the issues in the draft namely
> the size of the minimum group.
> 
> “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.

2048

This is of issue only to legacy applications that don't implement ECC, so 
higher security margin is of limited importance.
That's a work factor difference of around 10 bits, that's rather close to the 
difference between 3DES and AES128...

implementations of "round" numbers are much more likely to be optimised for 
higher performance in currently deployed software

It matches currently deployed base (around 4% of TLS-enabled Alexa top 1 
million servers use 2048 bit DH, while the ones that use any size between 2048 
and 3072 can be counted on one hand)

I don't know if there are HSMs that are used for DH key exchange, but of ones 
that I used, all supported only very specific RSA key sizes.

-- 
Regards,
Hubert Kario

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 05 Nov 2014 09:23:40 -0500

> document (I think), the latter could be read as requiring a [2^223, ...]

Thanks for this suggestion, Bodo.  i'll incorporate it in the next revision.

	--dkg

---

From: Rene Struik <[email-masked]>
Date: Wed, 05 Nov 2014 09:37:58 -0500

Hi Sean:

I think supporting 2048-bit defined discrete log groups would be 
acceptable.

Added note (not part of scope of the straw poll):
It would be useful to explicitly state that if short exponents are used 
with these 2048-bit defined groups, these shall be drawn at random from 
the set of 224-bit integers. (The current draft does not spell this out 
explicitly.) Of course, the more conservative expression would be "drawn 
at random from the set of m-bit integers, where m is at least 224".

Best regards, Rene

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Sean Turner <[email-masked]>
Date: Wed, 26 Nov 2014 01:47:45 -0500

Thanks to all those who participated in this poll, but after three weeks it’s time to close this poll.  The rough consensus expressed on this list is for 2048 as the minimum FF DHE group size.

dkg - please make the appropriate changes in the draft.  While you’re at it, please go ahead and add text to address the comment from the mic for a reference to how one can check that the primes are prime.

Once dkg posts as new version we’ll initiate a WGLC.  As noted during the TLS session in Hawaii, the chairs make a point to ensure whether using new groups vs the old IKE groups is an issue.

Cheers,
J&S (as chairs)