2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ But how exactly does a small subgroup attack work? First attempt: I'm sending a "bad" public point to the victim. Then the victim calculates a secret shared key, which I should not get. Second attempt: I take the public key of the victim, then make a multiplication with a small subgroup. But I don't understand how to get informations with this method. I did not find a example for that attack, can you provide a simple one? $\endgroup$
    – Titanlord
    Jul 11, 2020 at 10:15
  • $\begingroup$ The attacker sends a point $P$ to Alice who thinks it's a valid public point. she computes $Q=[k]P$ thinking $Q$ is the shared secret. Since there is only a few possible values for $Q$, it is the same for the secret key derived from it. Then, the attacker decrypts the communication by trying the possible keys, and learns $k\bmod h$ when the decryption is correct. (I have added this in my answer above.) $\endgroup$
    – user69015
    Jul 11, 2020 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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