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

The observations above allow an iterative attack: Inject an appropriate fault
while the first bits of d are processed. Using the public exponent, the result can
be transferred into a value that depends on the message and a few unknown
bits. Now the hypotheses for the fault and d L can be tested against this value.
A correct hypothesis increases the knowledge about d . The attack is repeated
until the whole exponent is known.
Note that the same attack is possible injecting a fault into R 1 by substituting
R 1 by R 1 ⊕ w in Table 2. If a register that stores either R 0 or R 1 is attacked,

both possibilities have to be checked simultaneously.

5 Fault Model: Skipping an Instruction

Another possible fault model is based on a modification of the program flow.
Instead of manipulating the data directly by flipping bits, an instruction is not
executed. This reduces the overhead generated by guessing the flipped bits, since
only the position of the skipped instruction is required, which depends on the
point in time the fault is injected 2 . Using the public exponent e the same way
as in the previous attack delivers a value which contains only a small part of the
unknown secret exponent. In this way, the whole exponent can be determined
iteratively.
Let m be a message to be signed using the exponent d =[ d L ,d i ,d T ]with
d i the bit that is processed as the squaring is skipped. The resulting equation
depends on d i , because if it is zero, a squaring of R 0 is skipped, while for a one
the squaring of R 1 is left out.
First, assume d i = 0. By skipping the squaring, R 0 stays unchanged and R 1
contains the value m 2 ·d L +1 . This can be seen as skipping d i and changing the
quotient to d L + 1. Together with the last line of Table 2 and d =2 i +1 · d L + d T

this results in:

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

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

⇒

(mod n ) .

Table 3 details the content of the intermediate variables and the quotient for a
skipped squaring of d i = 0. After the quotient between R 0 and R 1 is changed by
the fault, it stays constant for the rest of the computation. For d i =1, R 1 stays
constant and R 0 changes to 2 d L + 1. Together with d =2 i +1 d L +2 i + d T ,we · ·

get:

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

(mod n )

= m 2 i · (1+ d L · (3+2 ·d L )) −d L ·d (mod n )

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

⇒ (mod n ) .

2 In this model, we allow the fault injection to be imprecise, since it is possible to
check whether the fault is exploitable for our attack.