# curve25519 weak points for contributory behaviour

The Diffie-Hellman on curve25519 is usually calculated using the base point $(9,…)$ which induces a cyclic subgroup of $G:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times F_p))$ with index 8, i.e. there is a prime $p_1$ such that $|G|=8p_1$ and the order of $(9,…)$ is $p_1$. An attacker does not have to use a multiple of $(9,…)$ though and can even choose an element in the twist group $T:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times \sqrt 2 F_p))$ which has order $|T|=4p_2$ for a prime $p_2$.

Contributory behaviour (afaik) describes the property that none of the participants of the Diffie-Hellman exchange can force the outcome to be one of a small set of values. Such a property is for example interesting to defend against something like the triple handshake attack. The website on curve25519 lists 12 values to reject to assure contributory behaviour.

I understand where eleven of these come from, namely the elements of the subgroups of order 8 and 4 of $G$ and $T$ respectively. As they both share the same identity element ($\infty$) there are $8+4-1=11$ of those elements.

(If an element is not in those subgroups of order 8 and 4, then its order is $\geq \min(p_1,p_2)$ and thus the set of possible values that result out of the multiplication with the private scalar of the other party is large.)

Which of the 12 elements listed on the website is not one of the above eleven and why is it there?

• Discussion of the effect of weak points on Ed25519 signatures It's possible to forge messages that crypto_sign_open verifies if the public key is zero – CodesInChaos Jun 17 '14 at 14:38
• @CodesInChaos: Very interesting application… Regarding the discussion there: I'm torn between arguing that this property is not at all a weakness of the implementation and that relying on such notion would be the fault of the protocol (similarly as I would see non-malleability as an unreasonable requirement of a signature scheme). And on the other hand I see the length extension property of the SHA2 family as a weakness and struggle to justify why this property is any different to it and why signature schemes shouldn't also be build as strongly as possible. – Perseids Jun 17 '14 at 20:31

There are actually only 5 unique $x$-coordinates one needs to be concerned about:

• $(0, \ldots)$
• $(1, \ldots)$
• $(-1, \ldots)$
• $(x_1, \ldots)$
• $(x_2, \ldots)$,

where

$$\begin{eqnarray} x_1 =& 393823572354896145817230607815530211125 \\ & 29911719440698176882885853963445705823 \end{eqnarray}$$ and $$\begin{eqnarray} x_2 =& 32560625091655743179598362635611063129 \\ & 4008115727848805560023387167927233504 \end{eqnarray}.$$

These correspond to the $x$-coordinates of points of small order on the curve and its twist, as you have pointed out. The remaining values you see are the multiples of those $x$-coordinates below $2^{256}$:

• $0 \equiv 2^{255}-19 \equiv 2(2^{255}-19) \pmod{2^{255}-19}$
• $1 \equiv 2^{255}-19 + 1 \equiv 2(2^{255}-19) + 1 \pmod{2^{255}-19}$
• $2^{255} - 19 - 1 \equiv 2(2^{255}-19) - 1 \pmod{2^{255}-19}$
• $x_1 \equiv 2^{255} - 19 + x_1 \pmod{2^{255}-19}$
• $x_2 \equiv 2^{255} - 19 + x_2 \pmod{2^{255}-19}$

These extra values are checked because curve25519 was designed to accept any $256$-bit string as public-key, and each value has one or more 256-bit representations modulo $2^{255}-19$.

• Thx. Quite interestingly (0,…) stands out from the others, because the specification defines $X(Q)$ - which normally is the x-coordinate of $Q$ - as zero for $Q=\infty$. Still (0,0) is a valid point on the curve, so the image "0" of $X$ that is listed on the website refers to both $\infty$ and (0,0). Furthermore there is no $y\neq 0$ with (0,$y$) being an element on curve. So while the other dots refer to multiple y-coordinates for the same x-coordinate, the dots in (0,…) refer to the special case of the $X$ map. – Perseids Jun 15 '14 at 22:04
• If you reject points based on their bitstrings, one pitfall is that different implementations treat the last bit differently. NaCl treats the input as a 256 bit integer, most other implementations ignore the bit. The strings you need to reject differ between the encodings. – CodesInChaos Jan 8 '15 at 15:18