Subject: [TLS] draft-sheffer-tls-bcp: DH recommendations

From: Yaron Sheffer <[email-masked]>
Date: Sun, 15 Sep 2013 22:11:20 +0300

Hi,

I've been working with Ralph Holz on -01, and we would like the group's 
opinion before we publish.

Several people proposed that we recommend parameter lengths for RSA and 
for Diffie Hellman. RSA is easy enough, and we will recommend 2048 bits. 
The situation with DH is extremely messy, and if we're not careful, we 
might actually hurt security by recommending a reasonable parameter length!

Basic facts and assumptions:

- Brute force difficulty is similar for RSA and DH parameters of the 
same length.
- When using DHE, the TLS master key depends on the DH exchange only, 
and the certificate size doesn't matter.
- 1024 bit DH (or RSA) is still very common, but is too weak to 
recommend for the next few years.

We would like to recommend using 2048-bit DH by both client and server 
(maybe 1536 bits for performance, but for sure not 1024). But reading 
[1] and similar posts, this could have two undesirable consequences.

1. Some older clients will break (abort the negotiation) if they offer 
DHE, the server accepts it but sends a DH value whose length they don't 
support (e.g. higher than 1024). You might end up with a non-TLS 
connection or a 404, rather than the client retrying with no DHE.

2. New clients will follow our recommendation and offer DHE, but then 
will only receive 1024-bit DH parameters from (an older) server and will 
end up negotiating a weaker session than they would have negotiated if 
they'd avoided DHE, if the server happens to use 2048-bit RSA. (Yes, 
whether this is "weaker" depends on your threat model).

Problem #1 goes away if we say that the server only sends 2048-bit DH 
parameters to "new" clients (those that offer TLS 1.2), and assume these 
can all deal with DH of any length. Our draft recommends a TLS 1.2-only 
cipher suite anyway. And since new clients are still rare, this could work.

This partial solution is complicated by IE10, which (AFAIK) supports TLS 
1.2, but has this support off by default, and does not support larger 
than 1024-bit DH.

Problem #2 is mitigated if we suggest that clients fall back to non-DHE 
if the server cert is long enough, specifically to 
TLS_RSA_WITH_AES_128_GCM_SHA256. That is, if the client doesn't like the 
returned DH parameters, it aborts the session and re-negotiates it 
instead of choosing the 1024-bit DH option.

This extra logic is ugly. But if we cannot recommend >1024 DH, we may be 
better off giving up on PFS for now. Long term, I believe that TLS 
should negotiate DH explicitly.

Your thoughts, opinions and even facts :-) are most welcome.

     Yaron

[1] 
http://blog.ivanristic.com/2013/08/increasing-dhe-strength-on-apache.html

---

From: Yoav Nir <[email-masked]>
Date: Sun, 15 Sep 2013 19:56:15 +0000

Hi, Yaron

Why do we need to give up on PFS? There are ECDHE ciphersuites that are supported by nearly all browsers as well as well as OpenSSL (which means also Apache), IIS and others. Connect from any browser other than Opera to a Google server, and you'll be using a ECDHE-RSA ciphersuite.

So why do we need to give up on PFS?

Also, you are right that it depends on your threat model, but I think under most reasonable threat models, it's easier to steal a long-term private key (even if it's 2048-bit) than to calculate a discrete log in a 1024-bit group. Even harder to calculate a discrete log once for each session (it is ephemeral D-H), than to steal a single private key that is stored on a hard disk for at least a year. 

So no, I don't think we should give up of PFS.

Yoav

On Sep 15, 2013, at 10:11 PM, Yaron Sheffer <[email-masked]> wrote:

