Jump to content

Data Encryption Standard

From Alfawiki
Data Encryption Standard (DES)
Company typeEncryption algorithm
IndustryCryptography, Information security
Founded1973
FounderIBM
Headquarters
United States
ProductsSymmetric-key block cipher algorithm

The Data Encryption Standard (DES) represents a symmetric-key algorithm designed for the encryption of digital information. Although its 56-bit key length no longer meets contemporary security requirements, DES played a pivotal role in shaping the evolution of cryptographic techniques.

Originating in the early 1970s at IBM, DES was based on an earlier design by Horst Feistel. It was proposed to the National Bureau of Standards (NBS) as a means to safeguard sensitive but unclassified government data. Following consultations with the NSA, NBS adopted a slightly altered version in 1976—one that enhanced resistance to differential cryptanalysis while introducing vulnerabilities to brute-force attacks—and officially released it as a Federal Information Processing Standard (FIPS) in 1977.

The endorsement by the NSA facilitated widespread international implementation and academic evaluation of DES. However, concerns emerged due to certain confidential design aspects, its relatively short key length, and the NSA's involvement, which led to speculation about potential backdoors. The NSA-engineered S-boxes mitigated a known weakness (differential cryptanalysis) but simultaneously reduced the effective key size. This scrutiny contributed significantly to advancing the modern theories of block cipher design and cryptanalysis.

Currently, DES's 56-bit key is considered inadequate; notably, in January 1999, distributed.net together with the Electronic Frontier Foundation successfully decrypted a DES key in less than a day (see ). While some theoretical flaws exist, they are largely impractical for exploitation. The NIST has since withdrawn DES as an official standard. To improve security, a variant known as Triple DES was introduced but is also now regarded as insecure. The Advanced Encryption Standard (AES) has replaced DES as the preferred encryption standard.

Certain references distinguish between the DES standard and its foundational algorithm, referring to the latter as the DEA (Data Encryption Algorithm).

History

The inception of DES traces back to 1972 when a study by the National Bureau of Standards recognized the necessity for a unified government standard to encrypt sensitive but unclassified information.

That same year, engineer Mohamed Atalla established Atalla Corporation and created the first hardware security module (HSM), named the "Atalla Box," which was commercialized in 1973. This device protected offline systems using a PIN-generating key mechanism and achieved notable commercial success. The dominance of Atalla in this market segment concerned banks and credit card companies, which propelled efforts toward establishing an international encryption standard. Atalla emerged as an early competitor to IBM within banking security and influenced IBM personnel involved in developing DES. Subsequently, the IBM 3624 incorporated a comparable PIN verification method.

On 15 May 1973, after engaging with the NSA, NBS issued a call for cipher proposals that met rigorous specifications; however, none met their requirements initially. A subsequent solicitation on 27 August 1974 resulted in IBM submitting a suitable candidate—a cipher crafted between 1973 and 1974 rooted in Horst Feistel’s earlier Lucifer algorithm. The IBM development team included Feistel himself along with Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman.

NSA's role in the development

On March 17, 1975, the draft version of DES was released in the Federal Register, soliciting feedback from the public and organizing two workshops the following year. Critics such as Martin Hellman and Whitfield Diffie expressed concerns about the reduced key length and the secretive "S-boxes", suspecting that the NSA had influenced the design to weaken the cipher for intelligence purposes.[1]Cite error: The opening <ref> tag is malformed or has a bad name Alan Konheim, one of DES's creators, remarked, "We sent the S-boxes off to Washington. They returned completely altered."Cite error: The opening <ref> tag is malformed or has a bad name

The United States Senate Select Committee on Intelligence conducted an inquiry into NSA’s involvement. Their 1978 report stated:

Yet it also concluded:


Walter Tuchman from IBM declared, "All DES development occurred solely within IBM... The NSA did not impose any wiring decisions!"Cite error: The opening <ref> tag is malformed or has a bad name

On the other hand, a declassified NSA document reveals:

and


