# Malicious DH groups

Can an attacker construct a DH group, large enough to be considered secure (say, a modulus of 2048-bits), such that the group appears safe, but the attacker is able to solve the DLP in the group easily?

A lot of applications of DH either use a well known modulus, such as from RFC 3526, or generate it themselves, but I'm specifically interested in a scenario where the attacker chooses the group.

One approach is to choose $p$ such that $p-1$ has many small prime factors and then to use a small-subgroup attack. But this can be protected against by requiring $p$ to be a safe prime (so requiring $(p-1)/2$ to also be prime). By "appears safe" I therefore mean that $p$ is a 2048-bit safe prime.

I know the Special Number Field Sieve can make factorization easier for numbers of the form $r^e ± s$ (with small $r$ and $s$). From "A kilobit special number field sieve factorization" by Lenstra et al., a 1039 bit SNFS factorization would take as much computational power as factoring a "normal" 700 bit RSA modulus, which is a lot easier, but not yet trivial.

This answer suggests it is possible to choose $p$, $q$ and $g$ such that the discrete logarithm problem becomes easy, but doesn't elaborate. How could that work? Is that avoided by using safe primes?

• It is not clear if you want $p$ to be a 2048-bit safe prime (meaning $q=(p-1)/2$ is 2047-bit prime); or $p$ to be prime with $p-1$ divisible by a much smaller prime $q$ of specified size, e.g. 256-bit. The two are exclusive. In either case, the question is interesting, and I can't answer. $\;$ Also, it might not be quite the same to be able to solve the DLP, and break some protocol that is no safer than the DLP is.
– fgrieu
Commented Nov 18, 2014 at 15:04
• I can give one partial negative answer: we can show that the values of $g$ of the same order are equivalent, as far as the DLOG and cDH problems; if you can solve either the DLOG or the cDH problems with respect to one $g$, you can solve it for any other $g$ of the same order (with at most a polynomial number of queries). Hence, if there is a way to find a malicious group, the magic is in selecting $p$ and $q$. Commented Nov 18, 2014 at 15:42
• @fgrieu: I meant $p$ to be a 2048-bit safe prime, I'll clarify the question. Commented Nov 18, 2014 at 16:09
• @xnyhps your edit is incorrect: $p$ and $p-1$ can't be both prime unless $p=3$. You want, for example, $q=(p-1)/2$ prime, although it is more common to choose a prime $q$ and then find a prime $p$ such that $p-1$ is a multiple of $q$. To my knowledge if the user checks that $p$ is prime, $q$ is prime, and that $g$ has order $q$, then there's no way to fool him. Maybe tricking the (probabilistic) prime checking functionality could be the way to go... Commented Nov 18, 2014 at 16:47
• @Ruggero Ah, stupid typo, it should've been $(p-1)/2$. Commented Nov 18, 2014 at 16:53

DLP and factorization are very different problems (which cryptocipher gurus consider of same complexity). You can't really compare the choice of using a safe prime p in order to prevent the factorization of n=p*q (recommended for RSA) with the choice of using a prime p where (p-1)/2 has a large factor (recommended for DSA).

Since you are interested with DH and a chosen modulus, one of the tricky recipe for mayhem and chaos is to chose a pseudoprime to the tests the victim might run (e.g a strong primality test base 2). There are ways to build pseudoprimes which pass Miller-Rabin tests for many, many bases.

But if the attacker can impose its own domain parameters to the victim, it probably is in a position of a man-in-the-middle, and does not need to go thru attacks based on weak groups.

• AFAIK Miller-Rabin rejects non primes with probability of at least 3/4, so after 40 passes even maliciously constructed prime candidates should only pass with probabiility <$2^{-80}$. Commented Feb 13, 2015 at 7:48
• @CodeInChaos Agreed. Rabin theorem is the probability that a random number declared as "probably prime" would be in fact a composite number with P < 1/4^k. Which differs from starting from a non-random provably composite which k Miller–Rabin primality tests would declare as "probably prime". Commented Feb 13, 2015 at 16:44