# Public Key Primitive Fault and Power Attacks and Countermeasures

## Side Channel Attacks and Countermeasures

To model side channel attacks we can adopt the approach described in [2, 3]. Assume that we have a computation C (which can be an RSA modular exponentiation or EC scalar multiplication) that consists of series of O0 or O1 operations that require inputs X0 and X1, respectively (thus Oi (Xi) for i e {0, 1}). During processing of the C computation, each operation can be linked to an information leakage variable Li. A side channel analysis attack is possible if there is some secret information у that is shared between Oi and its leakage Li. The ultimate goal of a side channel analysis is, by using a strategy, to deduce у from the information leakage Li. The simplest way to achieve that is by examining a sequence of Oi operations in time to discover у. Simple SCAs (SSCAs) can be easily mounted in square-and-multiply/double-and- add algorithms used in ME/SM and are typically horizontal type of attacks meaning that they are mounted using a single leakage trace that is processed in time. When SSCAs are not possible, advanced SCAs (ASCAs) must be mounted to a ME/SM architecture to extract у.

Advanced SCAs do not focus only on the operations (eg. Oi) but also on the computation operands [3]. Advanced SCAs are focused on a subset of the calculation C (and/or Oi) and through collection of sufficiently large number N of leakage traces Li (t) for all t e{1,..., N} using inputs Xi (t) exploit the statistical dependency between the calculation on C for all Xi and the secret у. ASCAs follow the hypothesis test principle [2, 4] where a series of hypothesis У on у (usually on some bit j of у,

i.e., Sj = 0 or 1) is made and a series of leakage prediction values are found based on each of these hypothesis using an appropriate prediction model. The values of each hypothesis are evaluated against all actual leakage traces using an appropriate distinguisher 8 for all inputs Xi so as to decide which hypothesis is correct.

SSCAs and ASCAs can follow one of two different leakage collection and analysis strategies, as originally described in [2], the vertical or horizontal approach. In the vertical approach, the implementation is used N times using either the same or different inputs each time t in order to collect traces-observations Li (t). Each observation is associated with t-th execution of the implementation. In the horizontal approach, leakage traces-observations are collected from a single execution of the implementation under attack and each trace corresponds to a different time period within the time frame of this execution. As expected, in horizontal attacks the implementation input is always the same.

Many SSCAs fit on the horizontal analysis strategy, as long as they are based on a single implementation execution leakage collection. Such attacks enable the attacker to discriminate O1: modular multiplication (RSA) or point addition (ECC) from O0: Modular squaring (RSA) or point doubling (ECC) in time thus revealing all bits of the secret s (the exponent (RSA) or secret scalar (ECC)). There also exist ASCA horizontal attacks that take advantage of the fact that each Oi operation when implemented in an existing generic processor, is broken into a series of digit based operations (e.g., word-based field multiplications) that are all associated to the same bit of the secret exponent/scalar. Such attacks are the Big Mac attack [5], the Horizontal Correlation Analysis attack (HCA) [6] or the Horizontal Collision Correlation attack (HCCA) [2, 3] that are described both for RSA and ECC designs.

There is a very broad range of vertical approach-based attacks on ME/SM implementations including sophisticated SSCAs and most of the ASCAs. Such SSCAs that require more than one ME/SM executions (e.g., two executions) include comparative SCAs (originally focused on Power attacks (PAs)) like the doubling attack (collision based attack) [7] (DA attack) and its variant, relative doubling attack (RDA attack) [8] or the chosen plaintext attack in [9] (also known as 2-Torsion Attack (2-TorA) for ECC). Vertical SSCA include also attacks applied specifically to SM, like the refined PA (RPA) or zero PA (ZPA) where a special point P0 (that can zero a P coordinate) is fed to an SM accelerator, thus enabling scalar bit l recovery through a vulnerability at round l.

Most ASCAs follow the vertical attack paradigm. Their success rate is associated with the number of traces that are needed to be processed vertically in order to reveal the secret s. The most widely used ASCA vertical attack is Differential Attack (DSCA) originally proposed by Kocher in [10] that is later expanded into the more sophisticated Correlation SCA (requiring less traces to reveal the secret than DSCA)

[11] and collision correlation attack [12-14] that can be mounted even if the attacker does not have full control of the implementation inputs.

