Subject: [TLS] New Algorithm identifier for EDH > 1024 bits?

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 26 Sep 2013 10:15:02 -0400

My understanding of the 1024 bit Ephemeral DH key issue is that it is not
currently possible to use longer keys because a certain number of deployed
Web servers will abort the connection if a client presents a longer key.

Hmmm, wonder who made that decision...

Regardless, this is not a problem that will solve itself. Even if
presenting a longer key will cause a connection to abort in 0.1% of cases,
browsers are not going to make the attempt. So if nothing is done the
legacy servers will prevent use of longer DH keys for the next 20+ years.

I don't think a TLS version number upgrade is the solution either. It is
just a bad idea for an algorithm suite identifier to mean one thing in TLS
1.2 and another in TLS 1.3.

The simple solution to this problem in my view is to specify a new
algorithm suite identifier for DH larger than 1024 and use that in
parallel. That might get us to a point where 25% of Web Servers are using
very strong EDH within 12-24 months.

-- 
Website: http://hallambaker.com/

---

From: Wan-Teh Chang <[email-masked]>
Date: Thu, 26 Sep 2013 07:51:43 -0700

> Web servers will abort the connection if a client presents a longer key.

The size of ephemeral DH keys is specified by the server, and the
client must present a key of that size. (This doesn't change the
problem though.)

The client needs a way to negotiate the ephemeral DH key size (or the
DH domain parameters) with the server. This can be done by either an
extension (similar to the elliptic_curves extension of RFC 4492 for
ephemeral ECDH keys) or new cipher suites.

Wan-Teh Chang

> Regardless, this is not a problem that will solve itself. Even if presenting
> a longer key will cause a connection to abort in 0.1% of cases, browsers are
> not going to make the attempt. So if nothing is done the legacy servers will
> prevent use of longer DH keys for the next 20+ years.
>
> The simple solution to this problem in my view is to specify a new algorithm
> suite identifier for DH larger than 1024 and use that in parallel. That
> might get us to a point where 25% of Web Servers are using very strong EDH
> within 12-24 months.
>
>
> --
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: "Yngve N. Pettersen" <[email-masked]>
Date: Thu, 26 Sep 2013 17:00:40 +0200

Hi,

> ephemeral ECDH keys) or new cipher suites.

In my opinion the length of the DHE key should have at least the same  
length (number of bits) as the signing RSA key. And similar for ECDHE, if  
necessary.

Thus, no need to negotiate a length, or incur any delays caused by having  
to generate a new key to match the length requested by the client, or any  
performance problems caused by a client asking for a very long DHE key.

Unfortunately, based on what I have seen, it seems like the DHE keysizes  
are hardcoded in many cases.

>> presenting
>> algorithm

-- 
Sincerely,
Yngve N. Pettersen

Using Opera's mail client: http://www.opera.com/mail/

---

From: Yaron Sheffer <[email-masked]>
Date: Thu, 26 Sep 2013 23:14:56 +0300

Yes, the problem is with clients not accepting the server's parameter 
choice.

I would prefer an extension to solve this problem, because:
- You can encode more information, e.g. the minimum AND maximum 
parameter sizes acceptable to the client.
- It is similar to RFC 4492.
- You avoid the cross-product problem of specifying large DHE versions 
for lots of cipher suites.

Thanks,
	Yaron

---

From: Yoav Nir <[email-masked]>
Date: Fri, 27 Sep 2013 13:48:26 +0000

On Sep 26, 2013, at 6:00 PM, Yngve N. Pettersen <[email-masked]> wrote:

> In my opinion the length of the DHE key should have at least the same length (number of bits) as the signing RSA key. And similar for ECDHE, if necessary.

Not for ECDHE_RSA, though. That would require that we define what ECDHE curve is equivalent to X-bit RSA.

In general I don't like us doing the NIST magic tables of naming equivalent strength key lengths among different algorithms, as in 1024-bit RSA is similar to some non-existing 80-bit perfect symmetric algorithm, and a 1024-bit MODP group is sort of like that.

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 27 Sep 2013 18:07:42 +0300