Fears regarding concealed weaknesses in the S-boxes eased in 1990 when Eli Biham and Adi Shamir publicly disclosed differential cryptanalysis, demonstrating that DES’s S-boxes were stronger than arbitrary ones—suggesting IBM's prior awareness of this technique. Don Coppersmith later disclosed the original design principles behind the S-boxes.Cite error: The opening <ref> tag is malformed or has a bad name According to Steven Levy, IBM researchers had discovered differential cryptanalysis in 1974 but kept it confidential at NSA’s request for national security reasons.[2] Walter Tuchman confirmed that strict secrecy was maintained over related documents.[2] Bruce Schneier observed that it took nearly twenty years for the academic community to recognize that NSA’s modifications actually improved DES’s security.[3]

Adoption as a standard

Despite ongoing objections, DES was officially adopted as a federal standard in November 1976 and formally published on January 15, 1977 as FIPS PUB 46, authorized for use with all unclassified data. The standard was reaffirmed in 1983, updated in 1988 (FIPS-46-1), revised again in 1993 (FIPS-46-2), and further amended in 1999 (FIPS-46-3), which introduced "Triple DES". On May 26, 2002, DES was replaced by the Advanced Encryption Standard (AES) following an open competition. FIPS 46-3 was officially withdrawn on May 19, 2005; however, NIST continues to approve Triple DES for protecting sensitive government information through the year 2030.

DES is also incorporated in ANSI X3.92 (now ANSI INCITS 92), NIST SP 800-67, and ISO/IEC 18033-3 as part of TDEA.

While linear cryptanalysis emerged in 1994, it was the Electronic Frontier Foundation's DES cracker built in 1998 that demonstrated practical weaknesses in DES, highlighting the necessity for newer encryption methods.

The release of DES significantly stimulated both academic research and commercial interest in cryptography. According to NIST,

DES "served as a catalyst" for non-military encryption studies. During the 1970s, cryptography was largely confined to military applications with minimal scholarly focus. Today, numerous academic programs and private sector information security companies exist. A generation of cryptanalysts gained valuable experience through analyzing DES. As cryptographer Bruce Schneier stated, "DES did more to energize cryptanalysis than any other event." Much of the open literature on cryptography throughout the 1970s and 1980s centered on DES, which remains a fundamental reference point for assessing symmetric key algorithms.

Timeline

Date Year Event
15 May 1973 NBS issues its first call for a standardized encryption algorithm
27 August 1974 NBS releases a second solicitation for encryption algorithm proposals
17 March 1975 DES is published in the Federal Register for public feedback
August 1976 The inaugural DES workshop takes place
September 1976 Second workshop focuses on the mathematical principles behind DES
November 1976 Official approval of DES as a standard is granted
15 January 1977 DES formally published as FIPS standard FIPS PUB 46
June 1977 Diffie and Hellman assert that DES can be compromised through brute force attacks
1983 First reaffirmation of DES as a standard occurs
1986 HBO adopts Videocipher II, a satellite TV scrambling system utilizing DES
22 January 1988 DES reaffirmed as FIPS 46-1, replacing FIPS PUB 46
July 1991 Biham and Shamir rediscover differential cryptanalysis and apply it to a DES-like cipher
1992 Initial theoretical attack requiring less effort than brute force is reported, though it demands an impractical volume of chosen plaintexts
30 December 1993 DES reaffirmed again as FIPS 46-2
1994 Experimental linear cryptanalysis of DES is conducted for the first time
June 1997 Public demonstration of DES being broken by the DESCHALL Project
July 1998 The EFF's Deep Crack machine cracks a DES key within 56 hours
January 1999 Collaboration between Deep Crack and distributed.net reduces key recovery time to just over 22 hours
25 October 1999 DES reaffirmed as FIPS 46-3; Triple DES recommended for new applications, while single DES is restricted to legacy use
26 November 2001 Advanced Encryption Standard (AES) published under FIPS 197
26 May 2002 AES officially takes effect
26 July 2004 Proposal issued to withdraw FIPS 46-3 and associated standards
19 May 2005 NIST formally withdraws FIPS 46-3
April 
FPGA-based COPACOBANA hardware breaks DES keys in nine days at an estimated $10,000 cost; software optimizations reduce this to approximately six and a half days within one year
Nov. 
The successor to COPACOBANA, named RIVYERA, lowers average key recovery time to less than one day
August 2016 
Open-source hashcat software introduces GPU-accelerated brute forcing of DES; a single Nvidia GTX 1080 Ti (~$1000) recovers keys in about fifteen days, while multi-GPU setups cut this duration under two days
July 
A chosen-plaintext attack employing rainbow tables retrieves a specific DES key in just twenty-five seconds; limited tables are available for download

