For Diffie-Hellman key exchange method, what are examples of very poor a and b values?

Question

For Diffie-Hellman key exchange method, what are examples of very poor $a$ and $b$ values? Given that $g$ and $p$ values are both large prime number and the formula is

$$g^{a . b} \bmod p$$

Answer 1

In Diffie-Hellman key exchange, the values of the secret exponent like $a$ (or equivalently $b$) must be generated in a way such that from $g$, $p$, and $g^a\bmod p$ (which will get public), it can not be found $a'$ with $g^{a'}\equiv g^a\pmod p$, or equivalently $a'\equiv a\pmod q$ where $q$ is the order of $g$. This condition is necessary, because guessing $a'$ is as good as guessing $a$, and breaks the DH protocol.

This condition implies that some ways to generate $a$ are bad. In particular, any value of $a$ known or guessable by the adversary is bad, including small values of $a$.

As an illustration of the above, and that choosing $a$ randomly in a large set is not good enough, it would be bad to generate $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$: in this setup, DH could be attacked with algorithms requiring only $\sqrt{2^{80}}=2^{40}$ effort (including a simple variant of baby-step giant-step, now detailed in the last section).

Also, if it happened that the order $q_a$ of $g^a\bmod p$ was small (which is possible if the order $q$ of $g$ has small divisors), DH would be vulnerable; for example, to computing ${(g^a)}^j\bmod p$ for increasing values of $j$, allowing a guess of ${(g^a)}^b\bmod p$, as soon as $j\equiv b\bmod q_a$. Thus for maximum safety, $a$ should be such that the order $q_a$ of $g^a\bmod p$ is large. This explains why $q$ is often chosen to be a large prime: $0<a<q$ then insures $\gcd(a,q)=1$ and that $q_a$ is $q$ (thus large) without any explicit check.

---

Assume that the order of $g$ is a large prime $q$; perhaps $q=(p-1)/2$, or some other large prime dividing $p-1$, with $q>2^{2k}$ for $k$-bit security. It is then safe to generate $a$ uniformly randomly in range $[1\dots q[$. That criteria is used in the weakest form of the Diffie-Hellman assumption (thus the safest, and common).

It is demonstrably very nearly as safe to allow $a=0$, or/and generate $a$ uniformly randomly in range $[1\dots p[$ (which is also common and safe if the order of $g$ is $p-1$ with $(p-1)/2$ a large prime, rather than $g$ of prime order).

Another common method is generating $a$ as a string of at least $2k$ random bits; that's relying on a stronger form of the Diffie-Hellman assumption (thus less demonstrably safe, but still conjecturally safe).

---

Following (now gone) comments, here is how a choice of $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$ (where $q$ is the order of $g$) could be attacked, with $\sqrt{2^{80}}=2^{40}$ work (essentially that many pairs of modular multiplications modulo $p$, and searches in a huge table):

• Giant steps: tabulate $g^a\cdot{(g^{-(2^{40})})}^i\bmod p$ for all $i$ with $0\le i<2^{40}$, requiring about $2^{40}$ modular multiplications and comparatively negligible extra work.
• Baby steps: for $j$ increasing from $0$, compute $g^j\bmod p$ and search it in the previous table until it is found; that will happen precisely for $j=r_{80}\bmod 2^{40}$, and the match will be with the value tabulated for $i=\lfloor r_{80}/2^{40}\rfloor$ (the proof uses that $g^q\bmod p=1$); it thus requires at most $2^{40}$ modular multiplications and searches.
• We thus know $r_{80}=i\cdot2^{40}+j$. This is enough to compute $g^{a\cdot b}\bmod p$ as ${(g^b)}^{r_{80}}\bmod p$ and break DH.

Techniques exist to considerably reduce the amount of memory needed.

Note: $r_{256}$ is there as an (admittedly artificial) way to make the set of allowable $a$ large, but brings no actual security; the constant 256 is entirely arbitrary.

Answer 2

Typically $g$ is not a large prime number. Often, it's something like $2$, or $5$.

Anyway, two bad choices:

For $a = 1$, you get $A = (g^1 \mod p) = g$. This is makes it trivial for someone to guess $a$, given $A$.

For $a = p - 1$, you get $A = (g^{p - 1} \mod p) = 1$, due to Fermat's little theorem. Again, guessing $a$ becomes trivial.

Obviously $a = 0$ is also a terrible choice, but this is not allowed by the protocol, as $a$ needs to satisfy $1 \leq a < p$.

Answer 3

There are two possible weaknesses:

• Choosing $a,b$ not uniform random from the entire domain. If the values are predictable, and thus the assumption not met, then all security guarantees are off. Note: Small values in general (with $1$ just being the smallest) could be found easily. And with very little precomputation you can detect values like $2g,3g,...$ just as easily as $g$ itself. But you should not exclude them explicitly, because you actually just decrease the domain for valid values. Let this be handled by just making sure you choose $a$ and $b$ uniform random.
• If $p-1$ has a lot of small, known factors, then you should try to avoid values for $a$, such that $g^a$ falls into a small subgroup (analog for $b$). The reason is, that regardless of the choice of the other exponent, $g^{ab} = (g^{a})^b = (g^{b})^a$ is also in that small subgroup. This could be avoided by only admitting values for $a,b$, which are coprime to $p-1$. But more commonly, you would choose $p$ to be a a safe prime or work in a Schnorr group.

Answer 4

$g^a \bmod p = 1=A$, or $g^b \bmod p=1=B$ are both likely to indicate a MITM, since $$g^c \bmod p=1 \implies g^{a.c.b}=(g^c)^{ab}=1^{ab}=1=s$$

or on the other hand$$g^{Super.Big.Number} \bmod p=g^{2} \implies (g^{Super.Big.Number})^b=g^{2b}=B^2=s$$ so storing a table of $\{g^n,n\}|n=1..x$ for some $x$ that fits your storage space would allow you to find $B^x=s$ quickly by looking up the table entry $\{g^a=A,a\}$ and then calculate $B^a=s$, the same would hold if $1..x$ were not just a straight sequence but a set of easily guessables as previously mentioned.

Note: this answer does not take into account:

 g = h^{(p-1)/q} mod p, where
 h is any integer with 1 < h < p-1 such that h{(p-1)/q} mod p > 1
   (g has order q mod p; i.e. g^q mod p = 1 if g!=1)
 j a large integer such that p=qj + 1

from RFC-2631 Section 2.1.1 nor section 2.2 which is another good reason why you shouldn't roll your own encryption, and probably use the nothing-up-my-sleeve-numbers for $g$ and $p$ from a reputable source such as RFC-3526

Answer 5

I'm completely guessing here, but following bkjvbx's answer, it seems that if you take a,b such that:

• a * b = p - 1 (since all non-prime numbers can be written as factors of prime numbers), we fall into the second case of bkjvbx

• a * b = 1 (i.e. a & b are inverses) we fall into the first case.