Defense Against Power Analysis Attacks: Avoiding Elliptic Curve Side Channel Attacks

In 1999, Paul Kocher, Joshua Jaffe, and Benjamin Jun wrote an article titled “Differential Power Analysis”. They described how monitoring the power supply of a processor allowed them to determine the secret key associated with a DES encryption algorithm. This is still an important security attribute to be aware of when designing modern protocols. Fortunately, for elliptic curve cryptographic algorithms, there is a mathematical solution.

To perform a power supply attack, the eavesdropper must have physical access to the processor performing the algorithm. For a smart card, this is fairly easy. For an application on a smartphone, it takes a bit more equipment. For most applications, it is something to worry about.

This figure shows the basic setup for a power analysis side channel attack. You have the ability to monitor the voltage (or current) from the power supply into the processor. The changes are small, so there might be an amplifier involved, but the setup is the same. Every step the processor takes uses a different amount of power, and certain subroutines will create specific patterns on the oscilloscope.

In elliptic curve cryptography, the addition of two points has a specific formula. This formula can be more efficient if the two points are the same, which is known as doubling. The classic formula for point addition is

The values for (x_1, y_1) and (x_2, y_2) are the points being added together. The result (x_3, y_3) is the new point on the curve. The value of \lambda changes if the points being added are the same or are different. If the points are the same (a doubling operation), the value is

If the points are different, the formula is

This difference becomes exceptionally important when a private key is used in an algorithm. The multiplication process involves doubling for each bit position and then adding a point if a bit is set. You can see on the oscilloscope when a doubling operation happens and when an addition happens, so you can find the private key and break the security of the elliptic curve algorithm.

This is a bad problem to have. We want to use a different value for \lambda, which is always the same no matter what the input points are. The solution is to use this formula.

If x_1 and x_2 are the same, we recover the doubling formula. The only problem is when y_1 = -y_2. This gives the point at infinity - and we have to deal with that possibility no matter what formula we use.

From the attacker’s perspective, the number of doubling and adding operations can be determined. Since the prime number determining the field size is public, the attacker knows the number of bits used for doubling. The attacker can compute the number of bits in the private key that are set. If there are enough bits in the primes used to secure the elliptic curve, it will be impossible to guess which bits are set.

For example, if the base field has 256 bits for the prime, and the private key has 128 bits set, the attacker needs to try 2^128 keys. That should take the age of the universe with a large GPU supercomputer. This formula is less efficient than the standard version, but it is far more secure from the standpoint of power analysis.

For more details on elliptic curve mathematics, check out Elliptic Curve Cryptography for Developers: http://mng.bz/D9NA.