Cryptography Reference
In-Depth Information
3.1 Introduction to DES
In 1972 a mildly revolutionary act was performed by the US National Bureau of
Standards (NBS), which is now called
National Institute of Standards and Tech-
nology (NIST)
: the NBS initiated a request for proposals for a standardized cipher
in the USA. The idea was to find a single secure cryptographic algorithm which
could be used for a variety of applications. Up to this point in time governments had
always considered cryptography, and in particular cryptanalysis, so crucial for na-
tional security that it had to be kept secret. However, by the early 1970s the demand
for encryption for commercial applications such as banking had become so pressing
that it could not be ignored without economic consequences.
The NBS received the most promising candidate in 1974 from a team of cryp-
tographers working at IBM. The algorithm IBM submitted was based on the cipher
Lucifer
. Lucifer was a family of ciphers developed by Horst Feistel in the late 1960s,
and was one of the first instances of block ciphers operating on digital data. Lucifer
is a Feistel cipher which encrypts blocks of 64 bits using a key size of 128 bits.
In order to investigate the security of the submitted ciphers, the NBS requested the
help of the
National Security Agency (NSA)
, which did not even admit its existence
at that point in time. It seems certain that the NSA influenced changes to the cipher,
which was rechristened DES. One of the changes that occurred was that DES is
specifically designed to withstand differential cryptanalysis, an attack not known to
the public until 1990. It is not clear whether the IBM team developed the knowl-
edge about differential cryptanalysis by themselves or whether they were guided by
the NSA. Allegedly, the NSA also convinced IBM to reduce the Lucifer key length
of 128 bit to 56 bit, which made the cipher much more vulnerable to brute-force
attacks.
The NSA involvement worried some people because it was feared that a secret
trapdoor, i.e., a mathematical property with which DES could be broken but which is
only known to NSA, might have been the real reason for the modifications. Another
major complaint was the reduction of the key size. Some people conjectured that
the NSA would be able to search through a key space of 2
56
, thus breaking it by
brute-force. In later decades, most of these concerns turned out to be unfounded.
Section 3.5 provides more information about real and perceived security weaknesses
of DES.
Despite of all the criticism and concerns, in 1977 the NBS finally released all
specifications of the modified IBM cipher as the
Data Encryption Standard (FIPS
PUB 46)
to the public. Even though the cipher is described down to the bit level in
the standard, the motivation for parts of the DES design (the so-called design crite-
ria), especially the choice of the substitution boxes, were never officially released.
With the rapid increase in personal computers in the early 1980s and all specifica-
tions of DES being publicly available, it become easier to analyze the inner structure
of the cipher. During this period, the civilian cryptography research community also
grew and DES underwent major scrutiny. However, no serious weaknesses were
found until 1990. Originally, DES was only standardized for 10 years, until 1987.
Due to the wide use of DES and the lack of security weaknesses, the NIST reaf-