Recently, researchers have shown that appropriate combination of vertical and horizontal attacks can enhance SCA success rate even against implementations that have strong SCA countermeasures [14, 15]. These publications are mainly based on vertical attacks that use horizontal attacks to bypass randomization/blinding countermeasures.

Countermeasures: SSCAs are thwarted by making the leakage trace of Oi indistinguishable from the leakage trace of O0. This can be achieved by more sophisticated (regular) ME/SE algorithms, like the square-and-multiply always/ double-and-add always technique or the Montgomery power ladder (MPL) technique [16] (presented in the following Table) or by applying the atomicity principle in the existing square- and-multiply / double-and-add ME/SM algorithm. Atomicity is realized by braking each Oi operation into atomic blocks (e.g., the same field operations) that are arranged in such way in time that they follow the same sequence for both O1 and O0. On the other hand, regular ME/SM algorithms provide SSCA resistance by making

MPL for RSA primitives

Input: c, e = (1, et—2, ...e0) e Z* where n is the public modulus Output: S = ce mod n Initialization: 70 = 1, T = c For i = t — 1 to 0 If ei = 1 then T1 = T12 mod n T0 = T0 • T1 mod n else

T0 = T02 mod n T1 = T0 • T1 mod n Return: T0

MPL for ECC primitives

Input: P, e E(F), e =

(et—1, et—2, ...e0) e F Output: S = (eP) Initialization: T0 = O, T = P For i = t — 1 to 0 If ei = 1 then T1 = 2 • T1 T0 = T0 + T1 else

T0 = 2 • T0 T1 = T0 + Tx Return: T0

the number of Oi operations constant in each ME/SM round (that processes one bit of the secret exponent/scalar). Unfortunately, the above countermeasures can be bypassed when each Oi operation is realized by Z* operations or F operations (for ME or SM respectively) that are implemented as a series of word-based operations (typical case in software implementations). In such case, horizontal attacks like the Big Mac, HCA, HCCA are still successful. Furthermore, the above countermeasures are thwarted by all vertical type of attacks including DA, RDA, and 2-Torsion and all ASCAs.

Randomization is a favorable solution for countering ASCAs (both horizontal and vertical). Using randomization, the sensitive information (exponent or scalar) is disassociated from the leakage trace and is hidden by multiplicatively or additively blinding this information using a random Group (Zn or E (F)) element. This hiding/blinding involves exponent, public modulus or message multiplication with a random number in the RSA case, or adding a random R point to the SM base point P, multiplying with a random element of F the base point’s projective coordinates as well as applying EC or finite field random isomorphisms (Coron’s Countermeasures [17]). Many of the above countermeasures do not fully protect an ME/ SM architecture from CSCA, CCSCA (and the SM specific attacks of RPA, ZPA [18]). This is more evident in ECC SM implementations where attackers have managed to defeat all 3 of Coron’s countermeasures (for some regular SM algorithms). For example, in SSCA resistant algorithms, like the BRIP method [19] (presented below) where the same random number is added to each round’s point values (thus creating a vulnerability [20]), randomization (base point blinding) may not prevent RDA or 2-TorA. Researchers have also shown that blinding cannot protect an ME/SM implementation if Z* operations or F operations (for ME or SM respectively) are implemented as a series of word-based operations. In such case, horizontal attacks (HCA, HCCA) or vertical-horizontal attack combinations are successful in revealing the secret s [14, 15]. Yet still, message/base point blinding can resist horizontal attacks as long as the bit length of the employed random element is large enough [6].

BRIP for RSA primitives

Input: c, B, B—1, e =

(1, et_2, ...eo) e Z* where n is the public modulus Output: S = ce mod n Initialization: To = B, Ti = B-1, T2 = c ? B-1 mod n For i = t _ 1 to 0 To = To2 mod n If ei = 1 then To = To ? T2 mod n else

To = To ? T1 mod n Return: T0 = T0 ? T1 mod n

BRIP for ECC primitives

Input: P, B, e E(F), e =

(et_1, et_2, ...e0) e F Output: S = e ? P Initialization: T0 = B, T1 = —B, T2 = P _ B For i = t _ 1 to 0 T0 = 2 ? T0 If ei = 1 then T0 = T0 + T2 else

T0 = T0 + T1 Return: T0 = T0 + T1