Exploring the History of DES

Exploring the history of DES

DES is an extremely important block cipher, not just because variants of it are still heavily in use today, but also because it has an exciting and significant history, which we’ll only briefly cover here. This discussion is relevant because many of the issues concerned with the development of DES could arise again in the future.

Milestones in the history of DES

In 1973, the National Bureau of Standards (NBS) in the United States published a call for proposals for an encryption algorithm standard. That was a historic moment since, before this call, cryptography had been something of an obscure art during the 20th century, practiced mainly by military and national security organizations. The NBS recognized the need for a cryptographic algorithm that could protect the increasingly commercial use of computer communications.

Initially, there were no replies, but after a second call in 1974 was issued, IBM submitted an encryption algorithm that they had been developing. The submission of this algorithm and subsequent discussions with the National Security Agency (NSA) resulted in an encryption algorithm being published for public comment in 1975. This algorithm was adopted as a federal standard in 1976 and published as DES in 1977.

The use of DES became mandatory for federal agencies in 1977, and after its adoption in the banking standard ANSI $X_{3.92}$, it found widespread use throughout the international financial industry. Indeed, DES became the de facto global standard encryption algorithm, a status which it held until the establishment of AES. Although DES was predicted to have a 15-year lifespan, the NSA removed its endorsement of DES in 1988. However, the NBS reaffirmed the use of DES in the same year, primarily to appease the financial industry, which relied heavily upon it.

The NBS, now known as the National Institute of Standards and Technology (NIST), finally acknowledged that DES no longer offered adequate cryptographic protection by issuing a call for a new algorithm in 1998. This process resulted in the AES, which we’ll discuss in the next couple of lessons.

Early design criticisms

DES has proved to be a very well-designed block cipher since, to date, there have been no significant cryptanalytic attacks on DES other than exhaustive key search. Some academic breaks have involved techniques known as differential and linear cryptanalysis, but these attacks have not threatened DES in practice.

DES has, however, been subjected to several different design criticisms over the years:

• Secret design criteria: Although the full description of DES, including the round function and key schedule, was published, their design criteria (in other words, why they were chosen to be that way) were not. This resulted in some people becoming suspicious that ‘backdoors’ might exist in which the designers could easily subvert a DES encryption through knowledge of some secret technique. These fears appear to have been unfounded. In particular, the public discovery of differential cryptanalysis in the 1990s revealed that DES design protects against this type of cryptanalytic attack as well. Intriguingly, this implies the designers of DES must have known about this technique long before its public discovery.

• Potentially undesirable keys: One criticism pointed out that specific DES keys are not suitable for use. For example, some keys are described as ‘weak’ because these keys’ encryption and decryption have the same effect. It’s debatable whether this is a problem. In any case, there are only a few keys like these, and one can easily avoid their use.

• Inadequate key length: The main criticism of DES, even in 1975, was that the effective key length of 56 bits was not adequate. Indeed, there were (never-substantiated) accusations that the NSA had influenced the selection of a relatively small effective key length to keep the exhaustive search for a DES key within their capabilities. Whether these claims were valid may never be known. What is true is that 56 bits are inadequate protection today for most applications.

DES key searches

The security analysis of DES, right from the outset, has mainly focused on the difficulty of exhaustively searching for a DES key. To place the subsequent discussion in some perspective, recall our computation of real attack times. Suppose we have a machine consisting of one million processors, each of which can test one million keys per second. How long is it likely to take before we find a DES key during an exhaustive key search? DES effectively has a 56-bit key. A 56-bit key requires $2^{56}$ tests to comb the keyspace. Since $2^{56}$ is approximately equal to $7.2*10^{16}$, and since we can test $10^{6}$ × $10^{6}$ = $10^{12}$ keys every second, a complete search will take:

$$\frac{7.2*10^{16}}{10^{12}} = 7.2*10^{4} seconds$$

In other words, a complete search will take about 20 hours. That means we will probably find the correct key in about half this time, about 10 hours. These are straightforward mathematical facts. The real issue is how likely it is that an attacker has access to a powerful machine to search for a DES key exhaustively. The historical debate about the security of DES has essentially been a debate about the potential availability and cost of powerful computing devices. Some milestones in this debate are summarised in the table below. The details of each of these instances are given below the table.