Does this describe an invalid key share attack?

Question

I recently came across a mention of invalid key share attacks on this site. It is done with DH groups over $\mathbb{ℤ}_p$ :prime $p$, where $p = qh + 1$, where $q$ is the prime order of DH subgroup used, which can reveal $s$ s.t. $s \equiv x \bmod t$, given public key $X = g^x$, $x$ being a DH private key and $g$ being the generator of the subgroup. Where $t$ is some factor of $h$. I looked for it and could not find anything about it. I thought for a while and I think I know what it is. Can you please correct me if I am wrong?

For a simple example, I consider $p$ to be a safe prime so the subgroup should be the subgroup of quadratic residues modulo $p$. So let's say we have DH oracle with private key $x$ which takes as input a DH public key $Y = g^y$ and outputs $S = Y^x$. An attacker instead of feeding $Y = g^y$ to the oracle instead feeds $Z = g'^z$ where $g'$ is a primitive root modulo $p$ and $z$ is odd. It is an invalid public key because it does not belong to our subgroup. But the oracle ignores it and outputs $S' = Z^x = g'^{xz}$. Using the Legendre symbol, we calculate whether $xz \bmod p-1$ is even or odd which reveals whether $x$ is even or odd since $p-1$ is sure to be even. I am sure it is similar for other values of $h$ as well. Of course, it can be easily thwarted by having the oracle check whether or not the query is indeed a quadratic residue modulo $p$.

why to use a safe-prime in Diffie-Hellman key exchange?

EDIT: I thought of a new way that does not need oracle access. Since $p ≡ 3$ (mod 4), as $(p-1)/2$ is a prime number, each member of the subgroup must have two square roots, one quadratic residue and one non-residue. By choosing $g'$ as one of the square roots of $g$, whichever is a non residue, the attacker can get a diffie-hellman shared secret by trying $(\pm \sqrt{X})^z$. If authentication with shared key succeeds with the quadratic residue one, $x$ was even otherwise it was odd. This way we don't need an oracle that just spits out DH shared result.

Answer 1

Can you please correct me if I am wrong?

What you have is essentially correct; however it can be generalized a bit.

In real systems that use DH, the honest system will take the shared secret and do something with it; commonly putting it (and some public information that the attacker knows) through a KDF, and then using the keys generated by that KDF to either encrypt or decrypt a message. TLS would be an example of this.

What this means is that the attacker can verify a guess to the shared secret (by sending that guess through the KDF, and then seeing if the keys generated will decrypt the message from the honest system, or using the keys to encrypt a message that is sent to the honest system (and seeing if the honest system acted as if he could decrypt the message)

Here is how the attacker can exploit that to find $x \bmod t$ (where $t$ is a small factor of $(p-1)/q$); he finds a value $j$ that is of order $t$, he picks a random $y$ and sends as his key share the value $j \cdot g^y$. The honest system will compute $(j \cdot g^y)^x = j^{x \bmod t} \cdot g^{xy}$. The attacker knows the value $g^{xy}$; this gives him a way to test various values of $x \bmod t$.

Of course, it can be easily thwarted by having the oracle check whether or not the query is indeed a quadratic residue modulo $p$.

Or more generally making sure that $y^q = 1$. However, that is expensive; other possible defenses are:

• Simply never reusing a private value; this means that an attacker can learn some information about the value $x$ we used with an exchange with him - however, we wouldn't care if he could retrieve the entire $x$ value, as we allow him to learn the shared secret, and that's the only thing that $x$ would give him.

• Use a slightly larger value of $x$; for safe primes, $h=2$, which means that the attacker can learn the lsbit of $x$ and nothing else. Hence, if we select our $x$ value from a range 1 bit larger than we would have otherwise, then we have kept the discrete log problem just as hard (even if he learns that lsbit)