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.

As I understand it, bruteforcing a Diffie-Hellman generated secret key takes $P-1$ attempts to crack the shared secret, where $P$ is a very large prime used for modulus. If your $P$ is quite large, which according to the wikipedia page ought to be about 300 digits, then theoretically your encrypted data is secure.

Now, let's assume user A and user B generate a new personal secret for every session they hold. If a log of all of those sessions was stored, with a total of $N$ sessions, then in theory, given that you do not change $P$ or $G$ (where $G$ is defined as the primitive root mod $P$), the number of attempts it takes to crack any arbitrary session's generated secret should be $\frac{P-1}{N}$.

My question is, is that a giant security risk if $P$ is very large and kept static across many sessions? How often should it be updated, if ever? I am aware it increases the probability of a bruteforce attack succeeding, but is the increase something I should consider trivial?

Theoretically if someone is performing a bruteforce on this scheme, if the attack is random then am I correct in assuming that updating my prime would do me no good?

share|improve this question
    
Also I'm new to this SE, forgive me if this question seems overtly obvious or if I've used the MathJaX excessively or improperly. –  Cyclone Oct 7 '13 at 4:39
2  
This answer also answers your question although it doesn't give a justification. –  rath Oct 7 '13 at 4:52
    
@rath It's good to know I'm pointed in the right direction by not changing, but I'd still like to see some justification for it beyond "It's a really big number anyway" –  Cyclone Oct 7 '13 at 4:56
1  
...and that's why your question didn't get marked as a duplicate :) –  rath Oct 7 '13 at 4:57
    
I'm not sure why 'it's a really big number' isn't a sufficient justification. Exercise: estimate plausible values of P and N; compute the expected number of attempts $\frac{P-1}{N}$; compare that to the plausible amount of computing power any attacker may be expected to have. Extra credit: compare the probability of success with, say, someone winning the lottery 10 times in a row... –  poncho Oct 7 '13 at 14:21
add comment

2 Answers 2

up vote 7 down vote accepted

How long are parameters used for?

Usually $g$ and $p$ are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago.

So the answer is basically decades.

The impossibility of brute force

Let's suppose that I as an attacker decide I'm going to compute $g^{x} \mod p$. I start at 1 and work up to $p-1$ and start logging them in a table.

There are two problems here. One is there is not enough matter in the universe to store the number of items in that table. The second is that there is not enough time between now and the heat death of the universe to generate it either.

This is a simple consequence of the size of the primes involved.

What about collisions?

Suppose you have access to PRISM and you can see every Diffe-Helman key exchange in the world. Suppose I log every exchanged value in the hope that one specific exchange is repeated.

You're going to need approximately the square root of $p$ invocations to get a probability of approximately 50% that the item already exits in the list. The square root of $p$ is still so big that there simply isn't enough time, energy or matter in the universe to make that attack work.

Even with that table, you still need both exchanged DH parameters to be in there, along with any ciphertext from both sessions, if you wish to have a shot at recovering the plain-text.

Worse, this doesn't even mention that a collision might not even help you. If the cipher used after the exchange uses an additional initialization vector or nonce input (and this one is not simply derived from the exchanged secret, i.e. likely different), then the fact that two sessions shared the same key doesn't help you.

It's important to note here that unlike the attack above where you knew each $x$ for every $g^{x}$, in this attack you still don't know the $x$. All you have is $g^x$. I sensed a bit of confusion on this point in your question.

How are these values actually attacked?

There are more efficient ways to solve the discrete logarithm problem. Wikipedia gives a nice overview of the problem and some algorithms that solve it.

The parameters we choose in cryptography are large enough so that solving the problem is infeasible in any reasonable amount of time.

share|improve this answer
    
AES-CTR is a stream cipher. (CTR is a mode of operation to create a stream cipher from a block cipher.) –  Paŭlo Ebermann Oct 7 '13 at 11:58
    
Thanks! I kinda goofed. What I meant is that the attack will only work where you're using a stream cipher where there's no nonce and just a key. I've updated the answer to just refer to a block cipher. If you feel a better edit could be made to clarify this, go ahead and make it. –  Simon Johnson Oct 7 '13 at 14:45
    
Okay, I changed this to mention the nonce/IV instead of stream cipher/block cipher. (There are stream ciphers with IVs, as well as block cipher modes which don't use IVs, and block cipher mode "misuses" with fixed IVs as well.) –  Paŭlo Ebermann Oct 7 '13 at 16:43
    
Thanks Paulo. The answer is definitely better for the changes. –  Simon Johnson Oct 7 '13 at 16:56
add comment

One way to address this question is to notice that if there was such a vulnerability in reusing $g$ and $P$ multiple times, then that vulnerability can be used to attack a specific exchange, even if they use $g$ and $P$ only that one time. That is, changing $g$ and $P$ cannot help matters.

Here is how this observation works; suppose we have a black box that, given $g$, $P$ and a large pile of values $g^{x_1}, g^{x_2}, g^{x_3}, ..., g^{x_N}$, has a nontrivial probability of giving us the values $i, x_i$ (for some $1 \le i \le N$); that is, it gives us a value that we can use to decrypt session $i$.

Then, if we want to attack a single session with a specific $g, P$ and a public key $g^x$, here is what we can do:

  • We select $N$ random values $r_1, r_2, ..., r_N$, all relatively prime to $P-1$

  • We compute the values ${(g^x)}^{r_1}, {(g^x)}^{r_2}, {(g^x)}^{r_3}..., {(g^x)}^{r_N}$

  • We submit that list (along with the values $P$, $g$) to our black box

The black box, with nontrivial probability, gives us a value $i$ and $y_i$ with $g^{y_i} = {(g^x)}^{r_i}$; that is, $y_i \equiv x r_i\ (\bmod\ P-1)$. We compute ${r_i}^{-1} \bmod P-1$, multiply both sides with it, which gives us the explicit value $x = {r_i}^{-1} y_i$ which is the secret exponent we need to read the one session we are interested in.

So, does this reasoning mean that we shouldn't trust DH at all? Well, no, it turns out that we don't know of any such black box that works faster than the best known attacks that works against a single session.

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