Cryptography Reference
In-Depth Information
a round. A round consists of type II tables, type III tables and supporting type IV
tables, i.e. four 4-byte input and 4-byte output mappings.
P
i,j
(resp.
Q
i,j
)isthe
composition of two concatenated 4-bits to 4-bits input (resp. output) encodings
and one 8-bits to 8-bits mixing bijection.
P
i,j
and
Q
i,j
cancel each other between
two consecutive rounds (i.e.
Q
i,j
=Inv(
P
r
+1
[0
..
9]).
It was shown that by analyzing a round input/output the non-linear 4-byte
mapping
P
i,j
and
Q
i,j
can be reduced to one where they are ane. Removing
non-linear part requires 2
24
computation steps for each mapping.
To recover the ane mapping
Q
0
),
r ∈
i,j
q
0
where
A
0
is linear and
q
0
is a
constant, it was first shown in [4] that there exists a unique linear mapping
L
and a constant
c
, such that for all
x
0
∈
=
A
0
⊕
GF
(2
8
)
y
i
(
x
0
,
0
,
0
,
0) =
L
(
y
j
(
x
0
,
0
,
0
,
0))
⊕
c
where
y
i
is a function of (
x
0
,x
1
,x
2
,x
3
) defined as follows:
y
i
(
x
0
,x
1
,x
2
,x
3
)=
Q
i
(
α
i,
0
T
0
(
P
0
(
x
0
))
⊕α
i,
1
T
1
(
P
1
(
x
1
))
⊕
α
i,
2
T
2
(
P
2
(
x
2
))
⊕ α
i,
3
T
3
(
P
3
(
x
3
)))
(1)
(
α
i,j
are the coecients of
)andthat(
L, c
)canbedetermined
with a complexity lower than 2
16
by solving an over-defined linear system of
equations, involving 2048 equations and 72 unknowns.
Second, by determining the characteristic polynomial of
L
and knowing the
coecients of
InvMixColumns
operation, it is possible to determine
A
0
with a
time complexity of about 2
24
. From the knowledge of
α
i,j
values, constant
q
0
is
recovered at the same time by setting the four variables in Equation (1) to a zero
value. Billet et al. show that from the knowledge of the linear part of
Q
0
,the
linear parts of
Q
1
,
Q
2
and
Q
3
can be computed with a time complexity of 2
16
for each part. All
Q
i
of a round can be recovered similarly. As
Q
i
=Inv(
P
r
+
i
),
P
r
+
i
is recovered at the same time. Once the mappings are recovered, the bytes
of a subkey round (embedded in the
T
-boxes) can be retrieved. The bytes are
however in a shued order. Nevertheless, computing the
Q
i
for two consecutive
rounds makes it possible to get another shued subkey. Constraints in the AES
key schedule algorithm enable retrieving both subkeys in the correct order as
well as all other round subkeys.
Finally, the complexity for recovering the ane part of the
Q
i
InvSubBytes
is 2
16
+2
24
+
2
24
. The non-ane part of the
Q
i
can be recovered with the same time
complexity of 2
24
. Hence,
P
i
and
Q
i
can be determined in 2
25
steps. The attack
is performed for two consecutive rounds. The total complexity of the attack is
bounded by 2
2
16
3
·
≈
2
25
=2
30
.
·
4
·
4
·
3.2 Michiels et al. Attack
Michiels et al. presented in [14] another type of attack against white-box ci-
phers. They interestingly remarked that the diffusion operator of a block cipher
makes the white-box implementation relatively vulnerable to attacks. The dif-
fusion operator in the case of AES decryption algorithm is represented by the
InvMixColumns
operation. The attack they propose is composed of three steps.
Search WWH ::
Custom Search