Cryptography Reference
In-Depth Information
2
112
keys, would still make the search far from feasible in practice. Nevertheless,
the existence of such an attack would reveal a weakness in the cipher that might
lead it to be broken sooner than expected and, as it is often said in cryptographic
circles,
attacks never get worse, they only get better
. For these reasons a cipher for
which shortcut attacks significantly more efficient than exhaustive search are known,
is regarded as broken.
In the design of AES, the number of rounds was determined by considering the
maximum number of rounds for which shortcut attacks were found [62]. For reduced
versions of more than six rounds no shortcut attacks were known and the designers
added four rounds more as a security margin. There are several facts that suggest that
this is, in fact, a conservative approach. As mentioned in [62], two rounds of AES
provide full diffusion in the sense that every state bit depends on all the state bits
two rounds before, and, moreover, a change in one state bit is likely to affect half
of the state bits two rounds later. The number of rounds chosen also makes it much
more difficult to devise successful versions of several known attacks such as linear
cryptanalysis and differential cryptanalysis. For AES versions with a key longer than
128bits, the number of rounds was raised by one for every additional 32 bits in the
key. We shall not go into the details and refer the reader to [62] instead.
A basic characteristic of the design philosophy that led to the AES algorithm is, as
mentioned in [62],
simplicity
. This makes it possible to give a one-page description
of AES as H.W. Lenstra, Jr. did [126] (assuming that a little algebraic background is
known). This simplicity applies, in particular, to the S-box which, as we have seen,
was transparently built using the algebraic structure of
F
2
8
. On the one hand, this
leaves no ground for the suspicion that the S-box might contain a secret trapdoor—as
was suspected by some people in the case of the DES S-boxes—and, on the other
hand, the use of the highly non-linear inversion function of
F
2
8
, complemented with
the affine map we have described, aims at making the system resistant to linear
and differential cryptanalysis. According to present knowledge it seems that AES is
indeed resistant to these attacks.
The remainingAES operations are also very simple.
ShiftRows
has the purpose
of making the algorithm resistant to certain specific attacks and
MixColumns
pro-
duces diffusion among the state bytes, as the change of one byte produces a change
in the four output bytes in the same column of the state. The key schedule also uses
the S-box to produce a “non-linear mixture” of the key bits with the purpose, among
other things, of obtaining resistance against related-key attacks (defined below) and
attacks in which the key is partially known by the cryptanalyst.
The algebraic simplicity of AES's design led some critics to manifest their skep-
ticism or their doubts regarding the security of the algorithm but so far these doubts
have not been vindicated by successful attacks exploiting the algebraic structure
of the cipher. In 2002, an 'algebraic attack' called the
XSL attack
, based on the
description of AES by means of a system of quadratic equations, was announced
by N. Courtois and J. Pieprzyk in [56], purporting to lead to a shortcut attack on
the 256-bit version of AES. This attack, whose complexity analysis is heuristic, was
received with considerable skepticism by the cryptographic community, and several
cryptographers expressed their conviction that the attack as originally presented is