> Hi,
> 
> I've been working with Ralph Holz on -01, and we would like the group's opinion before we publish.
> 
> Several people proposed that we recommend parameter lengths for RSA and for Diffie Hellman. RSA is easy enough, and we will recommend 2048 bits. The situation with DH is extremely messy, and if we're not careful, we might actually hurt security by recommending a reasonable parameter length!
> 
> - Brute force difficulty is similar for RSA and DH parameters of the same length.
> - When using DHE, the TLS master key depends on the DH exchange only, and the certificate size doesn't matter.
> - 1024 bit DH (or RSA) is still very common, but is too weak to recommend for the next few years.
> 
> We would like to recommend using 2048-bit DH by both client and server (maybe 1536 bits for performance, but for sure not 1024). But reading [1] and similar posts, this could have two undesirable consequences.
> 
> 1. Some older clients will break (abort the negotiation) if they offer DHE, the server accepts it but sends a DH value whose length they don't support (e.g. higher than 1024). You might end up with a non-TLS connection or a 404, rather than the client retrying with no DHE.
> 
> 2. New clients will follow our recommendation and offer DHE, but then will only receive 1024-bit DH parameters from (an older) server and will end up negotiating a weaker session than they would have negotiated if they'd avoided DHE, if the server happens to use 2048-bit RSA. (Yes, whether this is "weaker" depends on your threat model).
> 
> Problem #1 goes away if we say that the server only sends 2048-bit DH parameters to "new" clients (those that offer TLS 1.2), and assume these can all deal with DH of any length. Our draft recommends a TLS 1.2-only cipher suite anyway. And since new clients are still rare, this could work.
> 
> This partial solution is complicated by IE10, which (AFAIK) supports TLS 1.2, but has this support off by default, and does not support larger than 1024-bit DH.
> 
> Problem #2 is mitigated if we suggest that clients fall back to non-DHE if the server cert is long enough, specifically to TLS_RSA_WITH_AES_128_GCM_SHA256. That is, if the client doesn't like the returned DH parameters, it aborts the session and re-negotiates it instead of choosing the 1024-bit DH option.
> 
> This extra logic is ugly. But if we cannot recommend >1024 DH, we may be better off giving up on PFS for now. Long term, I believe that TLS should negotiate DH explicitly.
> 
> [1] http://blog.ivanristic.com/2013/08/increasing-dhe-strength-on-apache.html
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 15 Sep 2013 21:04:46 +0100

> So no, I don't think we should give up of PFS.

+1024 :-)

S.

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 16 Sep 2013 00:16:07 +0300

Hi Yoav,

ECDH groups are negotiated using RFC 4492 extensions, which surely makes 
them more usable today, and allows for crypto-agility in the future.

There are worries about the way the NIST curves were generated. AFAIU, 
most everybody uses P-256. Currently this is plain FUD, no-one can say 
whether and how you can backdoor ECDH if you control generation of the 
curves. But you can bet this research topic has suddenly become very 
popular.

If we assume that the adversary hoards millions of terabytes of network 
traffic for later decryption, perhaps in 10 years, then we need to worry 
about the strength of the curves we recommend today.

I guess for the time being we could recommend ECDHE with P-256, 
migrating later to a verifiably random curve like Brainpool.

Thanks,
	Yaron

---

From: Michael D'Errico <[email-masked]>
Date: Sun, 15 Sep 2013 14:21:10 -0700

DH can be sped up if you incorporate a medium-sized (e.g.
256-bit) prime q into the parameters.  See for example
Cryptography Engineering, pages 187-188.  Since q is
missing from the signed ServerDHParams, adding it would
require an extension.

We all know how hard it is to new get extensions deployed,
but perhaps there's now sufficient incentive....

Mike

---

From: Patrick Pelletier <[email-masked]>
Date: Mon, 16 Sep 2013 00:55:33 -0700

On 9/15/13 12:56 PM, Yoav Nir wrote:

> There are ECDHE ciphersuites that are supported by nearly all browsers as well as well as OpenSSL (which means also Apache), IIS and others.

Supported in the source, sure.  But Red Hat will disable it when it 
builds packages:

https://bugzilla.redhat.com/show_bug.cgi?id=319901

--Patrick

---

From: Xuelei Fan <[email-masked]>
Date: Mon, 16 Sep 2013 18:43:09 +0800