Description

<imagemap> File:DES-main-network.png|thumb|250px| File:DES-main-network.png#Figure_1 — The complete Feistel architecture of DES rect 0 130 639 229 Initial permutation rect 220 300 421 405 get Feistel function rect 220 594 421 701 get Feistel function rect 220 1037 421 1144 get Feistel function rect 220 1330 421 1437 get Feistel function rect 0 1478 639 1577 Final permutation circle 50 351 26 Exclusive or#XOR operation with key mixing circle 50 647 26 Exclusive or#XOR operation with key mixing circle 50 1090 26 Exclusive or#XOR operation with key mixing circle 50 1383 26 Exclusive or#XOR operation with key mixing </imagemap>

DES represents the original model of a block cipher—a cryptographic algorithm that converts fixed-length plaintext bit blocks into ciphertext blocks of identical size. Operating on blocks of sixty-four bits, it uses a secret key to tailor the encryption process so that only holders of the corresponding key can decrypt the data. While the nominal key length is sixty-four bits, only fifty-six bits are actually employed in encryption; the remaining eight bits serve parity functions and are excluded from the effective key length.

Keys are managed as eight bytes with odd parity bits, following ANSI X3.92-1981 (ANSI INCITS standard number ninety-two from nineteen eighty-one), specifically section three point five:


As with other block ciphers, secure application of DES requires operating within an approved block cipher mode of operation. FIPS-81 outlines several modes compatible with DES, complemented by additional usage recommendations detailed in FIPS-74.

The decryption process mirrors encryption but applies the subkeys in reverse sequence, enabling identical hardware or software implementations to efficiently handle both encryption and decryption tasks.

Overall structure

The algorithm consists of 16 uniform processing stages known as rounds, flanked by initial and final permutation operations called IP and FP, which are inverses of each other. These permutations were designed to optimize data manipulation on 8-bit hardware from the mid-1970s, but they do not contribute to the cryptographic strength of the cipher.

The input block is divided into two 32-bit sections that are processed alternately using the Feistel scheme. This design allows encryption and decryption to employ essentially the same procedure, differing only in the sequence of subkey application. Such symmetry simplifies hardware implementation significantly.

The ⊕ symbol denotes the exclusive-OR operation. The F-function takes one half of the block and combines it with a portion of the key to produce a transformed output, which is then XORed with the other half. Afterward, the two halves swap places before proceeding to the next round. Following the final round, a last swap occurs to preserve the Feistel structure’s inherent symmetry.

The Feistel (F) function

The F-function operates on 32-bit half-blocks through a sequence of four steps:

  1. Expansion: The 32-bit half-block is expanded to 48 bits by an expansion permutation (E), which duplicates selected bits to generate eight segments, each containing six bits.
  2. Key mixing: Each expanded segment undergoes an XOR operation with a 48-bit subkey derived from the primary key via the key schedule. A total of sixteen such subkeys are utilized throughout the rounds.
  3. Substitution: The resulting 48-bit value is divided into eight 6-bit parts, each processed by one of eight S-boxes. Each S-box performs a non-linear transformation, converting six input bits into four output bits according to lookup tables. These S-boxes are essential for DES’s security, as they counteract linear cryptanalysis.
  4. Permutation: The 32 bits output by the S-boxes are rearranged through a fixed permutation known as the P-box, distributing bits so that subsequent rounds’ S-box inputs receive mixed outputs.

Together, these substitution (S-boxes) and permutation (P-box and E-expansion) steps implement the principles of confusion and diffusion, core concepts in secure cipher design identified by Claude Shannon.

Key schedule

