The broad variety and heterogeneity of PA and FA attacks implies that it is hard to design countermeasures capable of providing wide scale protection. This is further supported by the fact that PA and FA combinations apart from eliminating vulnerabilities may introduce new ones. Apart from specific design oriented countermeasures like dual rail logic and power balancing [41, 42] that must be fine-tuned to a single implementation in order to be effective, algorithmic-based countermeasures may offer a more generic protection approach that can be applied to a wide range of RSA/ECC implementations regardless of the architecture those implementations follow. Our goal is to describe such algorithmic approaches for PA and FA resistance that combine effectively different PA and FA countermeasures and offer long-term PA-FA resistance against known attacks. This research approach focus point is on well-established PA-FA resistance principles rather than specific resistance countermeasures on ME and SM accelerator units.
As a basis of the proposed algorithm approach on PA-FA resistant ME/SM, the MPL algorithm is used. The MPL algorithm is resistant against many of the mentioned attack in Sect. 5.2.1, it does not rely on dummy operations in order to hide the computation flow during ME/SM execution (modular multiplication or squaring for ME or point addition and doubling for SM) and also favors operation parallelism thus leading to fast implementations. The original MPL algorithm though offers SSCA resistance (and more specifically Simple PA resistance) and under some restrictions is horizontal attack resistant. To further enhance the MPL with ASCA resistance, we must introduce some blinding technique through additive or multiplicative randomization. Such countermeasure follows the protection technique of message/base point blinding, since it constitutes an approach that under careful application in the MPL algorithm cannot be bypassed or introduce considerable performance overhead to a ME/SM implementation. Other techniques like exponent/scalar blinding are not very efficiently implemented and are found to have vulnerabilities [36, 37]. However, message/base point blinding must be realized in such a way that it should not suffer from vulnerabilities similar to the BRIP method .
Assuming that all operations in the proposed algorithm are defined in a group G, where G is either the multiplicative group Z* (for RSA) or the additive group E(F) (for ECC), we introduce a random element B e G and its inverse B-1 e G into the MPL computation flow that can blind the message multiplicatively (B ? c mod n,
i.e., message blinding for RSA) or the base point P additively (B + P, i.e., base point blinding). In contrast to similar approaches, where in each ME/SM round the round’s computed values are blinded with the same random element, in the proposed approach, a round’s values are randomized with a different number in each round (a multiple of the random element B).
Concerning FA resistance, our approach adopts a combination of the infective computation and fault detection resistance principles, following the intermediate values mathematical coherence characteristic of the MPL algorithm. As observed in  and by Giraud in , the T0 and T1 value in an MPL round always satisfy the equation T0 = c ? T1 mod n or T0 = P + T1 for ME or SM, respectively. Injecting a fault during computation in a T1 or T0 variable will ruin this coherence and by introducing an MPL coherence detection mechanism in the end of the MPL algorithm, this fault will always be detected. Finally, efficiency of the proposed approach is achieved by employing Montgomery modular multiplication for ME and by exploiting the intrinsic parallelism that exist in the MPL algorithm. The proposed PA-FA resistant algorithm is presented below in two formulations, ME for RSA and SM for ECC schemes.
FA-PA Montgomery ME algorithm for RSA primitives
Input: c, B, B-1, e = (1, et-2,...e0) e Z* where n is the public modulus Output: (s0, s1, s2, s4) = (Be ? ce mod n, Be+1 ? ce+1 mod n, B2 ? c2‘ mod n, B-e
Initialization: T = R2 mod n, s0 = s1 = bR = B ? R mod n, s3 = s4 = s5 = bR-1 = B-1 ? R mod n, where R = 2j+2
- 1. TR = T ? c ? R-1 mod n
- 2. s2 = bR ? TR ? R-1 mod n
- 3. For i = 0 to t — 1
- (a) If ei = 1 then
s0 = s0 ? s2 ? R-1 mod n, s4 = s4 ? s3 ? R-1 mod n else
s1 = s1 ? s2 ? R-1 mod n, s5 = s5 ? s3 ? R-1 mod n
- (b) s2 = s2 ? R-1 mod n, s3 = s| ? R-1 mod n
- 4. s0 = s0 ? b-1 ? R-1 mod n, s1 = s1 ? c ? R-1 mod n
s2 = s2 ? 1 ? R-1 mod n, s4 = s4 ? b ? R-1 mod n
5. If (values of i, e are not modified and s0 ? s1 ? R-1 mod n = s2 ? 1 ? R-1 mod n)
then return s0, s1, s2, s4 else return error
The above algorithm can be used for non CRT RSA or as a building block for CRT RSA primitive. It employs as inputs the message c, the random number B and its multiplicative inverse B-1, the public modulus n and the exponent e. Note that ei corresponds to the i -th bit of e and that j is the bit length of the modulus n. We assume that the multiplicative inverse of B exists, meaning that gcd(B, n) = 1 (B and n are relatively prime). Possible fault injection attack can be detected by checking s0 ? s1 ? R-1modn = s2 ? R-1 mod n (Z* MPL coherency check). If no fault is injected, the above equation is always true.3 The exponentiation result can be found after fault detection by performing s0 ? s4 mod n = Be ? ce ? B-e mod n = ce mod n.
FA-PA SM algorithm for ECC primitives Input: P, B, B-1 e E(F), e = (1, et-2, ...e0) e F
Output: (50, 51, 52, 54) = (e ? (B + P), (e + 1) ? (B + P), 2t ? (B + P), (-e) ? B) Initialization: 50 = 51 = B, s3 = s4 = s5 = —B
- 1. 52 = B + P
- 2. For i = 0 to t - 1
- (a) If ei = 1 then
- 50 = 50 + 52,
- 54 = 54 + 53 else
- 51 = 51 + 52,
- 55 = 55 + 53
- (b) 52 = 2 ? 52, 53 = 2 ? 53
- 3Note that e is logical NOT of e and that e + e = 2t - 1.
- 3. So = So - B, Si = Si + P S4 = S4 + B
- 4. If (values of i, e are not modified and S0 + S1 = S2) then return S0, S1y S2, S4 else return error
The above algorithm can be applied to any EC type (Wierstrass, Hessian, Montgomery, Edwards curves etc.) under any coordinate system (affine, projective, mixed). It employs as inputs the base point P, a random point B and its additive inverse B-1 = -B, along with the scalar e. Note that ei corresponds to the i-th bit of e and that j is the bit length of all involved finite field elements. Similar to its ME
version, possible fault injection attack can be detected by evaluating the E (F) MPL
coherence check S0 + S1 = S2. If no fault is injected, the above equation is always true and only then can the exponentiation result be released (after fault detection) by performing S0 + S4 calculation.