Why do people worry about the exceptional procedure attack if it is not relevant to ECDSA?

Question

The exception procedure attack is described here: https://www.iacr.org/archive/pkc2003/25670224/25670224.pdf

People are afraid of this attack, because it could leak information on the private key in exceptional cases. [pun intended]

The assumed scenario for this attack is illustrated below:

1. If the attack is "not relevant to ECDSA, because the base point of ECDSA is usually fixed as the system parameter" then why do people worry about this attack?

2. The authors also note that "When the order of the elliptic curve is divisible by a small integer, the curve has several exceptional points. In other words, the curves whose order are prime are secure against the proposed attack, namely the recommended curves in several standards" The NIST curves have an order that is prime as well, then why do Tanja Lange and Daniel Bernstein mention this attack as a reason why the NIST curves are insecure, if the attack wouldn't work against these standardised curves?

Answer 1

Regarding your first question:

It is relevant for the Elliptic Curve Diffie-Hellman (ECDH) key exchange. In this scenario the user performs a scalar multiplication with the other user's public key, which is a variable point chosen by a possible attacker.

Note that another reason for the attack to not apply on ECDSA is because the scalar in ECDSA is a randomly selected integer different for each signature, which makes the attack ineffective as the attacker needs to test several base points with the same target scalar.

Regarding your second question:

It is not that simple. There might be condition where exceptions occurs even on prime order curves. For example if you don't restrict your scalar to be smaller than the curve's order or if you do a computation different from the classic double and add or if you don't use the standard formulas to achieve regularity (as the formula of Brier and Joye) or speed (as for example some Co-Z formula).

One of the point djb is making is that using the montgomery ladder on montgomery curves is extremely efficient and exception-free that you don't want to consider other solutions. And that works very well for ECDH. While for signatures you might rely on Twisted Edwards where similar properties apply.

Overall the message is not that we can't do exception free constant time implementation on the good old prime order curves. It's just that it is not as simple and in particular not as efficient then do it on Montgomery or Twisted Edwards curves.