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 O_{0} or O_{1} operations that require inputs X_{0} and X_{1}, respectively (thus Oi (X_{i}) for i e {0, 1}). During processing of the C computation, each operation can be linked to an information leakage variable L_{i}. A side channel analysis attack is possible if there is some secret information у that is shared between O_{i} and its leakage L_{i}. The ultimate goal of a side channel analysis is, by using a strategy, to deduce у from the information leakage L_{i}. The simplest way to achieve that is by examining a sequence of O_{i} 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. O_{i}) but also on the computation operands [3]. Advanced SCAs are focused on a subset of the calculation C (and/or O_{i}) and through collection of sufficiently large number N of leakage traces L_{i} (t) for all t e{1,..., N} using inputs X_{i} (t) exploit the statistical dependency between the calculation on C for all X_{i} 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 X_{i} 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 L_{i} (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 O_{1}: modular multiplication (RSA) or point addition (ECC) from O_{0}: 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 P_{0} (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 O_{0}. 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 O_{1} and O_{0}. On the other hand, regular ME/SM algorithms provide SSCA resistance by making

MPL for RSA primitives

Input: c, e = (1, e_{t—2}, ...e_{0}) e Z* where n is the public modulus Output: S = c^{e} mod n Initialization: 70 = 1, T = c For i = t — 1 to 0 If e_{i} = 1 then T1 = T_{1}^{2}mod n T0 = T0 • T1 mod n else

T_{0}= T_{0}^{2}mod n T1 = T0 • T1 mod n Return: T_{0}

MPL for ECC primitives

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

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

T0 = 2 • T0 T1 = T0 + T_{x }Return: T0

the number of O_{i} 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 O_{i} 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, e_{t}_2, ...eo) e Z* where n is the public modulus Output: S = c^{e} mod n Initialization: To = B, Ti = B^{-1}, T2 = c ? B^{-1}mod n For i = t _ 1 to 0 To = T_{o}^{2}mod n If e_{i} = 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