# Is it safe to operate over the prime sub-group of Curve25519?

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

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.
• 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... – poncho Dec 12 '16 at 22:29