3
$\begingroup$

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$$

$\endgroup$
  • 2
    $\begingroup$ TL;DR: Any predictable value for either $a$ or $b$ is bad. $\endgroup$ – SEJPM Oct 10 '16 at 20:13
  • 3
    $\begingroup$ There are no bad values, only bad ways to generate them. $\endgroup$ – CodesInChaos Nov 12 '16 at 13:47
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The question has been "bumped to the homepage by Community"; so here is a formal answer. $\endgroup$ – fgrieu Jan 11 '17 at 8:32
  • $\begingroup$ Why someone to choose $a>q?$ $\endgroup$ – 111 Jan 11 '17 at 14:03
  • $\begingroup$ @111: it is safe, and not uncommon, to generate $a$ randomly in range $[0\dots p[$ (give or take a some at the extremities), and that can make $a>q$ common; e.g. when $2q+1=p$, with both the modulus $p$ and the order $q$ of $g$ primes. I've also seen $a>q$ when $a$ is generated as a bitstring, as in the end of the second section of the answer. $\endgroup$ – fgrieu Jan 11 '17 at 15:31
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ $0$ is not an element in the multiplicative group of integers modulo $p$. So $g^{0}$ isn't even defined. $\endgroup$ – user13741 Oct 12 '16 at 13:57
  • 1
    $\begingroup$ @user13741 I know. But most explanations of Diffie-Hellman neglect to explain the group theory background, which is why I included it just in case. $\endgroup$ – bkjvbx Oct 12 '16 at 16:43
1
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ The linked (and usual) definition of a Schnorr group does not preclude that $p−1$ has a lot of small, known factors. And would that really mater (and require checking that $a$ is coprime with $p-1$), as long as the order of $g$ is a large random prime (dividing $p-1$, obviously)? $\endgroup$ – fgrieu Jan 11 '17 at 8:57
  • $\begingroup$ @fgrieu You're right in the sense that for a Schnorr group $p-1$ also can have a lot of small factors. But you can't fall into a "small subgroup" by bad choice of $a$ or $b$ - because the generator is already of prime order $q$. $\endgroup$ – tylo Jan 16 '17 at 9:37
0
$\begingroup$

$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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are these poor values though? Sure, the resulting shared secret is a number directly related to the parameters, but I don't see how the attacker would learn anything useful. There's $p-1$ sets of $a,b$ that satisfy each relation, and the resulting $A$ and $B$ don't reveal anything, as far as I can tell. Additionally, this is impossible to prevent, since $a$ and $b$ are chosen independently and secretly by each party. $\endgroup$ – bkjvbx Oct 10 '16 at 19:42
  • $\begingroup$ You're right. Per se, I don't think these are dangerous values, but it's always preferable to tackle all edge cases. For example, an attacker has then 1/(p-1) chance that the resulting g^ab is equal to g and also 1/(p-1) chance that the resulting g^ab is equal to 1. The attacker can feed the symmetric encryption algorithm with those two values see if he can decrypt the payload (common case in ssl where aes is used with the key being the result of the DH exchange). Again, it's probably not worth checking, but at least for the sake of completeness, I've put it here .. :) $\endgroup$ – Nikkolasg Oct 10 '16 at 20:12
  • $\begingroup$ There are only $p-1$ possible values for $g^{ab}$, so the chance that $g^{ab}$ is equal to any value is $1/(p-1)$, given uniformly random $a,b$. $\endgroup$ – bkjvbx Oct 10 '16 at 20:19
  • $\begingroup$ 1: g^ab = g^1 = g occurs with 1/(p-1). 2: g^ab = g^p-1 = 1 occurs with 1/(p-1). So Pr[g^ab = g OR g^ab= 1] = 2/(p-1). So the attack has a (very very) small chance of decrypting the ciphertext if he tries the naive values 1 & g as the key to the symmetric encryption. $\endgroup$ – Nikkolasg Oct 10 '16 at 20:37
  • $\begingroup$ @Nikkolasg, if you forbid values of $a$ and $b$ such that $g^{ab} = g^1 = g$, then would the next obvious value for the attacker to try be something like $g^{ab} = g^2$ ? Should we forbid values that lead to that, too? $\endgroup$ – ilkkachu Oct 11 '16 at 19:54

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.