Cryptography Reference
In-Depth Information
implementations, an attacker predicts, under some guess about a key byte, the series—
one value for each power curve—of intermediate data manipulated during the AES
computation. The difference with this classical scheme is that the targeted interme-
diate data is not the output of a first round S-box, but rather the random value by
which this S-box is masked. Provided the value of this random mask can be predicted,
under a key guess, for each execution, a CPA can be performed which will show a
correlation peak for the correct guess at each instant the mask is manipulated. The
need to identify, up to the corresponding key byte, the series of values taken by some
random mask is precisely the reason why the passive part of the attack is preceded
by an active phase which identifies the random series by means of a collision fault
analysis.
As often, the target of this CFA is an output byte of the first
AddRoundKey
which
is forced to zero by a fault. In the present implementation the plaintext
M
and the key
K
have been respectively masked, before they are XORed together, by two 16-byte
randoms
rm
and
rk
respectively. Iteration
i
of the
AddRoundKey
thus computes
(
rk
i
being the random value
used to mask the
i
th S-box in the first round. As forcing to zero this XOR output is
equivalent to introducing a differential equal to
m
i
⊕
rm
i
)
⊕
(
k
i
⊕
rk
i
)
=
(
m
i
⊕
k
i
)
⊕
r
i
with
r
i
=
rm
i
⊕
δ
=
m
i
⊕
k
i
⊕
r
i
, the attacker is able
to identify
k
i
⊕
r
i
, which is precisely the value for the
i
th plaintext byte that produces
a collision with the faulty ciphertext. Thus, for each faulty execution, the attacker
identifies the value
k
i
⊕
r
i
by means of a CFA, and stores the corresponding power
curve. When sufficiently many
k
i
⊕
r
i
values and corresponding curves have been
obtained, it is possible to perform a CPA where the series of
r
i
is predicted by simply
guessing
k
i
. On average, 126 faults are enough to collect traces with 100 different
r
i
values, while 1,568 are required to perform the CPA with all 256 occurrences.
Note that this attack is applicable even if the 16 XOR operations are computed in a
random order. In that case the attacker has to search for the colliding ciphertext in an
extended set of 2
12
plaintexts where the input byte to modify can be in any position.
The plaintext producing the collision automatically informs the attacker about the
index
i
of the XOR corrupted by the fault. The attack strategy is slightly different
since the different sets of power curves for all possible indices must be collected at
the same time rather than successively.
The attack described above does not apply in the case where the computation
verification countermeasure is implemented since no corrupted ciphertext is then
given to the attacker. In that case it is still possible to adapt the attack by preferring
an IFA strategy. When the plaintext byte
m
i
is set to the value
u
, each injected
fault is an attempt to obtain a power curve for which
k
i
⊕
u
. The probability
of success of each attempt is 2
−
8
(or 2
−
12
in the case of random order), so the
expected number of faults required to collect
n
power curves with different masks
for each attacked key byte amounts to 2
12
r
i
=
n
(or 2
16
×
×
n
). This is certainly a
large number of faults, so this attack is hardly practical, but a door is opened here to
break strongly protected implementations which include at the same time: high-order
Boolean masking, computation verification and random order execution.
Note that an interesting and unexpected property of the ineffective fault variant
is that it is easier to perform when a computation verification countermeasure is
