LR pixel

Differential power analysis on SIKE – part 2

In this blog, we talk about a power analysis attack on SIKE in a semi-static setting.

Side channel attack

Eventually, post-quantum cryptography will be implemented on a physical device and so it will be subjected to the same physical attacks as current cryptography. Side-channel attacks recover secret values from a device by focusing on the extra information unintentionally leaked by the physical implementation. To mount a side-channel attack, first the attacker measures physical variables, such as the timing of certain operations, or power measurements, and then analyzes such measurements to deduce secret values. These types of attack are typically non-invasive.

In this Blog post, we will focus only on power analyses on SIKE. The goal is to exploit the correlation between the processed information and the power consumption of the device. A simple power analysis deduces the information directly from the power measurement.

An example of such an analysis is the recovery of an RSA private key by analyzing the square-and-multiply implementation of the decryption procedure. In this case, the private key is directly recovered only by looking at the power measurement, as a bit set to ‘1’ produces a different pattern in the power consumption than a bit unset (bit equals to ‘0’).

Simple power analysis attacks can be prevented by making sure that all bits of a private key produce identical patterns of power consumptions. However, this does not protect from more powerful techniques, such as Differential Power Analysis (DPA) which statistically assesses values of secret keys by exploiting the link between power consumption and processed information. The two steps of a DPA are the following:

  • Data Collection: The attacker finds a suitable operation that takes several known inputs and one piece of secret information and collects one or more traces of power consumption (known as power traces) corresponding to the execution of such operation.
  • Data Analysis: The attacker tries to find a correlation between the energy consumption and the outputs of the operation, by making a guess on the unknown secret information.

DPA on SIKE

SIKE is a key encapsulation protocol using isogeny. Remember the blog on “SIKE and Side Channel Attacks”, to be able to compute his secret isogeny, Bob needs to calculate his secret point PB = P3 + [sk3]Q3. This operation is called the three-point ladder.

The operation “three-point ladder” is used on each phase of the protocol. The inputs are a part of Alice’s ciphertext (P’B, Q’B) and a Bob’s private key sk3. The computation of P’B + [sk3]Q’B is the following:

Three Point Ladder protocol

The function Ladder3pt takes as input the Bob’s secret key skB in a string bit m, the three points P, Q, Q-P which are part of Alice’s public key and return the point P + mQ.

We can observe that, in line 5 and 7 of the algorithm Ladder3pt, the function is the same but with different inputs. The operation xDBLADD takes as input three points (A,B,C) of an elliptic curve and return (2A, A+B). The goal of the DPA is to differential which of the two operations is used in each iteration of the loops. Indeed, guessing which operation occurred in one iteration gives one bit of the secret key.

DPA on a semi-static setting SIKE

Semi-static setting is not a setting invented for this attack, but it is used every day like the protocol: TLS.

In a semi-static setting, Bob generates one pair of keys (pk3, sk3), and Alice, for each communication, generates a new pair of keys. We will concentrate to recover only the first bit of Bob’s secret key. To recover the other, the attack is the same. Indeed, once the first bit is known, we can upgrade the values of the points and do the exact same thing to recover the second bit and so on.

The attacker does the next steps:

  • For each communication, he measures the power consumption of the first iteration of the three points ladder and intersects the communication between Alice and Bob (to know Alice’s public key).
  • For each communication, he can compute, in his own computer, the two possibilities (line 5 and 7).
  • He correlates the two different results independently with the power traces and looks which of the two has the biggest correlation (in absolute value) which gives the right guess for the bit.

The graph shows the difference of correlation between a good guess (in green) and a wrong guess (in red). We use the fact that the energy consumption is related to the update of the memory registers. The update will be different depending on which line (5 or 7 of the algorithm 1) we used.

Using the same principle, we could make an attack on one trace (i.e., in an ephemeral setting). For more information about this attack and the possible countermeasures, go to the following paper Full key recovery side-channel attack on ephemeral SIKE by A. Genet, N. Kaluderovic and N. Linard.

About CYSEC LAB

CYSEC LAB is a security evaluation lab performing research of front-edge technologies. The team, made of embedded engineers, security researchers and cryptographers, has the complementary skills that allows CYSEC to engineer and develop home made test benches with high performance.

For more information, please visit: www.cysec.com/lab/

 

Media Contact

Alexandre Karlov

alexandre.karlov@cysec.com

Latest Industry News