7
$\begingroup$

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?

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$
    – CodesInChaos
    Commented Feb 13, 2015 at 7:48
  • $\begingroup$ @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". $\endgroup$
    – Pierre
    Commented Feb 13, 2015 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.