In this blog, we talk about a power analysis attack on SIKE in a semi-static setting.
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:
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:
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.
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:
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.
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