Figure 3 illustrates DES’s key schedule, responsible for generating subkeys used during encryption. Initially, Permuted Choice 1 (PC-1) extracts 56 bits from the original 64-bit key; the remaining eight bits function as parity checks or are discarded. The extracted bits are split into two halves of 28 bits each. In every round, both halves undergo left rotations by either one or two bits as dictated by a predefined schedule. Following rotation, Permuted Choice 2 (PC-2) selects 48 bits in total—24 from each half—to form that round’s subkey. These rotations ensure diverse bit usage across subkeys, with individual bits appearing in approximately fourteen out of sixteen subkeys.

During decryption, this key schedule remains unchanged except that subkeys are applied in reverse order.

Pseudocode

Below is a representation of the DES encryption and decryption process expressed in pseudocode:

Security and cryptanalysis

Although DES has been subjected to thorough cryptanalytic scrutiny, brute force remains the most effective practical attack. While several theoretical and minor cryptanalytic vulnerabilities have been identified, they demand infeasibly large amounts of known or chosen plaintext, rendering them largely impractical for real-world exploitation.

Brute-force attack

The fundamental approach to compromising DES involves exhaustive key search, commonly known as brute force. The key length of DES is 56 bits, a reduction from an initial 256-bit design following consultation with the NSA to enable hardware implementation on chips. This limitation significantly constrained its security and motivated the development of alternative encryption standards.

In academic circles, initial proposals for machines capable of breaking DES were expensive and largely conceptual. However, by the late 1990s, practical demonstrations had materialized. For instance, in 1997, RSA Security organized contests offering a $10,000 reward for decrypting DES-encrypted messages; the DESCHALL Project succeeded by leveraging distributed computing resources. Subsequently, in 1998, the Electronic Frontier Foundation (EFF) constructed a dedicated DES-breaking device costing roughly $250,000 that could perform a brute-force key search in just over two days, thereby confirming DES's vulnerability in practical terms.

Further advancements followed in 2006 when researchers at Germany’s Bochum and Kiel universities developed COPACOBANA, a machine built from 120 commercially available FPGAs operating in parallel. Priced around $10,000, COPACOBANA illustrated a significant reduction in hardware costs compared to previous efforts like EFF’s machine, reflecting progress consistent with Moore’s law. SciEngines GmbH, a company spun off from this project, enhanced this technology further: their 2008 iteration—COPACOBANA RIVYERA—employed 128 Spartan-3 5000 FPGAs to reduce the time needed for DES key recovery to less than one day; subsequent models incorporating Spartan-6 LX150 FPGAs achieved even faster performance.

In 2012, David Hulton and Moxie Marlinspike introduced a system utilizing 48 Xilinx Virtex-6 LX240T FPGAs capable of processing 768 gigakeys per second. This setup could exhaustively search the entire DES key space in approximately 26 hours. Although this service was once commercially accessible online, it has been offline since 2024 and appears unlikely to resume operation.

These technological advances highlight the erosion of DES’s security due to improvements in hardware capabilities and parallel processing techniques.

Attacks faster than brute force

There exist three cryptanalytic attacks that can compromise the full 16-round DES algorithm with less effort than brute force: differential cryptanalysis (DC), linear cryptanalysis (LC), and Davies' attack. These methods are primarily theoretical and are generally regarded as impractical for real-world application; thus, they are often classified as certificational weaknesses rather than immediate threats.

  • Differential cryptanalysis, brought back into focus by Eli Biham and Adi Shamir during the late 1980s, had actually been discovered earlier by IBM and NSA researchers but remained classified. Successfully attacking all 16 rounds requires approximately 247 chosen plaintexts. The design of DES explicitly aimed to withstand differential cryptanalysis.
  • Linear cryptanalysis, credited to Mitsuru Matsui, demands about 243 known plaintexts and represents the first experimentally verified cryptanalytic attack on DES. There is no indication that DES was specifically engineered to resist this form of attack. Subsequent improvements—including multiple linear cryptanalysis—have lowered data requirements to near 241. Variants employing chosen plaintext further reduce computational effort to an estimated range between 239 and 241 DES operations.
  • The improved Davies' attack is a technique tailored for DES that originated with Donald Davies in the 1980s and was later refined by Biham and Biryukov (1997). Its most potent variant requires roughly 250 known plaintexts with computational complexity also near 250, achieving about a 51% success probability.

