DES, Breaking DES, and DES Variants

May 19th, 2014 by Rossy Guide

History of Data Encryption Standard (DES):

The origins of DES go back to the early 1970s. In 1972, after concluding a study on the US government’s computer security needs, the US standards body NBS – now named NIST — identified a need for a government-wide standard for encrypting unclassified, sensitive information. Accordingly, on 15 May 1973, after consulting with the NSA, NBS solicited proposals for a cipher that would meet rigorous design criteria. None of the submissions, however, turned out to be suitable. A second request was issued on 27 August 1974. The team at IBM involved in cipher design and analysis included Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, and Bryant Tuckerman.

The National Security Agency (NSA) assisted with the cryptographic algorithm evaluation processes, and in 1973, submission invitations were posted in the Federal Register. However, the submissions were unacceptable. In 1974, a second invitation was posted, which resulted in a submission from IBM. In 1975, technical specifications were published for comments in the Federal Register, and analysis and review commenced. In 1977, NBS issued the algorithm, i.e., DES, as Federal Information Processing Standards (FIPS) 46.

Shortly thereafter, the U.S. Department of Defense (DoD) implemented DES. Specifications are outlined in FIPS publication 46-3, FIPS 81, ANSI X3.92 and ANSI X3.106. For security reasons, the U.S. government has never authorized exports of this encryption software. There are at least 72 quadrillion DES key possibilities. In 1993, NIST recertified DES, and the Advanced Encryption Standard (AES) became its unofficial replacement.

What is this?

The data encryption standard (DES) is a common standard for data encryption and a form of secret key cryptography (SKC), which uses only one key for encryption and decryption. Public key cryptography (PKC) uses two keys, i.e., one for encryption and one for decryption.

Breaking DES:

Started 2006 with a third party scientific publication achieving a throughout of more than 65 billion keys per second using Xilinx Spartan-3 1000 FPGAs on a SciEngines COPACOBANA. SciEngines reported on July 15th 2008 to break DES in an average time of a single day using a setup of COPACOBANA.

o DES was standardized 1975, and already 1977 there was an estimate that a machine to break it would cost $20M (1977 dollars)
o DES was recertified in 1992 despite growing concerns
o One can use distributed computing, specialized hardware, or nowadays, cheap FPGAs
o The DES challenge in 1997 was broken in five months (distributed computation) having searched 25% of the key space (1998: 39 days, 85%)
o 1998: EFF DES cracker, parallelized, $200k, 4.5 days (on average)

DES variants:

DES also supports various modes to improve its security efficiency. DES also has two variants – 2DES and 3DES. DES still has the Man-In-Middle attack problem. A comparative analysis defined that 3-DES provides more security but memory usage of DES is less than 3-DES.

Double DES:

 

 

 

 

 

 

Double DES has a 112-bit key and enciphers blocks of 64 bits. DES is not a group; i.e., E(k2, E(k, p)) is not equivalent to DES encryption using a single key. Intuitively, double encryption should double the size of the key space. But, that is not the case with DES.

Triple DES – 3DES:

3DES was developed in 1999 by IBM – by a team led by Walter Tuchman. 3DES prevents a meet-in-the-middle attack. 3DES has a 168-bit key and enciphers blocks of 64 bits. 3DES effectively has 112-bit security. 3DES can be done with 2 or 3 keys.

 

 

 

 

 

3-key encryption

 

E (k3, D (k2, E (k1, p)))

 

2-key encryption

 

E (k1, D (k2, E (k1, p)))

 

One reason might be that by taking k2=k1; 2-key, 3DES becomes single DES with key k1. 3DES can communicate with single DES.

 

DES-X:

 

In cryptography, DES-X (or DESX) is a variant on the DES (Data Encryption Standard) symmetric-key block cipher intended to increase the complexity of a brute force attack using a technique called key whitening.

 

The original DES algorithm was specified in 1976 with a 56-bit key size: 256 possibilities for the key. There was criticism that an exhaustive search might be within the capabilities of large governments, particularly the United States’ National Security Agency (NSA). One scheme to increase the key size of DES without substantially altering the algorithm was DES-X, proposed by Ron Rivest in May 1984. DES-X augments DES by XORing an extra 64 bits of key (K1) to the plaintext before applying DES, and then XORing another 64 bits of key (K2) after the encryption:

 

 

The key size is thereby increased to 56 + (2 × 64) = 184 bits.

 

Leave a Reply