Point-at-infinity and error handling

Question

I'm looking at a piece of (non-object oriented) code where functions return point-at-infinity for a specific prime curve if a calculation errors out. This is even the case when validating arguments to the functions; obviously the point-at-infinity is used as a "magic value" (comparable with returning nil when a function fails).

Can I assume that each and every one of the occurrence of point-at-infinity is actually an error in the code itself? Should I just create an error each time I find point-at-infinity?

Or, if above is not the case, are there any valid EC calculations that may result in point-at-infinity? If yes, what would be an appropriate action when this occurs? Does it make sense to validate each time that a function never returns point-at-infinity (assuming that I get rid of the code-generated point-at-infinity return values, of course)?

Answer 1

This would of course depend on your protocol and or algorithm, so it's hard to give too specific advise without details of those.

Returning the point at infinity is not necessarily an error. The usual scenario would be a point $P$ of order $n$, and some secret scalar $k$. You would want to choose $1\leq k\leq n-1$, so that $k\cdot P$ will never end up being at infinity. However, one common scenario is side-channel sensitive implementation, where we would want to blind the scalar $k$. That is, we compute $(k+\lambda n)\cdot P$ for some random $\lambda$. The result will be the same, since $P$ has order $n$, but in this scenario you could run into the point at infinity at some intermediate step.

Another case would be a computation of the form $k_1 P+k_2 Q$, which is commonly done in signature verification. Also here it is not true that you never run into the point at infinity. A more general case of this would be when you start using endomorphism-based routines. Essentially the more complex the algorithm, the harder it is to prevent running into the point at infinity.

Note that for large primes, this will never happen (that is, it is extremely unlikely). However, there may be scenarios where an attacker can control input. In that case it is possible to force the algorithm to end up at the point at infinity, which may be exploitable.

How would you deal with this? It depends. If a 30-50% slowdown is not of crucial importance (I'd argue it rarely is), then there are complete formulas. These work even when you input the point at infinity. It is well-known for Edwards and Hessian curves, but a rather recent result shows that you can also do this on prime order curves. This would solve all your problems.

If you don't want to do this, you'd have to take a close look at your protocol. Is there any possibility of a scalar becoming larger than the order of a point? Is there any point where the attacker has influence on the input data? If so, is it exploitable?