While we're opening (maybe) the negotiation of DHE, I'd like to clarify 
an issue that bothers me in the implementation of DHE in TLS:

With DHE, the premaster secret depends only on the DH shared secret. We 
know that DHE is commonly used with 1024-bit parameters. So even if you 
have a 2048-bit RSA certificate, the session strength will be 1024 bits.

What if we mixed *both* the DH secret and the regular encrypted nonce 
that's used in RSA ciphersuites into the premaster secret? Wouldn't we 
get forward secrecy, as well as crypto strength equivalent to the higher 
of the two lengths?

Thanks,
	Yaron

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 27 Sep 2013 08:21:54 -0700

> get forward secrecy, as well as crypto strength equivalent to the higher 

In DHE_RSA, RSA is used in signature mode to sign the DH parameters.
It is not recommended to use the same RSA key for both signing and
key encipherment.

Mike

---

From: [email-masked] (Martin Rex)
Date: Fri, 27 Sep 2013 17:34:39 +0200 (CEST)

> It is not recommended to use the same RSA key for both signing and

Isn't that (using the same RSA key for both signing and key encipherment)
what pretty much all TLS Servers do when they support both,
traditional RSA ciphersuites plus DHE_RSA and/or ECDHE_RSA?

-Martin

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 27 Sep 2013 11:40:42 -0400

> It is not recommended to use the same RSA key for both signing and

I hear this recommendation a lot, and I think it makes sense, but i'm
wondering if there is a "canonical" reference for it.  It seems to be
violated far more often than it is honored.

There are many RSA X.509 certificates in use on the web today that
indicate both "key encipherment" and "digital signatures" in their
X.509v3 "key usage" extensions.

Just picking a random example (not trying to name-and-shame, since this
practice is so widespread), the 2048-bit RSA end-entity key used on port
443 of geotrust.com is marked in its certificate both key usages, and is
used regardless of whether you negotiate a DHE cipher suite or a non-PFS
suite.

Do we need to address this as well, perhaps by encouraging server
operators to use distinct keys/certificates depending on whether the
negotiated cipher suite is PFS or not?

	--dkg

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 27 Sep 2013 09:04:56 -0700

> traditional RSA ciphersuites plus DHE_RSA and/or ECDHE_RSA?

I believe that many servers do use the same key for both, though
they don't have to.  This practice is likely due to cost (buy one
certificate instead of two) and software limitations.

Mike

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 27 Sep 2013 09:18:51 -0700

> violated far more often than it is honored.

One contemporary reference is Cryptography Engineering, page 201.

The recommendation is if you want to reuse N for both operations, then
choose different public exponents such as e=3 for signing and e=5 for
encryption.  I'm pretty sure you can't do this using the same X.509
certificate.

Mike

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 27 Sep 2013 09:19:03 -0700

Mike

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 27 Sep 2013 12:41:52 -0400

> encryption.  I'm pretty sure you can't do this using the same X.509

Right, you can't do that with the same X.509 certificate because the
subjectPublicKeyInfo (SPKI) data for RSA keys includes both N and E, and
is covered by the certificate's signature.

So: is this common practice something we should be pushing back on (e.g.
encouraging implementors to provide mechanisms to use separate keys and
certs for the PFS suites, and administrators to adopt those mechanisms)?

	--dkg

---

From: Hanno Böck <[email-masked]>
Date: Fri, 27 Sep 2013 18:55:35 +0200

On Fri, 27 Sep 2013 18:07:42 +0300
Yaron Sheffer <[email-masked]> wrote:

> While we're opening (maybe) the negotiation of DHE, I'd like to
> clarify an issue that bothers me in the implementation of DHE in TLS:
> 
> With DHE, the premaster secret depends only on the DH shared secret.
> We know that DHE is commonly used with 1024-bit parameters. So even
> if you have a 2048-bit RSA certificate, the session strength will be
> 1024 bits.
> 
> that's used in RSA ciphersuites into the premaster secret? Wouldn't
> we get forward secrecy, as well as crypto strength equivalent to the
> higher of the two lengths?

