Cryptography Reference
In-Depth Information
Algorithm 2.2: S-box randomization
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 R s i r
3 end
4 return
S
how to exploit a modification of an S-box entry in both cases, where the index of the
corrupted value is known and unknown to the attacker. 15
2.3.2.1 Modifying Known S-box Values
When all eight S-Boxes are randomized as in Algorithm 2.2 an attacker can precisely
know which S-box entry it is modifying. For some fixed arbitrary plaintext, it is
possible to scan the randomization loop of some attacked S-box, induce a fault at
each successive iteration, and observe whether the ciphertext has been corrupted or
not. This results in the list of indices of all entries that are used for some S-box in one
round or another of this execution. Such list contains an average of 14
255 indices
which can all be taken as possible candidates for the S-box entries used in the first
round. From the relevant bits of the plaintext, each index value can then be turned
into a hypothesis on the S-box first round subkey. The different lists of candidates for
each subkey can be further reduced by repeating the attack with one or more other
plaintexts. The expected number of remaining candidates for the first round key K 1
is 2 30 . 7 (or 2 15 . 4 ) when the attack exploits one plaintext (or two plaintexts), which
results in 2 38 . 7 (or 2 23 . 4 ) candidates for the whole key K .
In practice, embedded implementations of DES are unlikely to have the 512
four-bit S-box values written as separated bytes in memory. To avoid this waste of
memory space, DES S-Boxes are usually compressed by storing the data into four
64-byte tables where the odd-numbered S-Boxes are stored in the high nibbles and
the even-numbered S-Boxes are stored in the low nibbles. 16
The number of key hypotheses generated by this attack against a DES using
compressed S-Boxes is shown in Table 2.1 for different numbers of plaintexts. Since
the number of faults required with two plaintexts when S-Boxes are compressed is
the same as those required with only one plaintext when they are not, one can notice
that the attack is more efficient on compressed S-Boxes. As an example, with 512
.
15 Note that some figures given in [12] happen to be imprecise. The figures we give in the sequel to
this section are borrowed from [92], where they have been more rigorously computed.
16 While there are a few other ways in which the S-box data could be compressed, we do not
consider this as something an attacker must previously know since he can conduct his attack under
all possible compression methods until the correct one is found.
 
Search WWH ::




Custom Search