# 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 $$\mathbb{Z}_p^*$$ be a group, where $$p$$ is a large prime and let $$\alpha$$ be 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$$ can be found by exhaustive search, efficiently, in the small subgroup $$\mathbb{G}_w$$.

### 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$$ such that $$p-1 = w \times k$$. Plus, we know that $$\mathsf{ord}(\alpha) = p - 1$$ because $$\alpha$$ is a primitive root modulo $$p$$ and a consequence of Cauchy's theorem is that, given an element $$x$$, $$\mathsf{ord}(x^k) = \frac{\mathsf{ord}(x)}{(\mathsf{ord}(x) \wedge k)}$$. (Here, $$\wedge$$ denotes the greatest common divisor between two numbers.) So, in our case, we have:

$$\mathsf{ord}(\alpha^{ab(p-1)/w}) = \mathsf{ord}(\alpha^{abk}) = \frac{\mathsf{ord}(\alpha)}{(\mathsf{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. Therefore,

$$\mathsf{ord}(\alpha^{ab(p-1)/w}) = \frac{wk}{k} = w$$

As a result, 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$. Aug 19, 2015 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$.