0
$\begingroup$

How to calculate key size for Diffie-Hellman key exchange? The strength obviously depends on both generator and prime modulus.

Formula:

$$g^x\bmod p$$

Public values:

$$g=3$$

$$p=17$$

Alice:

$$x=15$$

$$3^{15}\bmod 17=6$$

Bob:

$$x=13$$

$$3^{13}\bmod 17=12$$

Alice:

$$12^{15}\bmod 17=10$$

Bob:

$$6^{13}\bmod 17=10$$

The original numbers $(3,17,13,15)$ weren't that (no way secure, but not that) low and they ended up with 10 which is much easier to brute force than guessing each part from $g^x\bmod p$.

$\endgroup$
12
  • 2
    $\begingroup$ The generator is actually fairly irrelevant for security as long as it's not a really dumb choice (for example $1$). $\endgroup$
    – SEJPM
    Oct 10, 2016 at 20:10
  • 2
    $\begingroup$ The exponent kinda matters in the sense that you need to make sure that it is unpredictable (so choices with less than 128-bit length / entropy are dangerous). $\endgroup$
    – SEJPM
    Oct 10, 2016 at 20:17
  • 1
    $\begingroup$ I've updated my answer according to your edit (but please don't make this a habit) and the TL;DR is: While brute-forcing the shared secret is easier here, it doesn't scale as well as other attacks. $\endgroup$
    – SEJPM
    Oct 10, 2016 at 20:56
  • 1
    $\begingroup$ 17 is no safe-prime (i.e. $\frac{p-1}{2}$ isn't prime). $\endgroup$ Oct 12, 2016 at 8:15
  • 1
    $\begingroup$ @SamuelShifterovich Using a safe-prime as modulus for Diffie-Hellman is standard practice and avoid some of the problems you're seeing. $\endgroup$ Oct 12, 2016 at 13:03

1 Answer 1

1
$\begingroup$

With Diffie-Hellman in its most general description, there are three different types of objects involved:

  • The group
  • The exponents
  • The generator

The group

Diffie-Hellman operates in a group. This group may be $\mathbb Z_p^*$ or may be the points on your favorite elliptic curve usually. Usually the group parameters are what needs to be adjusted over time the most due to computational advances and the advances in cryptanalysis of the discrete logarithm problem (DLP). So what you want is a group where the DLP is assumed to be hard and for this you need to adapt the group or change parameters (like the prime or curve parameters).*

The exponents

There isn't much to the exponents with diffie-hellman except that you want to avoid predictable exponents, because then the other party or an adversary could predict your exponent and calculate the shared secret from that.

The generator

The generator of the subgroup of the group is actually fairly irrelevant. You need to make sure it indeed generates a subgroup of appropriate size and that's about it, especially you should avoid the neutral element or other elements with small order.


*This is actually not true as you usually want the computational diffie-hellman (CDH) problem to be hard, but these two are very closely related most of the time such that there's no known way to break CDH without breaking DLP.


As for the "the shared secret is actually easier to brute-force than all other values". While this is true here, this doesn't scale.

Brute-force of the shared secret scales at $\mathcal O(q)$ (because the shared secret is a random element from the group, with $q$ being the order of said group).
The best generic attack on the discrete logarithm problem scales at $\mathcal O(\sqrt q)$ (there are more efficient ones for prime-moduli-groups).
Now chunk in some numbers. If you multiply $q$ by, let's say, 10,000 you get a workload increase of 10,000 for brute-force, but only 100 for the better attack. So brute-forcing the shared secret clearly isn't the way to go for real-life parameters.


If you're seeking for advice on which keylengths to choose and which parameter set corresponds to which security level, you can use Keylength.com for the TL;DR and read the Lenstra-Verheul paper (PDF) for all the details.

$\endgroup$
5
  • $\begingroup$ Your answer contains a lot of theory, but is there any "formula" for calculating the key size? $\endgroup$ Oct 11, 2016 at 19:32
  • $\begingroup$ @SamuelShifterovich For standard finite field math, this is fairly complex and else (for sub-groups or groups where GNFS doesn't apply) you can just half the bit length of the order to get the bit length of the equivalent symmetric key. $\endgroup$
    – SEJPM
    Oct 11, 2016 at 19:49
  • $\begingroup$ Bit length of which part of g^x \mod p? $\endgroup$ Oct 11, 2016 at 19:59
  • $\begingroup$ @SamuelShifterovich Here the bit length of the modulus is key. Pick that according to keylength.com or according to the Lenstra and Verheul paper (PDF) and you're good. $\endgroup$
    – SEJPM
    Oct 11, 2016 at 20:01
  • $\begingroup$ Thanks, could you just put this all-you-need-to-know information into the question so that I can accept? $\endgroup$ Oct 11, 2016 at 20:26

Your Answer

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

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