# How well does breaking multiple DH key exchanges over the same group scale?

Suppose you are running a server with the Diffie-Hellman parameters (so the group G and generator g) generated once. There are many connections made to the server, all using TLS with an DHE cipher suite.

Now, assume an adversary captures all connections and is able to break one key exchange (find the master key). How much harder would it be for that adversary to break 2, 3, ... $n$ of the key exchanges instead?

Of course this will depend on the attack against DH that is used. In a naive brute force attack the adversary starts generating $g^0, g^1, g^2, \dots$ until they find either the exponent used by the server or the exponent used by the client.

Something like:

a := g
e := 1
while e < n:
a := a ∙ g in the group G
e := e + 1
if a == client_key or a == server_key:
return e


This contains one modular multiplication step (multiply previous value by $g$) and two comparisons. I would expect the comparisons to be very cheap compared to the multiplications, therefore doing this for 2 key exchanges instead of one should only have a small impact on the time required.

Does the same apply to other attacks on DH?

Background:

I think it's a common misconception that to compromise $n$ connections without forward-secrecy, an adversary only needs to break one key and with forward-secrecy and attacker would need to break $n$ keys, and therefore would need to spend $n$ times as much resources to do so. Forward-secrecy only implies that adversaries can't “cheat” the math by stealing the key, it doesn't necessarily mean that breaking multiple key exchanges is more difficult than breaking one.

-

The simplest index-calculus attack on discrete logarithms is the following. You have a generator $g$, a target $y$ and a bunch of small primes $\ell_1, \dots, \ell_k$. The computation proceeds in three phases.

First generate lots of relations of the form $$g^{r_i} = \prod_j \ell_j^{s_{ij}}.$$

These relations give you a set of linear equations in $r_i$, $s_{ij}$ and unknown $\log_g \ell_j$. Solve this system for the unknown $log_g \ell_j$.

Now find one relation of the form $$y g^u = \prod_j \ell_j^{v_j}.$$ From this, the logarithm of $y$ is easily recovered.

The third phase is much, much cheaper than the two first phases. Notice also that the two first phases do not involve $y$, so when you want to compute the logarithms of multiple elements, you only have to repeat the third phase.

I believe these essential characteristics are shared with the more advanced d.log.algorithms, so the cost of computing $n$ logarithms is not $n$ times the cost of computing one logarithm, but merely somewhat larger than computing one logarithm.

Typically, our goal is to make it impossible to compute even one logarithm, so this does not have to be a reason for using different groups. There are good reasons for everyone to use the same group. For prime finite fields, you can use carefully chosen primes that make arithmetic fast and/or secure implementation easy. For elliptic curves, you can use carefully chosen primes and curves that make arithmetic fast and/or secure implementation easy. (Note that index calculus doesn't work for elliptic curves, but I think there are speedups for Pollard $\rho$ when computing multiple discrete logarithms.)

-
Could you give some pointers for the reasons to use the same group? (Aside from group generation being really slow.) –  xnyhps Dec 9 '13 at 15:39

This paper shows, assuming standard heuristics regarding the number-field sieve, that a “batch NFS” circuit of area $L^{1.181\dots+o(1)}$ factors $L^{0.5}+o(1)$ separate $B$-bit RSA keys in time $L^{1.022\dots+o(1)}$. Here $L = \exp((\log2^B)^{1/3}(\log\log2^B)^{2/3})$. The circuit’s area-time product (price-performance ratio) is just $L^{1.704\dots+o(1)}$ per key. For comparison, the best area-time product known for a single key is $L^{1.976\dots+o(1)}$.