# Logjam: “composite order subgroups” explained for TLS developers and system admins?

I have read the recent logjam paper Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice.

On page 11 in the Recommendations section, they state:

Avoid fixed-prime groups In the medium term, employing negotiated Diffie-Hellman groups can help mitigate some of the damage caused by NFS-style precomputation for very common fixed groups. A current IETF draft  proposes a negotiated group extension to TLS. However, we note that it is possible to create trapdoored primes  that are computationally difficult to detect. At the very least, primes should be checked to be safe primes, or groups should use a verifiable generation process such as the one proposed in FIPS 186 , and the process for generating primes within the TLS session should be fixed so as to thwart the risk of trapdoors.

While this is lighter on the math than the section Attacks on Composite-Order Subgroups, I still don't know what that means in terms of implementations, algorithms, and libraries.

Further down that page they also state

A key lesson from this state of affairs is that cryptographers and creators of practical systems need to communicate better.

So, as a software guy working on a project which involves in-house implementations of TLS, I would love for a mathematician / cryptographer to explain to those us without group theory backgrounds (if possible) what is mean by "choosing safe primes", and choosing a generator $g$ which "generates a group with at least one sufficiently large subgroup order" (pp. 6, Attacks on Composite-Order Subgroups), and what that means for the code that I write, algorithms I implement, and libraries that I call. A layman's explanation, or pointers to group theory-related algorithms for generating DHE parameters would be great.

A safe prime is a prime number $p$ for which $(p-1)/2$ is also prime. The order of an element $g$ of the group $\mathbf{Z}^*_p$ (the integers modulo $p$, excluding 0) is the smallest integer $n$ such that $g^n\equiv 1\pmod{p}$; this is always a factor of $p-1$. The orders of the subgroups of the group generated by $g$ are the factors of the order of $g$; what's important for security is that at least one of the prime factors of the order of $g$ is large (for safe primes, if the order of $g$ isn't 1 or 2 then it has a prime factor of $(p-1)/2$, which is large). If you pick a prime that's not a safe prime, you need to make sure the order of $g$ is a multiple of at least one large prime; it's also important to try to make sure it's not a multiple of many small primes, and/or to pick a large exponent.

You can find good safe primes in RFC 3526. You could also generate your own; just try a lot of large odd numbers and check if both $p$ and $(p-1)/2$ are prime. You then pick $g$ such that $g^2\not\equiv 1\pmod{p}$, and you're good (since that means the order of $g$ is a multiple of $(p-1)/2$). With a safe prime, the worst that happens is that the last bit of your exponent leaks, which isn't a big deal with decent-sized exponents (so you don't even need to pick too big an exponent to be secure).

The following is more detailed background on why this is important. I tried to explain the math behind it in a way you could follow without prior background, but am not sure how well I did so.

## Group theory

Diffie-Hellman key exchange is done in a group, which is a set of elements and an operation that has a bunch of nice properties. In Diffie-Hellman, this group is the integers modulo a prime $p$, excluding any multiples of $p$ (so, the numbers between $1$ and $p-1$ are the elements of the group), with the operation being multiplication. A group has a set of elements associated with it; if there's a subset of those elements that is a group under the same operation, this is called a subgroup.

Diffie-Hellman more specifically happens in the subgroup generated by the generator $g$, meaning the smallest subgroup containing $g$. This subgroup consists of everything that can be written as $g\times g\times\cdots\times g$ (or $g^n$). The order of this subgroup (also called the order of $g$) is the number of elements in the subgroup, which is equal to the smallest $n$ where $g^n\equiv 1 \pmod{p}$ (once you get to 1, you start repeating yourself). The order of this subgroup is always a factor of the order of the main group (which for Diffie-Hellman is always $p-1$); this is true for all groups and subgroups.

Lastly, a number theory fact: If the order of $g$ is $r$, then $g^x\equiv g^y\pmod{p}$ if and only if $x\equiv y\pmod{r}$. This means that brute-forcing $e\equiv g^x$ just requires trying all values of $x$ between 0 and $r-1$.

## Composite orders

A composite order subgroup is what it sounds like: the order of the subgroup generated by $g$ is not a prime number. In this case, if you have $e=g^x\pmod{p}$ and are trying to find $x$, you can break the problem up into solving the discrete log problem on smaller subgroups.

Suppose, for instance, that the order of $g$ is 220. Then $e^{44}\equiv (g^x)^{44}\equiv (g^{44})^x\pmod{p}$. The order of $g^{44}$ is $220/44=5$ (because $(g^{44})^5=g^{220}\equiv 1$). So, any $y$ for which $(g^{44})^y\equiv e^{44}$ is congruent to $x$ modulo 5. We can solve the discrete log problem on this order-5 subgroup to find the remainder of $x$ modulo 5. Likewise, we can find $x$ mod 11 by solving discrete log on an order-11 subgroup. Because the order of $g$ is a multiple of $2^2$, we need to essentially solve two order-2 discrete log problems: the first to get $x$ mod 2, then using that we solve another one to get $x$ mod 4.

Once you have the value of $x$ modulo all powers of all prime factors of the order of $g$, the Chinese remainder theorem says that you have enough info to uniquely determine the value of $x$ modulo the product of those powers of primes (i.e. modulo the order of $g$). It's actually extremely quick to do so (this is incidentally also the basis of an attack on textbook RSA with multiple recipients, in which you get $m^e$ modulo a lot of different values and can compute the real $m^e$). So, instead of having to solve discrete log on a 220-element group, you solved it on an 11-element group, two 2-element groups, and a 5-element group.

Also, as the order of $g$ is a factor of the order of the group, factoring the order of the group (i.e. $p-1$) lets you attack any generator in that group. That means that an attacker can do work in advance that lets them attack any use of Diffie-Hellman with a given value of $p$.

## Mitigation

The solution to this is to make sure that one of the prime factors of the order of $g$ is very large; your strength is essentially the strength given by the size of the largest prime factor of the order of $g$, so you want to maximize that. The easiest way to do this is to pick a safe prime -- one for which $(p-1)/2$ is also prime. With a safe prime, the order of any element (which, remember, has to divide $p-1$) is either 1, 2, $(p-1)/2$, or $p-1$. It's easy to check that your generator doesn't have order $1$ or $2$, and if it doesn't then its order has a large prime factor ($(p-1)/2$).

If things aren't safe primes, you can still have secure choices of $g$ if you have a large prime factor in the order of $g$. However, all small factors of the order of $g$ leak some information about your exponent; if you have lots of small factors and pick a smallish exponent (which is normally perfectly fine), you can end up leaking lots of information about your exponent. Safe primes mean there's at most one small factor of the order of $g$, so you don't leak much information without having to try lots of possible values of $g$ to get one without many small factors or with a large factor.

• The reason it has the long math thing is that I wrote that up first, then reread the question, but I wasn't about to just delete the math explanation because I'd spent too long on it. The part before the horizontal line is the practical stuff. – cpast May 22 '15 at 3:40
• Thank you @cpast. I know we shouldn't comment to say thanks, but this explanation is excellent. It covers the answer, as well as giving the necessary background info. An upvote is not enough. – yegeniy Dec 20 '16 at 2:07