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 Nov 18 '14 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$. – poncho Nov 18 '14 at 15:42
• @fgrieu: I meant $p$ to be a 2048-bit safe prime, I'll clarify the question. – xnyhps Nov 18 '14 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... – Ruggero Nov 18 '14 at 16:47
• @Ruggero Ah, stupid typo, it should've been $(p-1)/2$. – xnyhps Nov 18 '14 at 16:53

• 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}$. – CodesInChaos Feb 13 '15 at 7:48