I feel this would add even more confusion.

What you'd get:
- Connection Security of the RSA key size, BUT
- Forward Secrecy only with the security of the DHE modulus size

Or to be concrete: an attacker able to steal the certificate's key
AFTER recording a connection and at the same time being able to break
the DHE would still be able to decrypt.

I don't really get why that should make any sense. Okay, it would avoid
that DHE "downgrades" the security of the RSA key.
But: This would require changes to the protocol. Won't work with
existing software, so it won't solve the mess we have today.

If you are already changing the protocol, you can also do something
that makes much more sense: Forbid DHE modulus size smaller than RSA
key size. (which also could be achieved just by server policy without
protocol changes, but then breaks messy clients like java - see past
discussion)

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

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

---

From: Hanno Böck <[email-masked]>
Date: Fri, 27 Sep 2013 18:59:31 +0200

On Fri, 27 Sep 2013 12:41:52 -0400
Daniel Kahn Gillmor <[email-masked]> wrote:

> subjectPublicKeyInfo (SPKI) data for RSA keys includes both N and E,
> and is covered by the certificate's signature.
> 
> So: is this common practice something we should be pushing back on
> (e.g. encouraging implementors to provide mechanisms to use separate
> keys and certs for the PFS suites, and administrators to adopt those
> mechanisms)?

PFS should be default and non-PFS should be phased out. Problem solved.

(Another reference for this principle "one key one usage" is by the way
an old paper by Schneier with the title "Chosen Protocol attack":
https://www.schneier.com/paper-chosen-protocol.html
)

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

---

From: Yaron Sheffer <[email-masked]>
Date: Sat, 28 Sep 2013 00:00:14 +0300

> protocol changes, but then breaks messy clients like java - see past
Hi Hanno,

Just a few weeks ago we as a community thought the server's private key 
was generally secure. Now the entire community seems to assume the 
private key is easy to steal. Practically, most private keys will 
probably not be stolen. OTOH the NSA (and also much smaller 
organizations) will have a pile of DH-1024 encrypted traffic for years 
to come just waiting for compute power to enable decryption en masse.

I'm sure you're not seriously suggesting that if I have a 3072-bit RSA 
cert, but my crypto library can only do 2048-bit DH, then I should never 
do DHE, and instead fall back to simple RSA, are you? Looking forward, 
there will always be mismatches and we should prefer the best possible 
TLS "mix", rather than enforce an idealistic policy.

Thanks,
	Yaron

---

From: Yoav Nir <[email-masked]>
Date: Fri, 27 Sep 2013 21:24:44 +0000

On Sep 28, 2013, at 12:00 AM, Yaron Sheffer <[email-masked]> wrote:
> 
> Hi Hanno,
> 
> Just a few weeks ago we as a community thought the server's private key was generally secure.

Did we? Private keys are just files on a web server. Sometimes they leak ([1])

> Now the entire community seems to assume the private key is easy to steal.

Easy or hard depends on the practices of the web server administrators. I personally (and maybe others feel the same) think it's easier than factoring a 2048-bit number (or even factoring a 1024-bit number, or calculating a discrete logarithm in a 1024-bit MODP group). I understand it's problematic comparing unlike things, like what's easier: peace in the middle east or a manned flight to Mars? But when assessing risks to your website, you do have to figure out where to invest your resources.

> Practically, most private keys will probably not be stolen. OTOH the NSA (and also much smaller organizations) will have a pile of DH-1024 encrypted traffic for years to come just waiting for compute power to enable decryption en masse.

The longer they wait, the less valuable decrypting them becomes. And storing that pile costs them. Also, what do you mean by "en masse". If the entire traffic on the Internet was encrypted with DES (broken by civilians over 18 years ago), could the NSA afford to decrypt it all today?

> I'm sure you're not seriously suggesting that if I have a 3072-bit RSA cert, but my crypto library can only do 2048-bit DH, then I should never do DHE, and instead fall back to simple RSA, are you? Looking forward, there will always be mismatches and we should prefer the best possible TLS "mix", rather than enforce an idealistic policy.

