Fault Attacks on the Montgomery Powering Ladder - Information Security and Cryptology-ICISC 2010 - page 400

Table 2. Fault injection during Montgomery ladder computation

Fault in R 0 Fault in R 1

Step R 0 R 1 R 0 R 1

1 m 1 m

) d L m d L m d L +1 m d L m d L +1 ( ·

z d L +1 m d L

Fault z

m (2 i ·d i + d T ) · ( d L +1) · z 2 i − (2 i ·d i + d T ) m (2 i − (2 i ·d i + d T )) ·d L · z (2 i ·d i + d T ) Output

fault models that are suitable for an attack and show how to proceed in these
cases. Furthermore, we discuss how to mount an attack on blinded versions of
the algorithm.

4 Fault Model: A Guessable Fault

In the first model, we assume that an intermediate variable of an RSA imple-
mentation using the Montgomery powering ladder is modified by a fault at a
known point in time. Furthermore, this fault influences the variable in a way
that the result is within a limited range that can be searched exhaustively.
In order to inject such a fault, an adversary can use a focused laser beam to
flip/set some bits in a register [12]. Another method to cause a fault is to inter-
rupt the loading of a word into a register, e.g. by injecting glitches or spikes [13].
Hence, the size of the fault depends on the word size of the microcontroller. Both
methods can control the point in time when the fault is injected very precisely.
In particular, if fault w is injected into R 0 after processing the exponent bits of
d L (a fault in R 1 leads to similar equations), the intermediate variables ( R 0 ,R 1 )
contain ( m d L ⊕ w, m d L +1 ). As a consequence, the final (erroneous) signature is

S = m (2 i ·d i + d T ) · ( d L +1)

w ) 2 i +1 − (2 i ·d i + d T )

( m d L

· ⊕

(mod n ) .

Since we assume that the fault is injected at the beginning of the computation,
d L is small and hence guessable, while d T is not. However, we can substitute
d T +2 i 2 i +1 · d L :

S = m ( d− 2 i +1 ·d L ) · ( d L +1)

d i = d − ·

w ) 2 i +1 − ( d− 2 i +1 ·d L ) ( m d L ⊕

· (mod n ) .

From this we can eliminate d becauseweknow e and we further know that
ed =1 (mod ϕ ( n )). Raising S to the power of e delivers an expression in which
only w and d L remain unknown:

S e = m (1 − 2 i +1 ·e·d L ) · ( d L +1)

w ) 2 i +1 i·e +2 i +1 ·d L ·e− 1 ( m d L ⊕

· (mod n ) . (1)

Now we can test hypotheses for w and d L . For correctly guessed values equation
(1) must hold.