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