Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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