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