It's another worry that there is no way to negotiate the ephemeral DH 
key size.  A robust client may have to support 756/1024/1536/2048-bit 
keys. And a wildly deployed server may have to always use the wildly 
supported DH key sizes, for example 1024-bit, in order to server more 
clients.  If we want a new extension for ephemeral DH keys, it would be 
nice to support ephemeral DH key size negotiation.

Xuelei

---

From: [email-masked] (Martin Rex)
Date: Mon, 16 Sep 2013 23:17:25 +0200 (CEST)

> 1.2, but has this support off by default, and does not support larger 

IE10 is an awkward way to refer to an implementation.
What matters is what Microsoft's SChannel from the underlying OS supports.
And Microsoft seems to not support DHE with RSA
(only DHE_DSA, ECDHE_RSA and ECDHE_ECDSA).

Windows 7 & 2008R2 
http://msdn.microsoft.com/en-us/library/windows/desktop/aa374757%28v=vs.85%29.aspx 

Windows Vista & 2008:
http://msdn.microsoft.com/en-us/library/windows/desktop/ff468651%28v=vs.85%29.aspx

Windows XP & 2003
http://msdn.microsoft.com/en-us/library/windows/desktop/aa380512%28v=vs.85%29.aspx

-Martin

---

From: Yaron Sheffer <[email-masked]>
Date: Tue, 17 Sep 2013 12:25:34 +0300

Hi Martin,

you are right about Windows of course.

More generally, the draft is not trying to make recommendations that are 
actually implemented today by all browsers. We all know that 
implementation of TLS 1.2 is patchy to say the least. But we also know 
that the industry is in fact moving there. My personal goal is to make 
recommendations that will be useful (using real production software) 
mid-2014 or so, for people who are willing to update to the latest 
product releases.

Thanks,
	Yaron

---

From: Yoav Nir <[email-masked]>
Date: Tue, 17 Sep 2013 12:41:23 +0000

Hi Yaron

OK, so on the one hand we have DHE with 2048 bits which, (a) doubles the cost of a handshake with an 2048-bit RSA key, and (b) doesn't work in Apache and Windows.
On the other hand with have ECDH with P-256, which (a) far less than doubles the cost of the handshake, and (b) is implemented everywhere but disabled in a few places (clients running on RedHat)

To get DHE-2048, we'd need to patch Apache, change Windows, get everyone to use the new Windows, probably some more I forgot.

To get ECDH we need to change a compilation option of RedHat (and probably some other distributions). 

I think the choice is pretty much a no-brainer.

And if you're worried about NIST curves, there are people pushing brainpool and other curves on the TLS list. 

Yoav

On Sep 17, 2013, at 12:25 PM, Yaron Sheffer <[email-masked]>
 wrote:

> More generally, the draft is not trying to make recommendations that are actually implemented today by all browsers. We all know that implementation of TLS 1.2 is patchy to say the least. But we also know that the industry is in fact moving there. My personal goal is to make recommendations that will be useful (using real production software) mid-2014 or so, for people who are willing to update to the latest product releases.
> 
> Thanks,
> 	Yaron
>

---

From: Yaron Sheffer <[email-masked]>
Date: Tue, 17 Sep 2013 16:05:43 +0300

So yes, I agree. Here's from our work-in-progress -01 version:

As currently specified and implemented, elliptic curve groups are 
preferable over modular DH groups: they are easier and safer to use 
within TLS.

[...]

[RFC4492] allows clients and servers to negotiate ECDH parameters 
(curves). We recommend that clients and servers prefer verifiably random 
curves (specifically Brainpool P-256, brainpoolp256r1 
[I-D.merkle-tls-brainpool]), and fall back to the commonly used NIST 
P-256 (secp256r1) [RFC4492].

Thanks,
	Yaron

---

From: [email-masked] (Martin Rex)
Date: Tue, 17 Sep 2013 15:14:35 +0200 (CEST)

> preferable over modular DH groups: they are easier and safer to use 

Elliptic curve crypto is still fenced with non-expired patent claims,
requires an implementation of elliptic curve algorithms and the
relevant TLS extensions (something which is FAR from universally
available) and elliptic curve technology is considerably more
sensitive to side channel (=timing) attacks that DH, RSA & DSA.

