Subject: [TLS] Short Ephermal Diffie-Hellman keys

From: "Yngve N. Pettersen (Developer Opera Software ASA)" <[email-masked]>
Date: Mon, 14 May 2007 09:41:59 +0200

Hello all,

I have recently started to see an increasing number of reports about  
SSL/TLS servers using short Ephermal Diffie-Hellman keys, in some cases  
very short ones.

Opera's SSL/TLS client will display warnings to users if the server is  
using RSA/DH/DSA keys shorter than (currently) 900 bits. All keys used in  
the chain, including the CA certificates are included in this evaluation,  
as well as the ephermal key, if the server selects a cipher with an  
ephermal key.

The short DHE keys I have seen have usually been 512 bits, but I have seen  
servers sending keys as short as 256 bits.

I have seen these keys on both normal webservers and mail servers, but I  
have an impression that there are more reports about the mail servers.

I think it might be an idea for TLS specification to include  
recommendations about how such keys should be selected.

My preference for such a recommendation is that the ephermal key should be  
as long, or as strong, as the key used to sign the ephermal key. I don't  
think the specification should mention specific keylengths, because what  
is secure is likely to change over time.

Comments?

As far as Opera is concerned, I am considering a few options, including  
automatically disabling the ephermal ciphersuites or re-sorting the cipher  
suite list toplace them last, and renegotiate the connection.

-- 
Sincerely,
Yngve N. Pettersen
 
********************************************************************
Senior Developer                     Email: [email-masked]
Opera Software ASA                   http://www.opera.com/
Phone:  +47 24 16 42 60              Fax:    +47 24 16 40 01
********************************************************************

_______________________________________________
TLS mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tls

---

From: Mike <[email-masked]>
Date: Mon, 14 May 2007 09:32:36 -0700

> The short DHE keys I have seen have usually been 512 bits, but I have 
> seen servers sending keys as short as 256 bits.

This is probably the result of an administrator not wanting to wait
the extra 30 seconds to generate a strong key.  If the server is
set up to generate a key on startup, it may not start listening for
connections until it has completed the task.

I recall (hopefully correctly) that a 1536 bit D-H key provides the
equivalent of about 90-120 bits of security.  I would guess that a
512-bit or 256-bit key is down in the EXPORT category of security.
This is a terrible trend.

Mike

---

From: Nelson B Bolyard <[email-masked]>
Date: Mon, 14 May 2007 11:46:58 -0700

Yngve N. Pettersen (Developer Opera Software ASA) wrote:
> using RSA/DH/DSA keys shorter than (currently) 900 bits. 

Do you mean the length of the public value?  or the length of the prime P?

Do you really wish to disallow public values that are low numeric values
even when the prime P is adequately large?

-- 
Nelson B

---

From: "Yngve N. Pettersen (Developer Opera Software ASA)" <[email-masked]>
Date: Mon, 14 May 2007 22:18:50 +0200

Hello Nelson,

> even when the prime P is adequately large?

The keysize used by Opera for DH keys is calculated using OpenSSL's  
DH_size function, which returns the number of bytes in the "P" element of  
the DH (dh_st) structure, which is then multiplied by 8 (so the real size  
may be 7 bits lower than stated; should probably use a more low level  
call). Background: EVP_PKEY_bits does not return anything about DH keys,  
which is why DH_size is used.

-- 
Sincerely,
Yngve N. Pettersen

---

From: <[email-masked]>
Date: Tue, 15 May 2007 10:15:20 +0300

Mike wrote:

> This is probably the result of an administrator not wanting to
> wait the extra 30 seconds to generate a strong key.  If the
> server is set up to generate a key on startup, it may not start
> listening for connections until it has completed the task.

Generating a 1024-bit DH key on a modern PC takes less 
than 30 _milli_seconds, so I doubt this is the real reason 
(unless the implementation is really, really stupid).

> I recall (hopefully correctly) that a 1536 bit D-H key provides
> the equivalent of about 90-120 bits of security.  I would guess
> that a 512-bit or 256-bit key is down in the EXPORT category of
> security.  This is a terrible trend.

RFC 3766 puts 1536 bit DH at around 90 bits. Factoring a 256-bit
number on a single PC takes only couple of hours, so if discrete
logs are approximately the same difficulty, 256-bit DH would
be even less secure than the old EXPORT ciphersuites.

