1
$\begingroup$

Is there a way to prevent the shared secret to be a small value (eg 4) to avoid easily succeeding brute force attacks?

In $g^a \bmod p$, I understand that choosing $p$ not a multiple of $g^a$ is a first step. But other than that, are there fast ways to achieve that goal?

Thanks

$\endgroup$
4
  • 1
    $\begingroup$ By the same reasoning, all possible shared secrets are insecure: What if an attacker simply guesses that $g^{ab}\bmod p$ lies in a certain "small" range and brute-forces that range? $\endgroup$
    – yyyyyyy
    Commented Jan 25, 2019 at 17:04
  • $\begingroup$ You are perfectly right $\endgroup$
    – Kroma
    Commented Jan 28, 2019 at 7:05
  • 1
    $\begingroup$ Note that excluding a certain range of values from potential secrets will reduce the entropy of the secret and hence make brute forcing easier. Values from the excluded range of values will not have to be tested. $\endgroup$
    – JimmyB
    Commented Jan 28, 2019 at 9:02
  • $\begingroup$ @JimmyB correct! $\endgroup$
    – Kroma
    Commented Jan 30, 2019 at 12:27

1 Answer 1

3
$\begingroup$
  1. $p$ is a prime number and $g^a\bmod p$ will fall between $[1, p-1]$, so $p$ will never be a multiple of $g^a \bmod p$ unless $g^a= 1\bmod p$.
  2. In Diffie Hellman, the secret exponents $a,b$ are chosen uniformly and randomly from $[1,q-1]$, where $q$ is a very large number. The probability that $Pr[g^{ab} = 4]$ or more generally $Pr[g^{ab} = x]$ for any $x$ in the group is negligible. This implies that for any integer $y=poly(n)$ where $n$ is the security parameter and $poly(\cdot)$ is any polynomial, $Pr[g^{ab} \le y]$ is negligible as well. So you don't need to worry about the key being a small value.
$\endgroup$
1
  • $\begingroup$ Ok thanks! Since we cannot do anything against a very lucky attacker, it will do! $\endgroup$
    – Kroma
    Commented Jan 25, 2019 at 12:58

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.