Cryptography Reference
In-Depth Information
Algorithm 3.
Schematic of the Attack
Require:
A device that can be manipulated and uses the blinded Montgomery ladder
to produce faulty signatures
˜
S
.
Ensure:
The exponent
d
=(
d
t−
1
,...,d
0
)
2
that is used by the device.
Set
d
t−
1
= 1 (leading zeros are neglected)
for
i
=
t −
2
downto
0
do
Choose
m ∈
Z
n
with
m
n
=
−
1
Calculate
˜
S
with the
i
th squaring operation skipped
=
−
1
then
d
i
=
d
i
+1
else
d
i
=1
˜
S
n
if
⊕ d
i
+1
end if
end for
return
d
Taking a closer look at the result shows that if a squaring is skipped during
the processing of Algorithm 2, the result
S
is
S
=
R
(2
t
)
2
m
d
with
r
2
t
−
1
+2
i
−
1
·u
·
·
⎧
⎨
d
T
for
d
i
=0
u
=
⎩
2
i
−
d
T
for
d
i
=1and
⎧
⎨
2
i
1+
d
L
−
e
·
·
d
L
·
(1 + 2
·
d
L
)(mod
ϕ
(
n
))
for
d
i
=0
d · e
=
⎩
e
·
2
i
·
(1 +
d
L
·
(3 + 2
·
d
L
))
−
d
L
(mod
ϕ
(
n
)) for
d
i
=1
.
Hence, the result can be split up into an unknown part, which includes the
random mask and another one that depends on the input message, on the ex-
ponent, and of the position of the fault. Raising the resulting
S
to the power
e
cancels the unknown bits of
d
T
out. If the fault is chosen in a way that only
d
i
is
unknown and
d
L
is known, the whole message-dependent part of the signature
depends on the one bit
d
i
. Furthermore, it follows that it directly depends on
this bit, whether the result is a quadratic residue assuming that
m
is a quadratic
non-residue. This is because the remaining part of the random mask is always a
quadratic residue due to its exponent, which is a multiple of two. In detail, if
m
is chosen with a Jacobi symbol
m
n
=
1,
S
is a quadratic non-residue with
−
S
n
=
1, iff
d
is odd. Moreover, whether
d
is even or not depends on the last
−
bit of
d
L
and
d
i
.Since
d
L
is known, the knowledge of the Jacobi symbol of
S
determines
d
i
.Thisisbecause
ϕ
(
n
)isalwaysevenand
d
isalwaysoddinthe
case of RSA. Thus, computing the Jacobi symbol leads to an attack similar to
the one presented by Boreale on square-and-multiply [2]. In contrast, our result
Search WWH ::
Custom Search