52 Things: Number 44: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for ECC.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we consider what can be done to mitigate the threat of side-channels against  ECC implementations...

In this blog post we will discuss "some basic (maybe ineffective) defences against side channel attacks proposed in the literature for ECC". This can be seen as a complement to last weeks blog which asked the same question for AES.

Before we start the discussion, I want to clarify what kind of countermeasures we will be considering. From this point forward we will only be considering implementation level countermeasures, I will not consider hardware countermeasures such as Dual Rail Logic, or location security such as putting it in a concrete box. While the title says "maybe ineffective" I will stick to designs that at least have some hope of working, for example wearing a tinfoil hat will not secure my credit card and will clearly not work and so will not be discussed.

Elliptic curve cryptography as a rule is reasonably good when it comes to resisting side channel attacks but there are still some points that are worth considering.

Scalar Multiplication
As with most cryptography scalar multiplication (normally exponentiation in other schemes) is a very leaky operation, this is well studied in RSA. This is no different in elliptic curve cryptography because the addition operator and the double operator behave differently. Various techniques that can be applied to RSA can also be applied here, such as exponent blinding where for each scalar multiplication you choose a value $r$ such that $[a]P=[a+r]P$ where $a$ is the value you require to keep secret and $P$ is a generator of the curve. Since scalar multiplication only leaks information about the scalar this technique only needs to be applied when you want to keep the scalar secret. Recently there has been work to create elliptic curves which have the same operation for double and add which would resolve this issue.

Is a point on the curve?
Sometimes an $x$ value is chosen and to learn if it is on the curve you use the Jacobi symbol to learn if $x^3+a\cdot x+b$ is square. If it is $(x,y)$ is an elliptic curve point. As can be seen by the algorithm in the link, the process of calculating the Jacobi symbol is variable length and thus may leak information about the secret value $x^3+a\cdot x+b$. Since we are only interesed if $x^3+a\cdot x+b$ is square, we note that $x^3+a\cdot x+b$ is square if and only if $r^2\cdot(x^3+a\cdot x+b)$ is, for random $r$. Using this technique we can check if $x$ is a valid point on the curve but since it has been blinded by a random $r$ this will not leak anything about the underlying point.

Theoretically secure
While against known side channel attacks elliptic curves are reasonably secure without much help, it is possible to secret share certain schemes to enhance the security. Providing that each share leaks independently it is possible to create schemes which are provably secure against arbitrary leakage functions (including ones which can only happen in theory and not in practice). This area of cryptography has become known as Leakage Resilient Cryptography.