Fault Attack and Countermeasures

Fault attacks can be injected in various parts of the RSA/ECC implementation including storage elements, control instructions or computation units as a whole. Bellcore researchers introducing FAs in public key systems, have shown that RSA, especially CRT1 RSA, is very vulnerable against fault attacks [21]. Similarly, FAs have been very successful in ECC implementations. There exist various FAs aiming the SM implementation, like C and M safe error attacks where the value of a single bit of the scalar e is changed and it is observed if this action leads to a different point multiplication outcome or not (safe error). There also exist FAs focusing on a weak curve-based fault analysis including invalid base point attacks where by injecting a fault in the SM base point, this point with high probability becomes a point of a weak curve.1 2 This approach can be expanded into invalid curve attacks, where any unknown fault in any part of the hardware implementation (memory, buses, registers etc.) influencing any EC parameter can possibly lead to a transition to a weak curve [22]. By specializing the fault injection process to the x EC point coordinate (as long as the y coordinate is not used), more promising attack results can be provided by transferring SM calculations to a weak twist of the original EC with high probability (twist curve FAs) [23].

Apart from the patented approach of Shamir [24] (Shamir’s trick), early attempts to thwart the Bellcore attack and EC SM fault attacks were based on infective computation [25]. Through this approach, any computational errors introduced by a fault will propagate throughout the computation, “infecting” all intermediate variable thus ensuring that the final result always becomes faulty and appears random and useless to the adversary in the end. After an initial attempt on this concept by Yen in [26], in the case of RSA, insecurities were found by Blomer et al. [27], thus the infective computing approach was enhanced with a fault detection mechanism based on the introduction of public modulus (n) multiplicative masking (BOS scheme). [1] [2]

BOS scheme was insecure in several possible thread models [28], as shown in [29, 30]. More than one fault can be carefully injected, as shown by Kim and Quisquater in [31], in certain parts of the CRT and non-CRT RSA to bypass the fault detection operation as a whole; thus revealing the public modulus or its private factors (KQ scheme). This attack consists of injecting two faults, one during exponentiation and another during fault detection. To prevent such attack, the RSA outcome should be revealed and stored only after fault detection. This attack of more than one fault injections can also be applied to ECC designs to bypass the fault detection mechanism.

In the case of ECCs, similar countermeasure steps where introduced by researchers, including infective computation and fault detection [32]. However, to thwart the transition to weak ECs due to fault injection additional countermeasures could be taken into account, including point validation and EC integrity checks for invalid point and invalid curve (EC parameter) attacks. In general, the fault detection mechanism for both RSA and ECC schemes is focused on a coherency check between intermediate values during ME (RSA) or SM (ECC). This check is usually a mathematical connection between those intermediate values that is retained throughout the computation flow and is disrupted when an fault is injected. A coherency sensitive mechanism can check if the mathematical connection between those values exists or not, thus detecting an attack [33-35].

RSA and ECC implementations are very susceptible to SCA and especially power attacks (PA) especially when such attacks are combined with Fault attacks [36, 37]. Providing protection for FA or PA independently can thwart only one kind of hardware attack while adversaries usually apply a combination of different attack techniques to compromise an RSA/ECC hardware architecture. Combining more than one type of countermeasure as well as adopting and combining well-established resistance principles in an RSA/ECC implementation can achieve long-term SCA- FA resistance against such attacks [33, 34, 38]. However, combining FA and PA resistance approaches may introduce new vulnerabilities that can be exploited to attack the public key implementation system [16, 19, 37, 39, 40] thus reducing the RSA/ECC implementation overall physical attack resistance.

  • [1] Chinese Remainder Theorem.
  • [2] A weak elliptic curve is a curve that can be cryptanalyzed easily.
 
Source
< Prev   CONTENTS   Source   Next >