Subject: [TLS] DH parameters, primality

From: Hanno Böck <[email-masked]>
Date: Fri, 7 Mar 2014 10:45:13 +0100

Hello,

Recently two issues brought DH parameters to my attention. First, it
was mentioned in the triple handshake issue that a server sending
malicious DH parameters could cause trouble. And second a crash in
chrome was detected when using it with very short DH parameters.

So I did some tests on that you might be interested in:
https://dh.tlsfun.de/

I wrote up a bit about my findings here:
http://blog.hboeck.de/archives/841-Diffie-Hellman-and-TLS-with-nonsense-parameters.html

tl;dr Probably not many people have tested these things in the past.
Using obviously wrong parameters could uncover other bugs. Some
browsers (and other tls clients) accept all kinds of bogus parameters
for DH. No browser checks for primality.

What conclusions to draw from all that for TLS?

First I would propse that all DH parameters below 1024 bit get
rejected. I don't see any valid reason for them. (I'd prefer to say
here that < 2048 bit should be rejected, but I'm aware that this is not
realistic for quite some time considering the implementations out
there).
I'd expect rejecting < 1024 bit exchanges to have very low impact, as
opera already doesn't like to connect to them.

The more difficult part is if primality should be tested in some way.
The finders of the triple handshake issue propose to define a number
of good primes. This is a good idea, but it doesn't solve the problem
for connections with existing implementations.
Currently, most DH exchanges are still 1024 bit. Primality tests for
them are feasible. However, for 2048 bit they're challenging and for
4096 probably not feasible at all (about 1 second on my core2).

Maybe it would be possible to run a miller rabin test with less rounds
and have a "high probability prime" and consider that good enough?

Another option would be to define some fixed "good" primes now and try
to get them out quickly. As currently DH exchanges with 2048/4096 bit
are rare, it could probably avoided that arbitrary primes get widely
deployed. Then browsers could test either if they see a known good
prime (fast) and if not test primality. The performance impact would
probably be acceptable if the event of getting a 2048/4096 prime is
rare.

Thoughts?

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

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

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 07 Mar 2014 13:27:23 +0100

> http://blog.hboeck.de/archives/841-Diffie-Hellman-and-TLS-with-nonsense-parameters.html

Note that the prime number along with the public key and the generator
are signed by the server in the ServerKeyExchange message. If we
disregard some previous problems found with that signature, the client
has no reason not to believe that the server sent a valid prime.

Nevertheless, even if you add a primality check there, there is no way
with the parameters that are provided by TLS to check whether the prime
is not of some special form that makes the DL problem easy. Moreover,
there is also no way to verify that g is an actual generator, and is not
an element with a small order (try sending one as g).

Thus no matter how many checks you add there, they will consume time,
and they will not be sufficient; in the end you'll have to rely on the
server signature and that's what current implementations do.

regards,
Nikos