# 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$.