Fault Injection and Key Retrieval Experiments on an Evaluation Board - Fault Analysis in Cryptography - page 314

18.5.2 Boneh et al.'s Attack Against CRT-Based RSA

Before introducing Boneh et al.'s attack against CRT-based RSA, we review the
security of RSA against side-channel attacks. First of all, all the CRT-based RSA
modules are potentially vulnerable to Boneh et al.'s attack with one fault injection.
The attacker can easily distinguish the CRT-based modules from others by conduct-
ing a simple power analysis (SPA) on a power consumption trace (as described in
Chap. 2 ). An attacker can also distinguish whether or not the LR or RL binary RSA
module is used using SPA. In the case of the LR or RL binary RSA module, the
attacker can retrieve a private key bit by bit using SPA. If the target device is not
the LR or RL binary RSA module, the attacker can conduct a safe-error attack to
retrieve the key if the dummy operations are involved in the exponentiation. We first
introduce Boneh et al.'s attack in this subsection, and then we describe safe-error
attacks in the next subsection.
Boneh et al. proposed a fault analysis attack against the CRT-based RSA
implementations [56]. This attack can recover a private key using one pair of correct
and faulty outputs. Without loss of generality, suppose a fault occurs only during
the computation of one of two modular exponentiations using the CRT, but no fault
occurs during the other computation of the modular exponentiation. Then, the public
modulus can be easily factored by calculating the greatest common divisor of the
difference between the correct and faulty outputs and the public modulus.
As mentioned above, SPA based on a power trace can help an attacker to identify
whether or not the CRT is used. This indicates that an attacker can find an appropriate
timing of fault injection. For example, Fig. 18.10 shows the power consumption of
a CRT-based LR binary RSA module with dummy multiplication. The power trace
shown in Fig. 18.10 can be divided into two parts, denoted by periods A and B. We
can guess that periods A and B of the power consumption correspond to the two
exponentiations required to compute the CRT algorithm, i.e. C p = y d mod p and

y d C q = mod q , where y is output, p and q are the prime numbers, and d is the

secret key.
By following the experimental results of the fault injection in Sect. 18.4.2 ,we
inject a fault at any timing during the computation corresponding to the period A
shown in Fig. 18.10 . We then try to factor the public modulus and retrieve two primes
and the secret key with one pair of correct and faulty outputs. For example, Table 18.6
shows the actual values in the experiments and the secret values calculated using the
above attack method in the case of a CRT-based LR binary method with the dummy
multiplication module. In the same way, we can retrieve the private key from CRT-
based RSA modules implemented on the LSI.