# Small subgroup confinement attack on Diffie-Hellman

I am trying to understand the small subgroup confinement attack on the Diffie-Hellman algorithm. I will present the attack and try to explain why it works.

### Small subgroup confinement attack on the Diffie-Hellman algorithm

Let be a group $\mathbb{Z}_p^*$ where $p$ is a large prime and $\alpha$ a primitive root modulo $p$. Let's consider that Alice and Bob want to do a key agreement on the whole cyclic group $\mathbb{Z}^*_p$ using the Diffie-Hellman algorithm. The following sequence diagram illustrates how Eve can perform a small subgroup confinement attack: By doing this, if $k$ is well chosen, the secret $S$ can be found by exhaustive search.

### How to choose the $k$-value

As $p$ is a prime number, the order of $\mathbb{Z}^*_p$ is a composite, so there exist subgroups. Say $\mathbb{G}_w$ is one small subgroup of prime order $w$. So by picking $k = \frac{p-1}{w}$, the secret value $S \in \mathbb{G}_w$ and as it is a small subgroup, $S$ can be found by exhaustive search efficiently.

### Why does it work?

In this section I will try to prove that $S \in \mathbb{G}_w$.

We know that $w\text{ | } (p-1)$ so $\exists k$ as $p-1 = w \times k$. Plus we know that $ord(\alpha) = p - 1$ because it is a primitive root modulo $p$ and a consequence of the Cauchy's theorem is that given an element $x$, $ord(x^k) = \frac{ord(x)}{(ord(x) \wedge k)}$. So in our case we have:

$ord(\alpha^{ab(p-1)/w}) = ord(\alpha^{abk}) = \frac{ord(\alpha)}{(ord(\alpha) \wedge abk)} = \frac{(p-1)}{((p-1) \wedge abk)} = \frac{wk}{ (wk \wedge abk)}$ and we know that $(wk \wedge abk) = k$ because $w$ is a prime number. So we obtain that $ord(\alpha^{ab(p-1)/w}) = \frac{wk}{k} = w$ so we can conclude that $S \in \mathbb{G}_w$.

Could someone approve or disapprove my demo?

• Here's a simpler way to see it: using the fact that $\alpha^k \in \mathbb{G}_w$ that you've already proved, you know that $A^k = (\alpha^k)^x \in \mathbb{G}_w$. Since the (new) $K$ is a power of $A^k$, it also lives in $\mathbb{G}_w$. – Chris Peikert Aug 19 '15 at 20:11

The proof provided in the question is correct, but as Chris Peikert pointed out in comments, there is an easier way to prove that $S \in \mathbb{G}_w$:
$ord(\alpha^k) = \frac{ord(\alpha)}{ord(\alpha) \wedge k} = \frac{p - 1}{(p-1) \wedge k} = \frac{p - 1}{k} = w$ so it implies that $\alpha^k \in \mathbb{G}_w$.
As $A^k = (\alpha^a)^k = (\alpha^k)^a$ is a power of $\alpha^k$, it also implies that $A^k \in \mathbb{G}_w$.
In the same way, $S$ is a power of $A^k$ so $S \in \mathbb{G}_w$.