Cryptography Reference
In-Depth Information
Table 3.
Intermediates of a Montgomery Powering ladder with a skipped squaring
instruction while
d
i
= 0 was processed
Step
R
0
R
1
Quotient
m
d
L
m
d
L
+1
after
d
L
m
m
d
L
m
2
·d
L
+1
m
d
L
+1
after
d
i
(
m
d
L
)
2
m
3
·d
L
+1
m
d
L
+1
next bit
d
i
+1
=0
m
3
·d
L
+1
m
4
·d
L
+2
m
d
L
+1
d
i
+1
=1
m
(2
i
−d
T
)
·d
L
+(2
d
L
+1)
·d
T
Erroneous Output
The same equations can be set up for a skipped multiplication:
⎧
⎨
m
1
−d
l
·
(1
−
2
i
+1
·d
l
·e
)
(mod
n
)
for
d
i
=0
S
e
=
⎩
m
(2+
d
L
)
·
(1
−
2
i
+1
·e·
(1+
d
L
))
(mod
n
)for
d
i
=1
.
Hence, a Montgomery powering ladder can be attacked by iteratively skipping
either squarings or multiplications and calculating the expected values. If they
do not match, the fault was not injected in the intended way.
Note that the attack works analogously starting from the least-significant bits
of the exponent. Furthermore, the attack can be applied to algorithms that are
based on ECC. Moreover, for an ECDSA implementation, guessing a block of
several bits for each ephemeral key and building a lattice is also possible, like it
is done in [6] for a double-and-add algorithm.
6 Attack on a Blinded Implementation
In order to provide a side-channel secure implementation, Fumaroli and Vigilant
proposed a blinded version of the Montgomery ladder [8]. Their suggestion also
includes a signature for preventing an adversary from tampering with the loop
counter. In this section, we assume the same fault model as in the previous
one. The only difference is that a precise fault injection is required. On the one
hand, each fault that is injected into only one operation i.e. the squaring or
the multiplication is not detected by the checksum. On the other hand, such
a fault produces an unpredictable output, since a part of the random mask is
still included in the return value. This makes a direct guessing of bit chunks
as in the previous attacks impossible. But there is still one bit of exploitable
information left in the output, namely if the result is a quadratic residue. More
precisely, we can compute the Jacobi symbol of the result, which indicates a
quadratic non-residue if it is negative
3
. A schematic view of the attack on a
blinded implementation is given in Algorithm 3.
3
Note that a positive result does not imply a quadratic residue.
Search WWH ::
Custom Search