Cryptography Reference
In-Depth Information
is appropriate to point out explicitly that there is no known proof that this cipher is
a pseudo-random permutation, not even a conditional proof based on some simpler
hardness hypothesis. This is not a peculiarity of AES and the same can be said of all
the block ciphers that are efficient enough to be used in practice. Thus a block cipher
like AES has a somewhat different status than, say, the Blum-Blum-Shub PRG in
that the security of the latter reduces to the hardness of the factorization problem,
which seems simpler and hence better understood than the problem whether AES is
distinguishable from a random permutation. Moreover, there is another perhaps less
important but more quantitative difference: while AES was only introduced in 1998
and standardized in 2001 by the United States National Institute of Standards and
Technology (NIST), the factorization problem has been studied for a longer time and
in different contexts by the scientific community.
AES has been intensively studied and submitted to cryptanalytic attacks since
it was introduced and, so far, the only successful practical attacks against its full
version are so-called
side-channel attacks
that apply to specific implementations,
which are based on physical information obtained from these implementations. We
will mention below other recent attacks that show that AES deviates slightly from
the ideal behavior but, for now, the hypothesis that it behaves as a pseudo-random
permutation for most practical purposes is still reasonable.
4.2.1 The Data Encryption Standard
Before going into the details of AES, it is also appropriate to make a brief com-
ment on its predecessor: the
Data Encryption Standard
(DES). The block cipher that
would ultimately become DES was developed by an IBM team led by Horst Feistel
in the 1970s, under the name of
Lucifer
. Then, in 1973, an unprecedented event in
the history of cryptography happened: the National Bureau of Standards (NBS, the
US Government office that would later become NIST) made a request for a cipher
meeting strict design criteria that would serve as a Government standard for encrypt-
ing unclassified but sensitive information. After none of the initial candidates was
deemed to be suitable, there was a second request in 1974 and Lucifer was submitted
by the IBM team. The public request and the idea of making the selected algorithm a
public standard were a departure from the historical development of cryptography in
which encryption schemes were secretly developed and maintained. Thus this event
can be regarded as the first implicit but clear endorsement of Kerckhoffs' principle
by a Government body. In 1977 the algorithmwas approved as a Federal Information
Processing Standard (FIPS) under the name of the Data Encryption Standard.
In the following years DES was intensely examined and attacked but no relevant
weaknesses were found and the best
practical
attack against it is still a brute-force
search. DES has a block length of 64 and the key size is 56 bits so that, while
searching the 2
56
-bit key space was certainly out of reach for ordinary people in the
mid-1970s, it already seemed possible that a dedicated machine could be built by a
large organization—for instance, by a Government or by the NSA (the US National
Security Agency)—that would be able to successfully complete the attack. Other