-Martin

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 17 Sep 2013 09:29:28 -0400

Sure I'd agree with ECC implementations being more vulnerable to side-channel attacks than say RSA.

Patent-wise, the ECC situation now reminds me that of pre-pre-2000 RSA, when IETF and especially implementers wouldn't touch it with a 10-foot pole. 

I wish NSA lawyers did a better job negotiating with Certicom. 

My personal $0.02. 
--
Regards,
Uri Blumenthal                            Voice: (781) 981-1638
Cyber Systems and Technology   Fax:   (781) 981-0186
MIT Lincoln Laboratory                Cell:  (339) 223-5363
244 Wood Street                        Email: <[email-masked]>
Lexington, MA  02420-9185       

Web:  http://www.ll.mit.edu/CST/

MIT LL Root CA: 

 <https://www.ll.mit.edu/labcertificateauthority.html>

DSN:   478-5980 ask Lincoln ext.1638

----- Original Message -----
From: Martin Rex [mailto:[email-masked]]
Sent: Tuesday, September 17, 2013 09:14 AM
To: Yaron Sheffer <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [TLS] draft-sheffer-tls-bcp: DH recommendations

-Martin

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 17 Sep 2013 09:31:11 -0400

Darn. It meant to say "I'm NOT sure I'd agree..."

:-(

MIT LL Root CA: 

----- Original Message -----
From: Blumenthal, Uri - 0558 - MITLL [mailto:[email-masked]]
Sent: Tuesday, September 17, 2013 09:29 AM
To: [email-masked]' <[email-masked]>; [email-masked]' <[email-masked]>
Cc: [email-masked]' <[email-masked]>
Subject: Re: [TLS] draft-sheffer-tls-bcp: DH recommendations

My personal $0.02. 

MIT LL Root CA: 

----- Original Message -----
From: Martin Rex [mailto:[email-masked]]
Sent: Tuesday, September 17, 2013 09:14 AM
To: Yaron Sheffer <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [TLS] draft-sheffer-tls-bcp: DH recommendations

-Martin

---

From: Yaron Sheffer <[email-masked]>
Date: Tue, 17 Sep 2013 22:21:20 +0300

Hi Martin,

IMHO this is far from clear-cut.

There is some IPR mess surrounding ECC. But I know of vendors who are 
avoiding it by interpreting the IPR statement as referring to CAs 
(rather than endpoints), with the NSA license and RFC 6090 serving as 
fallback (NSA is your friend :-). As an example, Red Hat and Canonical 
are arguably in a similar position, but Canonical includes OpenSSL with 
ECC while RH disables it.

Our -00 draft proposed MODP DH, because it is simpler and more widely 
implemented. But I now prefer ECDH despite the drawbacks of ECC, because:

- Important implementations are broken, and will abort the connection 
when receiving >1024-bits DH.
- Modular DH cannot be negotiated, so there's no way for the server to 
know what the client supports and whether it'll break.

Thanks,
	Yaron

---

From: Ralph Holz <[email-masked]>
Date: Tue, 17 Sep 2013 15:39:32 +0200

Hi,

> To get DHE-2048, we'd need to patch Apache, change Windows, get
> everyone to use the new Windows, probably some more I forgot.
> 

I do think we should mention DHE-2048. It's the classic, well-understood
concept. I take a very conservative POV here, but ECC is younger and
less tested. Add to that the NSA speculations.

You're right about the Apaches, but Windows users, I think, should not
be too much of a problem once Microsoft decides to enable DHE-2048 and
push it out with their update mechanism.

> And if you're worried about NIST curves, there are people pushing
> brainpool and other curves on the TLS list.

Brainpool and/or djb's curves will take some time for adaption, too,
especially for secure implementations. Another reason to mention the
classic DHE alternative.

Ralph

-- 
Ralph Holz
I8 - Network Architectures and Services
Technische Universität München
http://www.net.in.tum.de/de/mitarbeiter/holz/
Phone +49.89.289.18043
PGP: A805 D19C E23E 6BBB E0C4  86DC 520E 0C83 69B0 03EF