Logjam attack

[amirmc]

More details and link to papers via https://weakdh.org/

I'm curious whether #5 may have addressed any part of this.

[hannesm]

we accept (as client) any DH group of at least 512 bits in size, as server we use oakley_2 (from rfc2409 1024-bit group).

[hannesm]

512 has been lifted to 1024 in b77f39ffc3ef34546f9c26f21adb92424f7f02c1

[avsm]

Apparently some of the shipping Java libraries only support 768-bits, so there may be incompatibilities. Probably best to release note this rather than encourage interop with them though.

[hannesm]

good point. what I'm still struggling with is whether or not to use a different DH group.. and if so, which one? oakleyXX or ffdheXX? (dislike the suggestion to use a randomly generated one) 1024 bit seems to be at the lower limit atm.. @pqwy oakley15 maybe (in ffdhe 3072 bit is suggested for the future..)? https://weakdh.org/sysadmin.html dislikes oakley2

[pqwy]

So:

• The server never supported DHE_EXPORT and was not vulnerable.
• The client did support DH groups down to 512 bits, fixed by lifting the limit to 1024.
• The problem we now have is that it has been conjectured that certain government agencies might have invested on the order of $100,000,000 to gain a capability to decrypt traffic protected by a key exchange which used one of the very few published 1024-bit groups.

Everything that follows relates to the point 3, brought to you by your neighborhood conspiracy theorists:

The group we use for DH is Oakley 2, a historical 1024-bit group since standardized here and there. If someone did, in fact, undertake a massive computational effort to target common 1024-bit DH groups, Oakley 2 is about the first one to try. So in that case, we would be fully transparent to the afore-alluded-to agency and for this reason, we need to change the group.

Now there are two parameters that describe the security of a DH public key, g^a mod p:

• The modulus size drives the computational complexity of the general number field sieve as used in LogJam. log2(p) ~ 1024 is now thought to be "insanely hard, but possible".
• There is a number of attacks that take O (sqrt (min (a, k))), k being the largest factor of the order of the subgroup generated by g. (There is a related issue of an active attack exploiting the smallest order factor.) Therefore, for the coveted 120 bit security™, both a and k need to exceed 240 bits.

Contrary to the popular opinion, we know how to reliably generate good DH groups. We just need to control factorization of p - 1. A simple way to do that is to find two primes, p and q, such that 2q + 1 = p. In the context of DH, such p is called a safe prime and the related q is a Sophie Germain prime. As the group order divides p - 1, we can find a g with the order q. This is how both the Oakley and the proposed draft-ff-dhe groups were constructed, and is how nocrypto generates DH groups.

One line of reasoning is to keep on regenerating groups, each time incurring about $100,000,000 and about a year of work for the privilege of eavesdropping. Unfortunately, the time to do that, in modulus bits over runtime seconds, looks like this:

1024 bits takes about 13 seconds on average on my system, and we can't hide this computation inside TLS. We can't do that in the background either, as we want to remain single-thread-friendly. But group-hopping is certainly feasible as a part of a larger system that incorporates TLS and might be worth thinking about.

An alternative would be to pre-compute a number of 1024-bit groups, ship them in the code and select from them randomly, but this can add only so many orders of magnitude to the effort to break them all. I don't think that approach makes sense.

So I guess we have to increase the group size. Obvious, no?

Sadly, this choice has its performance cost (seconds):

... and we used to be at the far-left end. Going from 1024 to 2048 bumps the cost by a factor of about 6 on my new machine.

I think there is a wide agreement that given the asymptotics of generalized number field sieve, going over 2048 makes no sense. The LogJam paper recommends 2048 too. As far as we know now, the difficulty of attacking that is completely incommensurable with going after 1024.

There is a performance regression associated with this move, but it can be somewhat mitigated. I am pouring over Handbook of Applied Cryptography in hopes of finding a sane function giving equivalently-strong exponent lengths for various moduli sizes, and to complement the move to a larger group, we will start using much shorter exponents. Given some guesstimates of the size this will in fact accelerate computations, but only if the endpoint chooses to use this trick and clip the a to match the strength of the modulus. Naive clients talking to our server and using 2 < a < p-1 will have to take a speed hit.

A final question is which exact group to use. I was partial to one of the lower-order groups from RFC5114 because they were constructed to have exactly the required, reduced order, and need no guesses as to how much to shrink the space for a, but then it seems that they were pasted onto the internets out of the blue, no-one else takes them seriously, it is anyway impossible to use their structure on both endpoints as TLS does not communicate q, and their performance advantage can alternatively be gained as described above.

So I concur with the choice of ffdhe, but it should be the 2048-bit one.

As this exercise of picking another standard group really just lifts the bounds but repeats the same fundamental mistake of reusing the same group everyone else is using, it's worth thinking about making our own catalogue of groups at some point.

For now we should be bullet-proof with Dh.Group.ffdhe2048.

[pqwy]

P.S.

Obviously, this means dropping compatibility with some implementations, but compatibility undermining basic security is by now an old TLS trope. It makes all the sense ever to drop that bit of compat.

[hannesm]

thanks for your detailed analysis, explanation and performance measurements!

I agree. btw, as an update to the logjam paper, karthik mentioned that using 2048 bit ffdhe groups are good (and not proposing to generate custom 2048 bit groups) http://www.ietf.org/mail-archive/web/tls/current/msg16511.html

I updated #274 to use ffdhe 2048

[cfcs]

First, I agree with your ultimate decision to increment to a 2048-bit group as far as elliptic curves aren't available.

In regards to generation time, I'd like to add that the groups could be generated at compile-time, meaning that each compilation had its own (set of?) group(s). Doing so would avoid run-time costs of generating parameters, and would also avoid the issue of having a global set of ocaml-tls-specific groups to be broken by "higher powers".

[pqwy]

In tandem with the last group of changes to nocrypto, which constrain DH exponent size to not exceed the group strength (according to conservative guesstimates), we are now in a better shape than we were: a) no-one can negotiate us down; b) we offer far stronger parameters when acting as a server; and c) to sweeten the pot, our DH computations are now much faster.

I'm almost glad that LogJam happened.

:dancers:

[amirmc]

Is it appropriate to close this issue now? Seems like anything new would be a separate concern.

[pqwy]

I think so.

[hannesm]

there should still be a release done...