Best regards,
Pasi

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 15 May 2007 13:11:32 +0100

> (unless the implementation is really, really stupid).

The 30 seconds reference should be for DH _parameter_ generation (which
some servers perform on start up) rather than key generation.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 15 May 2007 14:58:01 +0200

> some servers perform on start up) rather than key generation.

Furthermore, getting the entropy needed to generate DH parameters can be
the bottleneck, especially on servers that also consume entropy for
incoming connections.

Some applications that use GnuTLS (I believe Exim is an example) have a
separate script invoked once every day (or similar) to re-generate the
DH parameters.  This approach works fine even if getting the entropy is
a bottle-neck, since it allows servers to continue to run using the
earlier DH parameters until the new parameters have been generated.

/Simon

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 15 May 2007 15:08:04 +0200

> even when the prime P is adequately large?

While this really is about the prime P and not the public value, it
wouldn't be wrong to disallow small public values.  In practice the
public value won't be too much shorter than the public value unless
something weird (and presumably insecure) is going on.

It's only shorter secret values (DH exponents) that can be used in a
secure way.  But then the client coudn't easily reject these anyway.

Bodo

---

From: jimmy <[email-masked]>
Date: Tue, 15 May 2007 18:44:01 +0530

Bodo Moeller wrote:
[snip]
> public value won't be too much shorter than the public value unless

you meant 'public value won't be too much shorter than the prime' right?

> secure way.  But then the client coudn't easily reject these anyway.

-jb
-- 
The biggest problem with communication is the illusion that it has occurred.

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 15 May 2007 15:16:21 +0200

> you meant 'public value won't be too much shorter than the prime' right?

Oops -- er, yes!  Thanks for the correction.

---

From: <[email-masked]>
Date: Tue, 15 May 2007 16:50:13 +0300

Simon Josefsson wrote:

> Some applications that use GnuTLS (I believe Exim is an example)
> have a separate script invoked once every day (or similar) to
> re-generate the DH parameters.  This approach works fine even if
> getting the entropy is a bottle-neck, since it allows servers to
> continue to run using the earlier DH parameters until the new
> parameters have been generated.

BTW, why do you generate new DH parameters in the first place?

Earlier I suggested that TLS 1.2 spec should probably recommend just
hardcoding some of the groups from RFC 3526 (i.e., recommend against
generating DH parameters). This would simplify code and provide less
opportunities for getting things wrong (e.g. very small primes seen by
Yngve; small subgroup attacks; etc.).

http://www1.ietf.org/mail-archive/web/tls/current/msg01115.html

Best regards,
Pasi

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 15 May 2007 16:34:21 +0100

> secure way.  But then the client coudn't easily reject these anyway.

Speaking of which what do people think about including the sub prime
value (aka "q") as an optional value in DH parameters in a TLS 1.2
handshake?

Steve.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 15 May 2007 18:12:50 +0200

> BTW, why do you generate new DH parameters in the first place?

GnuTLS doesn't -- external applications, notably Exim, do it.  However,
I have not idea why they do it.  There are some discussion about this
behaviour in section 2.2.3 of:

http://pkg-exim4.alioth.debian.org/README/README.Debian.html#id224002

Frankly, I'm not sure I really understand what they are doing or why.

> http://www1.ietf.org/mail-archive/web/tls/current/msg01115.html

I think we would need solid support from the cryptographic community to
change this.

Regenerating new DH parameters appear to me, if they are computed
correctly, to potentially offer one additional wall of protection.

The risk is if the parameters are not computed correctly.  But that risk
have to be weighted against the risk of someone exploiting the fact that
many D-H exchanges on the Internet uses the same parameters, and does so
over a multi-year time period.

Personally, I'm leaning towards reviewing the code to generate D-H
parameters, and to recommend administrators to re-generate parameters
every X days.  Instead of putting all trust in one D-H parameter.

/Simon

---

From: Nelson B Bolyard <[email-masked]>
Date: Tue, 15 May 2007 09:44:11 -0700

> value (aka "q") as an optional value in DH parameters in a TLS 1.2

How does that help the recipient?  How does the recipient use that info?

