Cryptography Reference
In-Depth Information
5.4.1 Parity-Based Countermeasures
Parity-based schemes use linear codes to ensure the integrity of the AES state. Thus,
the appended bits are a linear sum (over GF(2)) of the state. For instance, one option
would be to XOR all bytes of a column together and to store them as parity. Thus,
the new, protected state would consist of 16 data bytes and four parity bytes.
As actually three of the four AES round operations are also linear over GF(2),
they are compatible with linear codes. In [212], the authors use this property to
achieve a high detection rate for these operations. However, the AES also consists
of the SubBytes operation, which is nonlinear. As a consequence, it is impossible to
efficiently protect the whole state with such parities during all four operations.
In principle, there are two solutions to this problem. The first one protects each
byte with a single parity during all four operations. The second solution is to use
different protection schemes for linear and nonlinear operations.
The single parity approach was pursued in [34, 424]. There, the authors implement
the SubBytes operation with lookup tables which consist of 256 nine-bit entries. The
parity of each entry is the sum of the input and the output parities. We denote
x
as the input and
p
(
)
x
as the input parity. Analogously,
y
denotes the output, which
can be derived as
y
=
SubBytes
(
x
)
, and
p
(
y
)
is the corresponding output parity.
The parity which is stored as the ninth bit is thus
. Hence, during the
SubBytes operation,
x
is replaced by
y
from the lookup table and the new parity is
calculated as
p
(
p
(
x
)
+
p
(
y
))
. It can be checked that only a valid input
can result in a valid output. Alternatively, it is possible to use a lookup table with
512 entries where only 256 lead to a valid output.
A similar approach can be pursued for hardware implementations that do not use
lookup tables. In [220], it is shown how the S-Box can be realized as a pure matrix
operation. Such an implementation is more expensive than for instance a composite
field realization, but it allows us to reduce the circuit to one output bit. This is then
equal to calculating the parity for the S-Box.
Although the last two single-bit approaches seem to be very similar, there is a big
difference, namely that the first one incorporates the old parity in the calculation of
the new one. If this is not the case, that is, if a new parity is calculated from the plain
data only and the old parity is discarded, it has to be ensured that the operation is
preceded by a check which is still active during the operation. Otherwise it would
be possible to manipulate the input data without violating any checks as the parities
would be calculated from the very same erroneous input.
The second solution to the problem is to split the protection between the linear
and the nonlinear parts. In order to provide continuous protection, the methods for
both parts have to be interleaved. Otherwise, the interconnection between the parts
would be unprotected and an easy target for the adversary. For the protection of the
nonlinear part, i.e. the S-Box, several approaches have been proposed. A possible
solution is to split a tower field-based S-Box into five parts [221]. Each part can now
be equipped with a parity. Another possibility is to protect the affine transformation of
SubBytes together with the linear part. This leaves only the inversion to be protected,
(
x
)
+
(
p
(
x
)
+
p
(
y
))
=
p
(
y
)