That I agree with, but rather than optimizing mixes, I prefer to think of it as a minimum level for each primitive, and mandating at least that. An RSA ciphersuite has zero bits for PFS. Obviously, 1024-bit DH is better than zero bits (80 bits according to NIST estimates). If for various legal, commercial and BC reasons we can't mandate the 112 bits of 2048-bit DH or the 128 bits of ECDHE with the P-256 or equivalent brainpool curve or some other curve, then we should set the minimum level for now at 1024-bit DHE.

Yoav

[1] http://www.net-security.org/secworld.php?id=11144

---

From: Michael StJohns <[email-masked]>
Date: Sun, 29 Sep 2013 13:20:53 -0400

On 9/27/2013 5:00 PM, Yaron Sheffer wrote:
>
> Just a few weeks ago we as a community thought the server's private 
> key was generally secure. Now the entire community seems to assume the 
> private key is easy to steal.

If the server private key isn't inside an HSM (hardware security module) 
of some sort, normal attacks on the server will make it possible to 
steal the key.  Even if encrypted at rest, to be used the key must be 
decrypted and moved to memory at some point.  Anyone who thought 
datafile based server private keys were unconditionally or even 
marginally secure probably hadn't thought it through.

If the server private key IS inside an HSM, the current way session keys 
are derived from the session master key makes it possible for an 
attacker to steal those keys unless the entire TLS negotiation and 
packet processing takes place inside an HSM specifically designed for 
that version of TLS.
> Practically, most private keys will probably not be stolen. 

With respect to whether a key will be stolen or not, you really need 
only compare the value of the data being protected by that key to the 
cost to an attacker to retrieve that key (and the data).  If the value 
of the data is >> or >>> than the cost to attack, chances are someone 
has done so.

HSMs increase the cost of attack and that's a good reason to use them, 
but you still need to consider the relationship of the expected cost to 
attack to the value of the data being protected and adjust your 
protections if the value of the data - to the attacker - exceeds the 
attackers cost of attack.

Mike

---

From: [email-masked] (Martin Rex)
Date: Mon, 30 Sep 2013 20:00:07 +0200 (CEST)

> of the data is >> or >>> than the cost to attack, chances are someone 

If someone if after the data, then it will go after the data,
not after the keys.  

> HSMs increase the cost of attack and that's a good reason to use them, 

For the vast majority of useful attacks it is entirely irrelevant
whether your keys are in a HSM or not.

First of all, HSMs will always and significantly increase the cost
of setting up and running a TLS peer by a significant amount, and
in particular, for a server, when performance is an issue.
HSMs also do not scale with multi-core CPUs; instead, you got to pay
factors more for a faster HSM.

With existing TLS, your HSM would have to implement current TLS versions
in its entirety, which most of the current HSMs probably do not.  And
interop with current TLS is likely going to be necessary for another
two decades (SSLv3 is 18 years old and we only recently managed to put
SSLv2 to rest (on paper, that is)).

Even when you have your keys in a HSM, this will not prevent that a
subverted server could look at incoming connections and perform
TLS-protected communication with a purely software-based TLS protocol
and software-based keys with the attacker.  In many situations,
the value is primarily in the data of the server, i.e. access to
data the server is processing or has on persistent storage.

Listening into communication and determining which client does what
might be interesting for collection by spooks (NSA, GCQH, etc.)
for performing data mining on the bigger picture, but is pretty
irrelevant for the average malfeasant attacker.

Being able to impersonate users might be *MUCH* more interesting
to attackers than being able to listen into boring communication,
e.g. obtaining credentials for users by various means, such as
pulling them from the data persistence, modifying access control lists,
capturing credentials of a disclosing authentication within the server
(rather than trying to sniff and decrypt them from the network),
setting/overwriting user credentials, creating new admin users,
adding X.509 trust anchors for acceptable TLS client certs and
probably lots of other things that are more powerful and more
devastating than obtaining the server's boring private key.

-Martin