6
$\begingroup$

During a regular Diffie–Hellman public key exchange, Alice and Bob agree to use a prime number $p$ and a base $g$… which are both made public and are therefore also assumed to be known by Eve. Alice chooses a secret integer $a$ and sends $(A = g^a \mod p)$ to Bob, Bob chooses a secret integer $b$ and sends $(B = g^b \mod p)$ to Alice, etc.

One of the main pitfalls with a Diffie–Hellman public key exchange is, that Eve could try to use $p$ and $g$ for cryptanalysis, potentially learning the DH secret. Eve would have to solve the Diffie–Hellman problem to obtain $g^{ab}$. This makes things hard for Eve, but given enough computing power, it is not impossible.

Now, if Alice and Bob would agree upon $p$ and $g$ in advance (for example, during a face-to-face meeting in a SCIF), they would not have to agree upon $p$ and $g$ in public. As a result, Eve would have no option to learn the values of $p$ or $g$.

Under this condition:

  1. Would it still be possible for Eve to work out the shared secret key that Alice and Bob calculate? After all, Eve would only be able to intercept Alice’s $A$ and Bob’s $B$. Would it be feasible for Eve to learn anything (useful) at all, or would the missing $p$ and $g$ make it impossible for Eve to calculate the secret (even when assuming she had solved the DH problem)?

  2. What would be the impact on security, if Alice and Bob would “reuse” those $p$ and $g$ values for more than a single public key exchange? Would that give Eve any advantage in this scenario?

$\endgroup$
  • $\begingroup$ My intuition tells me that $p$ and $g$ would become part of the key, and keys can be brute forced (as long as the result can be verified). And if you repeat the use of $p$ I presume you learn more information about the modulus, so I guess the answer is "yes" and "yes", if you just look at the problem from a theoretical point of view. $\endgroup$ – Maarten Bodewes Aug 9 '14 at 12:37
  • $\begingroup$ @owlstead Well, I got asked this question by a friend yesterday – and all I could do was guess just like you. Yet, I would like to have an answer I can point to… because guessing feels so “incomplete” compared to the answers some of our Public-Key-Specialists tend to offer around here. ;) $\endgroup$ – e-sushi Aug 9 '14 at 12:44
  • $\begingroup$ Agreed, just trying to send it in the right direction, hence a comment instead of an answer. IMHO it's better to go for ECDH instead of trying to "amend" DH in this kind of fashion. Basically your friend is trying to fix a protocol that isn't broken. $\endgroup$ – Maarten Bodewes Aug 9 '14 at 13:12
  • $\begingroup$ @owlstead I doubt he’s planning to turn his “came-with-a-beer-question” into a real thingy… but if, you can be sure I’ll shoot him in the foot! ;) Nevertheless, thanks for the comments – I appreciate them (as always). $\endgroup$ – e-sushi Aug 9 '14 at 13:31
6
$\begingroup$

For the moment assume $g$ is a secret (uniformly random) generator, but that $p$ may be known to the adversary. Then given only $g^a, g^b$, the Diffie-Hellman key $g^{ab}$ is information-theoretically uniform (up to small statistical error), i.e., it cannot even be found by brute force because the adversary does not have enough information to determine it. This is because every generator $h=g^c$ for all $c$ (coprime to the group order) is equally likely to be the "real" one, so the "real" key is equally likely to be $g^{ab/c^2}$. Such values essentially cover all group elements (up to rare degeneracies). So essentially, Alice and Bob have a true one-time pad value.

However, this is not really interesting, because Alice and Bob were able to set up a secret generator $g$ in the first place, which is just as good as (or better than) a one-time pad value.

If Alice and Bob use the same $g$ for two or more runs of the protocol, then there is only one "degree of freedom" in the derived keys. That is, knowing one key (and the public messages) information-theoretically determines all the others. So any hope that the keys would look uniform and independent would have to depend on a computational assumption.

This all assumed that $p$ was known. It's much harder to analyze what happens when $p$ is unknown, because revealing group elements reveals some information about $p$, but it's hard to say what.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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