In ECC scalar multiplication, how do `add(Q, Q)` exceptions occur?

Question

Consider some scalar multiplication algorithm for a prime order (Weierstrass) curve $E$ with order $\ell$. Bernstein and Lange's SafeCurves: Completeness page mentions:

The problem is that the standard Weierstrass "addition formulas" don't always work: in particular, they fail for the doublings Q+Q.

Now let's say my scalar multiplication properly "clamps" any secret scalars $k$ such that it is ensured that $0 < k < \ell$. We also check that $P$ lies on the curve and $P \ne \infty$. Then we implement the scalar multiplication using a standard left-to-right DoubleAndAdd algorithm:

1: function DoubleAndAdd(k, P)
2:     R = ∞
3:     for i from n-1 down to 0 do
4:         R = double(R)
5:         T = add(R, P)
6:         R = select([R, T], k[i])
7:     end for
8:     return R
9: end function

Now my intuition thinks that add(Q, Q) will never occur in this algorithm.

---

Observation. First observe that in $m$ loop iterations we can only compute points $R \in \{∞, P, \ldots, [2^m-1] P\}$.

Argumentation. Now, assume that add(Q, Q) indeed occurs in this algorithm. In the algorithm, P is constant, so this will happen only when R == P before executing line 5. In the same iteration, R has just been doubled in line 4. During that same iteration before the doubling in line 4, R had the value [1/2]P $=\left[\frac{\ell + 1}{2}\right] P$. This means that we can always compute $R = \left[\frac{\ell + 1}{2}\right] P$ in $(n-1)$ loop iterations.

For example, if $\ell$ is the Mersenne prime $2^n-1$, then we have computed $R = \left[\frac{2^n - 1 + 1}{2}\right] P = \left[2^{n-1}\right] P$ in $n-1$ loop iterations. After filling in $m = n-1$ we realize that $R = [2^m] \cdot P$. But this contradicts our Observation. So add(Q, Q) can indeed not occur. □

---

Now I am not really sure if my gut is right, or if I should trust the SafeCurves page. Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

Answer 1

In ECC scalar multiplication, how do add(Q, Q) exceptions occur?

Probability that it occurs when performing multiplication for large random $k$ (allowed to exceed $l$) and $P$ a generator is $\mathcal O\left(\dfrac{\log(k)}l\right)$ for a random $n$-bit curve, thus negligible when using actual curve parameters. Thus it can occur only when fed incorrect parameters; the cryptosystem or hardware is under attack; or using toy-size parameters making the crytosystem insecure.

So add(Q, Q) can indeed not occur. □

I see no gap in the question's proof, now that it is explicitly stated that $P$ is on the curve, thus itself has prime order $l$.

Using the DoubleAndAdd algorithm above, is it possible for any exceptions to occur in the addition in line 5?

No for correct execution (including, no induced fault attack) and parameters: $P$ on the curve of prime order $l$, $P\ne\infty$, $0\le k<l$.