Cryptography Reference
In-Depth Information
Table 2.1
Number of key hypotheses generated by attacking compressed S-Boxes
Plaintexts
Hypotheses per S-box pair
Hypotheses for the first round key
Whole key space
2
37
.
3
2
45
.
3
1
25.3
2
27
.
4
2
35
.
4
2
10.8
2
19
.
2
2
27
.
2
3
5.29
2
13
.
5
2
21
.
5
4
3.23
Algorithm 2.3:
S-box randomization in random order
Input
: The original S-box table
S
=
(
s
0
,...,
s
63
)
16
The input and output masks
R
∈
(
0
,...,
63
)
and
r
∈
(
0
,...,
15
)
S
Output
: The randomized S-box table
=
(
˜
s
0
,...,
˜
s
63
)
16
1
for
i
←
0
to
63
do
2
s
i
←
s
i
⊕
R
⊕
r
3
end
4
return
S
faults, the whole key space is reduced to 2
35
.
4
keys with compressed S-Boxes instead
of 2
38
.
7
with uncompressed S-Boxes.
Note also that the attack can be further slightly optimized by observing that, based
on the faulty ciphertext, it is possible to identify cases where an S-box entry has been
used only in one of the last two rounds. In these cases, the S-box entry should not be
considered as a candidate for the first round subkey.
A countermeasure for this specific attack is to randomize the order in which the
S-Boxes are randomized. This applies to the order in which the S-Boxes are treated,
and to the order in which the S-box elements are masked. The data masking can be
done as shown in Algorithm 2.3. The counter
i
is XORed with a random number
before being used so the order in which the S-box elements are treated is unknown.
When only the order in which the S-Boxes are treated is randomized, one can
still attack by searching for S-box indices that never change the ciphertext when
modified. If the same S-box index is repeatedly changed, but the ciphertext never
changes after numerous executions with the same plaintext, it can reasonably be
assumed that this index value does not represent a key hypothesis for any part of the
first round key. Faulting 22 times on the same index with no ciphertext modification
ensures a probability of non-detection as small as 0
01. The expected number of
indices that are used for at least one S-box in at least one round is 55
.
5. For each
of them four faults are enough on average to show that this index is used. For the
others the fault must be repeated 22 times. Thus an average of 409 fault injections
are required for each plaintext. Table
2.2
presents the complexity of the resulting
exhaustive search for different numbers of plaintexts.
.
