Join Log in
Score:1
user363406 avatar Crypto

How to know if you have guessed the correct Diffie-Hellman shared secret?

tg flag
user363406

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.

80
0 + 0
ming alex avatar
in flag
ming alex
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.
0
Reply
Score:1
poncho avatar Crypto
my flag
poncho

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.

0 + 0
user363406 avatar
tg flag
user363406
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.
0
Reply
poncho avatar
my flag
poncho
@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
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.