7
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Chris Peikert Aug 19 '15 at 20:11
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.