4
$\begingroup$

As reusing a widely used group for Diffie-Hellman key exchanges might lead to far easier third-party key discovery through precomputation for that specific group, I would like to know what can possibly go wrong when generating custom groups for use as Diffie-Hellman parameters.

Here is what I currently believe to be true about the requirements. Please correct me or explain further if this is wrong or not detailed enough:

  • A field is needed for the Diffie-Hellman key exchange to work.
  • Rings without zero divisors are also integral domains. Integral domains that are finite are also fields. For some reason, a group with a prime modulus is also a finite ring without zero divisors and therefore a finite integral domain and therefore also a field.
  • To be hard to attack, the modulus needs to be large enough and one needs to be sure that the modulus is actually prime and not just pseudo prime.
$\endgroup$
  • $\begingroup$ I edited out the adjective "algebraic" from your question, as an algebraic group is something specific and not what you are talking about. The term "algebraic field" does not exist as far as I know. $\endgroup$ – fkraiem Feb 7 '16 at 23:19
4
$\begingroup$

One requirement that you don't have listed is that the generator $g$ needs to generate a subgroup that's of a large prime order; here's what can go wrong if that is not true:

  • If the order of $g$ (which we call $q$) has a factor $r$, then the attacker can, hearing $g^x$, determine $x \bmod r$ in $O(\sqrt{r})$ time. If $r$ isn't large, this immediately implies that you're leaking data

  • Worse yet, if the order $r$ is smooth (has no large factors), that makes the DLOG problem easy.

One strategy is, as mandragoe suggests, is look for a prime $p$ with $(p-1)/2$ prime as well. There is certainly a lot to like about this strategy; you can use (say) $g=2$, which can make the computation easier (and if the order of $g$ happens to be $2q$, all that means is that the attacker can learn the lsbit of your DH private values, which really doesn't tell him much, and you can avoid even that by making sure that $p \equiv 7 \pmod{8}$.

On the other hand, it is also a comparatively costly option, as looking for a value $p$ that meets both conditions means going through a lot of candidates. Now, if you're doing this computation only rarely (say, once a day), that's really not that big of a deal; however if you're coining a fresh group for every exchange, it is certainly more expensive that you need.

An alternative approach is:

  • Search for a 256 bit prime $q$

  • Once you have that, scan through 2048 bit values $kq+1$ for a prime; when you find it, call it $p$

  • For $g$, select an arbitrary value $x$ (2 works), and compute $x^k \bmod p$; if that value is not 1, use it for $g$.

The order of the generator $g$ will be $q$, which is a sufficiently large prime that we don't need to worry about attacks that take $O(\sqrt{q})$ time.

The expensive operation is the search for $p$, which is no more expensive than any other prime search for that size.

$\endgroup$
1
$\begingroup$

One consideration might be to generate a group so that the prime modulo p can be written in the form:

$$p = 2q +1$$

Where $q$ is prime. Since every subgroup of $Z_p$ has order $a$ such that $a|p-1$ the only possible subgroups of this group have order either 2 or $q$. Then you can use a generator for the subgroup of order $q$.

$\endgroup$
0
$\begingroup$

I would like to know what can possibly go wrong when generating custom groups for use as Diffie-Hellman parameters.

Aside from the mathematical issues that others have described, if you generate a parameter yourself, you need to convince the other party that you're exchanging keys with that the parameter that you have given them is actually a prime that meets those criterias, rather than some number that's specifically chosen to create a backdoor.

$\endgroup$
  • 1
    $\begingroup$ Do you really need to convince someone that you haven't deliberately introduced a backdoor? After all, if I am exchanging keys with you, I could easily post our shared keys on facebook, should I choose to. You can't check for that, hence you need to trust that I wouldn't. What I might need to prove is that I haven't accidentally introduced a backdoor, by selecting bad parameters... $\endgroup$ – poncho Feb 9 '16 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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