4
$\begingroup$

Referring to D. J. Bernstein's paper Bernstein-Curve25519 on Curve25519, the group $\{\infty\} \cup (E(F_{p^2}) \cap (F_p \times F_p))$, where $p$ is the prime $2^{255}-19$ and $E$ is the elliptic curve $y^2 = x^3 + 486662x^2 + x$, has size $n = 8p_1$, where $p_1$ is the large prime $2^{252} + 27742317777372353535851937790883648493$.

In the same paper, he suggests clearing the 3 least significant bits of the 255-bit secret scalar $k \in [1, n-1]$ (for elliptic curve scalar multiplication over Curve25519), that is, making $k$ a multiple of 8, to prevent small sub-group attacks. Note that this also reduces the effective security level of the curve to $\approx 2^{252}$.

Instead, is it equally safe to choose the scalar $k$ from $[1, p_1-1]$, that is, operate over the prime sub-group of Curve25519? This does not change any of the curve operations, only the scalar is chosen differently. Also, small sub-group attacks are not possible since $k < p_1$ in this case, and the effective security level is again reduced to $\approx 2^{252}$.

$\endgroup$

1 Answer 1

3
$\begingroup$

Theoretically, yes you can do that. The idea you have is correct: we can simply choose an integer $k\in[1,p_1-1]$ to determine our public key $Q=[k]P$. The effective hardness in solving the discrete logarithm comes from the large prime order subgroup, so in that case we lose nothing.

However, it is not true that small sub-group attacks are not possible. We are still working over a curve $E$ which contains points of small order, let's say $P_2$ is a point of order 2. Now I engage in a Diffie-Hellman key exchange by sending over my (malicious) "public key" $P_2$. In turn I receive back $[k]P_2$, given that your secret key is $k$. Then $$k\equiv0\bmod{2}\iff [k]P_2=\mathcal{O}.$$ Hence I have learnt $k\bmod{2}$.

How should we prevent this? In the obvious way: before computing $[k]P_2$, we first check $8P_2\neq\mathcal{O}$. As poncho notes, this prevents only this specific attack. The more generalized attack, where we send $P_s=[k']P+Q_s$, for $Q_s$ a point of small order, still works and can instead be prevented by checking that $[p_1]P_s=\mathcal{O}$. As mentioned, this is quite expensive.

What we can do instead, is only allow our scalars to be $0\bmod{8}$ (i.e. the three lsb's all zero), so that there is nothing to be learnt in the first place. Therefore we have an inherent resistance against small sub-group attacks, which is not true if $k$ were prime. This is exactly what happens for Curve25519.

$\endgroup$
3
  • 1
    $\begingroup$ Actually, verifying that $8P_2 \ne \mathcal{O}$ does not prevent this attack; that's because the attacker can pick a random $k'$ and make $P_2 = k'P + Q$ where $Q$ is a point of order 2; then the shared secret you derive will be either $[kk']P$ or $[kk']P + Q$ (depending on the lsbit of $k$), and if the attacker can test which secret you got, he then learns the lsbit of $k$. Checking whether $[p_1]P_2 = \mathcal{O}$ does work, but is expensive; allowing only scalars of the form $0 \bmod 8$ is cheaper... $\endgroup$
    – poncho
    Dec 12, 2016 at 22:29
  • $\begingroup$ @poncho Thanks, I added that to the answer. It was misleading to infer that this prevents all small-subgroup attacks, whereas you show that it only prevents some. $\endgroup$ Dec 13, 2016 at 7:38
  • 1
    $\begingroup$ @Naruto999 Also note that curve25519 scalars have the 254 bit set. This was done to avoid time leaks in certain implementations (e.g. montgomery ladders discarding the leftmost zeros in the scalar). You loose this property if scalars are defined your way. $\endgroup$
    – Ruggero
    Dec 13, 2016 at 8:28

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.