Pohlig Hellman and small subgroup attacks

Question

While studying Curve25519 I read about the small subgroup attack in chapter 3. So far i know, that you need a point with a small subgroup to do such an attack. Curve25519 has a basepoint with prime order, therefore it is resistent. My question is: How does such a small subgroup attack work? Can you give me an example?

Now I'm a bit confused, too. I know the Pohling Hellman attack. You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $E$ an elliptic curve over $F_p$. Be $p = f_1 \cdot f_2 \cdot ... \cdot f_n$ the factorization. Be $xP = Q$ the discrete logarithm. Now you can use the Chinese remainder theorem to solve the following system of equations: $x \cdot (p/f_1)P = (p/f_1)Q$, $x \cdot (p/f_2)P = (p/f_2)Q$, ... , $x \cdot (p/f_n)P = (p/f_n)Q$. So this can be used to calculate the private key by just knowing the public key. My question: I think those two attacks are related. But I don't understand how. Can you explain this to me?

Answer 1

The Pohlig-Hellman algorithm reduces the discrete logarithm from a group of composite order to subgroups of prime order. For instance, with an elliptic curve and a point $P$ whose order is a composite integer $q = p_1 \cdot p_2$, and we want to find $k$ such that $Q = [k]P$ for a given point $Q$. Then, since $[p_2]P$ is a point of order $p_1$. Let $$ Q_2 = [p_2] Q,\quad \text{and} \quad P_2 = [p_2]P, $$ and now we have $Q_2 = [k\bmod p_1] P_2$. Generic discrete logarithm algorithms can then be used to get to obtain $k\bmod p_1$.

With $Q_1 = [p_1]Q$ and $P_1 = [p_1]P$, we obtain $k\bmod p_2$ and the Chinese Remainder Theorem can be used to get $k$. Then, the security depends mainly on the largest prime in the decomposition of $q$. That's why points whose order $q$ is a large prime is chosen.

In the small subgroup attack, the idea is to make the computation happens with a point of small order instead of a point whose order is a large prime. Typically, standardized curves in cryptography have order $q\cdot h$ where $q$ is a large prime and $h$ is generally small. The principle is the attacker, instead of sending a point of order $q$, sends a point $P$ of order $h$ (for example in a Diffie-Hellman key-exchange). Then the computation with a secret value $k$ will be $Q = [k]P$, but since $P$ has order $h$, there is at most $h$ possible values for $Q$.

In a Diffie-Hellman key-exchange, it works like this: the attacker sends $P$ of small order to Alice instead of its valid public point. Alice computes $Q = [k]P$ thinking that the point $Q$ is the shared secret, from which she derives a symmetric key to encrypt the communication. Since there is only a few possible values for $Q$, there are only a few possible keys. The attacker tries them one by one until the decryption is correct. When this is the case, he learns $k \bmod h$.

You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $E$ an elliptic curve over $F_p$. Be $p = f_1 \cdot f_2 \cdot \ldots \cdot f_n$ the factorization.

For clarification, in cryptography an elliptic curve is defined over a finite field, and a finite field has an order that is either a prime $p$ or a power of a prime $p^\ell$. This value is not the order of the curve. The order of the curve is very close to it, but is generally different.