Analyzing attacks on truncated-round versions of DES offers valuable insights into how many rounds are necessary to maintain robust security margins.

Differential-linear cryptanalysis, introduced by Langford and Hellman in 1994, merges differential and linear strategies into a combined approach. An enhanced variant can break a nine-round version of DES using approximately 215.8 chosen plaintexts with time complexity around 229.2.

Minor cryptanalytic characteristics

DES demonstrates the complementation property, expressed as:

<math>E_K(P)=C \iff E_{\overline{K}}(\overline{P})=\overline{C}</math>

where <math>\overline{x}</math> represents the bitwise complement of <math>x.</math> Here, <math>E_K</math> signifies encryption using key <math>K,</math> while <math>P</math> and <math>C</math> correspond to plaintext and ciphertext blocks respectively. This attribute effectively halves the complexity of a brute-force attack under the assumption of a chosen-plaintext attack, and it is also applicable to TDES.

Within DES, there exist four weak keys for which the encryption and decryption operations are equivalent:

<math>E_K(E_K(P)) = P</math> or equivalently <math>E_K = D_K.</math>

Additionally, six pairs of semi-weak keys are known where encryption with one key matches decryption with its paired key:

<math>E_{K_1}(E_{K_2}(P)) = P</math> or <math>E_{K_2} = D_{K_1}.</math>

These keys are rarely selected by chance and pose no practical threat, thus implementations typically avoid them without difficulty.

It has been established that DES does not constitute a group under the composition of its encryption functions. This finding is crucial because if DES formed such a group, applying multiple encryption rounds—such as in Triple DES—would not enhance security, as repeated encryptions would simplify to a single encryption under some key.

Simplified DES

Simplified DES (SDES) was developed as an instructional model to demonstrate fundamental cryptanalytic methods. It adopts the structural design of DES but is simplified enough to permit manual encryption and decryption processes. SDES offers valuable practical experience for comprehending DES and similar block ciphers, facilitating a better grasp of cryptanalysis techniques.

Replacement algorithms

Due to concerns over DES’s security vulnerabilities and its relatively slow performance in software implementations, several alternative block ciphers emerged during the late 1980s and early 1990s. Notable examples include RC5, Blowfish, IDEA, NewDES, SAFER, CAST5, and FEAL. Most maintained DES’s 64-bit block size, allowing them to serve as direct substitutes, often employing key lengths of 64 or 128 bits. In the Soviet Union, the GOST 28147-89 cipher was introduced featuring a 64-bit block size coupled with a 256-bit key; it later saw use within Russia.

Triple DES (3DES) enhanced security by encrypting data three times per block but was eventually deprecated by NIST due to inefficiency and emerging vulnerabilities. Contemporary cryptographic practice favors more robust schemes such as RSA, ECC, and post-quantum algorithms that offer stronger protection against both classical and quantum threats.

The permutations and key scheduling mechanisms within DES are fundamental to its encryption operation but also reveal its inherent security limitations, underscoring the need for more secure alternatives.

Many users transitioned from DES to Triple DES (TDES), which applies DES encryption thrice using either two (2TDES) or three (3TDES) distinct keys, providing sufficient security despite reduced speed. A more efficient variant is DES-X, which increases the effective key length by XORing extra key material before and after the standard DES process. The GDES modification aimed at accelerating encryption but was found vulnerable to differential cryptanalysis.

On January 2, 1997, NIST announced intentions to identify a replacement for DES. Following an international contest in 2001, NIST selected the Advanced Encryption Standard (AES), based on the algorithm known as Rijndael. Other finalists included RC6, Serpent, MARS, and Twofish.

See also

References


External links

  1. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named dh-exh
  2. ↑ 2.0 2.1 Cite error: Invalid <ref> tag; no text was provided for refs named Levy
  3. ↑ Cite error: Invalid <ref> tag; no text was provided for refs named schneier20040927
Retrieved from "https://www.alfawiki.org/index.php?title=Data_Encryption_Standard&oldid=27427"