1
$\begingroup$

Given only $p,$ $g,$ $A = g^a\pmod{p}$ and $B = g^b\pmod{p},$ the possible values for the shared secret are all the unique values of $A^b\pmod{p}$, where b is some integer. The shared secret is also equal to $B^a\pmod{p}$, where a is some integer.

So, we can check each one of these possible values for the shared secret. My question is, how do we check if a number is the correct shared secret?

My guess is this:

Usually the shared secret is used in a symmetric encryption scheme, the overall terms of which must logically be agreed upon in the public channel. So from our vantage point, we would know what type of symmetric encryption is being used, and therefore how the shared secret is being used, and could therefore try decrypting a given message with each possible shared secret until we find one that gives us the original, unencrypted message. But then we would have to know what the original unencrypted message should look like.

Improve this question
$\endgroup$
1
  • $\begingroup$ As we known, the security of DH protocol is mainly based on the discrete logarithm problem. If $|p|$ is very large, then no PPT algorithm can sovle this problem. I suggest you read some cryptographic book to further understand this point. $\endgroup$
    – ming alex
    Nov 13, 2021 at 3:50

1 Answer 1

Reset to default
1
$\begingroup$

So, we can check each one of these possible values for the shared secret.

In practice, the number of possible values for the shared secret is too large for scanning over all the possibilities to be practical - there are always easier attacks. And, as you appear to have guessed correctly, recognizing the shared secret based on $g, g^a \bmod p, g^b \bmod p$ is believed to be a hard problem (in fact, we call it the "Decisional Diffie-Hellman problem")

One attack is to take $g$ and $g^a \bmod p$ and attempt to recover $a$ (that is, solve the discrete log problem) - once we have $a$, we can compute $B^a \bmod p$ (which is the shared secret), and that's the shared secret.

The other possible approach is to attack the symmetric side of things - we ignore the DH operation completely, and just do a brute-force attack on the symmetric key. BTW: not knowing the exact plaintext is typically not an issue; even if we don't know what it is exactly, we generally know enough about it to distinguish it from random gibberish (which is what you get when you attempt to decrypt it with the wrong key) - in addition, if you use an AEAD algorithm, the key is used to generate a tag (as well as encrypt), and the tag can also be used to distinguish the correct key (even if the plaintext really is random gibberish).

For both of these attacks, we typically select security parameters (such as the size of $p$ and the size of the symmetric key) to make both these approaches infeasible.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The thing is, the discrete logarithm problem has infinite solutions, because there are infinite values for $a$ that satisfy $g^a\pmod{p} = A$ where A is some number in the set {1,...,p-1}. That's what confuses me when people say "solve the discrete logarithm problem". Afaik solving it would just come down again to guessing and checking different possible $a$ values, and so this is just a more computationally intensive version of the Decisional DH problem. $\endgroup$
    – user363406
    Nov 13, 2021 at 20:41
  • $\begingroup$ @user363406: if we find any solution $a$, then we can find all the other solutions by adding or subtracting multiples of $q$ (where $q$ is the order of $g$). Another way of saying this is that there is (at most) one solution in the range $[0, q)$; since we usually know the value of $q$, we can say that there is a "unique" solution. BTW: there are known groups where the decisional DH problem is known to be easy (given the values $g, g^a, g^b, g^{c}$, we can always determine if $g^{ab} = g^c$), and the computational DH problem is believed hard - hence the cDH problem appears inherently harder $\endgroup$
    – poncho
    Nov 13, 2021 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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