Safe primes (where (P-1)/2 is also prime) are commonly used for DH primes.
Is sending Q helpful for such primes?

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 15 May 2007 22:27:26 +0200

>> value (aka "q") as an optional value in DH parameters in a TLS 1.2

Yes, this definitely should be done!

> How does that help the recipient?  How does the recipient use that info?

This would tell the recipient that it only needs to generate an
exponent in the  0 ... q-1  range.  The subgroup order  q  can be
much shorter than the modulus p, so this can save a lot of time
for the exponentiation.  Think of DSA-style parameters (actually
Schnorr-style, reused for DSA) where p has 2048 bits, say, and the
matching size of q is just 224 bits.

Currently such parameters can be used to make the server side
run faster for ephemeral-DH TLS ciphersuites, but the client side
cannot benefit from them.  With q included in the ServerKeyExchange
message, the client side can benefit from short q too.

> Is sending Q helpful for such primes?

It doesn't really help for such primes regarding the optimization
mentioned above.  So I guess when using safe primes, it would be
reasonable to simply omit q if it is introduced into the
ServerKeyExchange message as optional information.

The client *might* use the information that p is a safe prime, though.
(This is implied by seeing that the length of q is just one less than
the length of p, both counted in bits, assuming that the specification
requires q to actually be a prime.)  The scenario where this would be
relevant is arguably somewhat to bizarre to explain, though.

Bodo

---

From: Russ Housley <[email-masked]>
Date: Tue, 15 May 2007 17:54:27 -0400

>Yes, this definitely should be done!

RFC 2412 does not seem use "q" this way.  Does anyone every use 
Oakley groups with TLS?  If so, then you probably need some more 
general way to indicate the size of the subgroup.

Russ

---

From: Bodo Moeller <[email-masked]>
Date: Wed, 16 May 2007 00:43:51 +0200

> general way to indicate the size of the subgroup.

For the Oakley well-known groups, the generator actually is a
generator of a prime-order subgroup, so specifying a 'q' value is no
problem.  (It doesn't help much in this case, though, since 'q' is
just one bit shorter than 'p'.)

In general, Oakley-style group specifications include a "group order
largest prime factor" field, which is pretty useless for
implementations.  It only helps to estimate the security that
can be obtained using such a group when doing Diffie-Hellman
*properly*, which is something for which you *don't* need this piece
of information (and for which you shouldn't rely too much on
Appendix D of RFC 2412).  What you do need for implementations is the
group order, and (if you want to use the short-exponent trick
suggested in RFC 2412 App. D) information on whether the group order
is prime (which is *not* part of Oakley-style group specifications).

I'd suggest stating in the TLS specification that 'q' can only be
included in the ServerKeyExchange message for the case of prime-order
subgroups.  These are what you'd usually use, except sometimes if the
DH subgroup is nearly as large as 'p', which is a case where knowing
'q' doesn't provide significant benefits anyhow.

Bodo

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 16 May 2007 15:49:51 +1200

Dr Stephen Henson <[email-masked]> writes:

>Speaking of which what do people think about including the sub prime value
>(aka "q") as an optional value in DH parameters in a TLS 1.2 handshake?

It's a good idea, I've been wanting that for awhile (SSH should be doing this
as well).

Peter.

---

From: <[email-masked]>
Date: Wed, 16 May 2007 11:04:09 +0300

Simon Josefsson wrote:

> > opportunities for getting things wrong (e.g. very small 
> > primes seen by Yngve; small subgroup attacks; etc.).
> >
> I think we would need solid support from the cryptographic 
> community to change this.

Current TLS specs already allow implementations to do this; also 
many existing protocols (IKE/IKEv2, MIKEY, HIP) do this. So I don't 
think that this is very controversial (especially if we keep this
as a recommendation, not a MUST).

(BTW, even with TLS, I think FIPS/Suite B compliance would prohibit
generating new DH parameters in the ECDH case.)

> The risk is if the parameters are not computed correctly.  But that
> risk have to be weighted against the risk of someone exploiting the
> fact that many D-H exchanges on the Internet uses the same
> parameters, and does so over a multi-year time period.

IKE has done exactly this over a multi-year time period, and I haven't
heard of any concerns over that...

Best regards,
Pasi