8
$\begingroup$

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)?

$\endgroup$
8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks! Do you have a link for the "recent result" for prime order curves? I'll also check if complete formulas are used by the underlying library, but I strongly doubt it. It seems to me that I'd still rather stop execution with an error than continuing with execution - they'll have to try with other (randomized) input whenever I get to the point-at-infinity. PS: The curves are 256 bit or over, so the primes are pretty large. $\endgroup$ – Maarten - reinstate Monica Feb 14 '17 at 22:10
  • 1
    $\begingroup$ Here is the paper: eprint.iacr.org/2015/1060 $\endgroup$ – user94293 Feb 15 '17 at 6:33
  • 1
    $\begingroup$ Good Answer. Just few addons: Encountering the point at infinity in an intermediate computation will produce a wrong output due to limitations of addition formula in handling the point at infinity (in short weierstrass curves). If k > n (i.e. scalar blinding) this might happen. It might happen in algorithms with precomputations (e.g. comb). - The brier-joye montgomery ladder works exception-free if the input point has x \neq 0, and if you use formula 9 from citeseerx.ist.psu.edu/viewdoc/… for the addition then it always works. $\endgroup$ – Ruggero Feb 15 '17 at 8:28
  • 1
    $\begingroup$ The paper is the one given by user94293. You indeed will still want to do some checks (e.g. a public key is not the PAI), but the complete formulas protect against some unwanted behaviour in some cases. Note that it will be a little larger, but allows you to have a branch-free implementation (there are no exceptions!). This does not mean you cannot identify errors on a higher level: you are still able to check whether an output is the point at infinity. What @Ruggero suggests also definitely works, and will be faster. But the "security" guarantee is not as strong. $\endgroup$ – CurveEnthusiast Feb 15 '17 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.