Data Encryption Standard (DES)

Data Encryption Standard (DES)

Abdul Wahab

M Sc. Computing

Griffith College Dublin, Ireland.

Abstract

  

The selective application of technological and related procedural safeguards is an important responsibility of every organization in providing sufficient security to its electronic data systems. I explain in this repport the data encryption algorithm that is called Data Encrytion Standards (DES), which uniquely define the mathematical steps required to transform data into a cryptographic cipher and also to transform the cipher back to the original form.

1   Introduction

The Data Encryption Standard (DES) is a block cipher (a form of shared secret encryption) and National Bureau of Standards selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is based on a symmetric-key algorithm which uses a 56-bit key. The algorithm was initially controversial with classified design elements, a relatively short key length, and suspicions about a National Security Agency (NSA) backdoor. DES as a result came under intense academic study which motivated the modern understanding of block ciphers and their cryptanalysis.

     The DES (Data Encryption Standard)  is the most widely used encryption algorithm in the world. For many years, and among many people, "secret code making" and DES have been synonymous. The Electronic Frontier Foundation in creating a $220,000 machine to crack DES-encrypted messages, but DES will live on in government and banking for years to come through a life- extending version called "Triple DES" [3] Triple-DES (3DES) applies DES three times with two keys. That is 112-bit key.

  As the Data Encryption Standard (DES) by adopted the National Security Agency (NSA), NIST as a federal standard on November 23, 1976, they authorized it for securing all sensitive, unclassified government data from unauthorized access and for encrypting information transferred through communications. “Data Encryption Standard,” was published on January 15, 1977 and this became effective six months later the publication. In 1983 and 1988 DES was reaffirmed without significant changes, spanning the first decade of its implementation. In 1993, FIPS 46-1 was reaffirmed as FIPS 46-2 with allowances for software implementation. In 1999, FIPS 46-3 (“Triple DES”) was approved.[2].

        DES works on binary numbers, the 0s and 1s common to digital computers. Each group of four bits makes up a hexadecimal, or base 16, number. e.g Binary "0001" is equal to the hexadecimal number "1", binary "1000" is equal to the hexadecimal number "8", "1001" is equal to the hexadecimal number "9", "1010" is equal to the hexadecimal number "A", and "1111" is equal to the hexadecimal number "F" [3].

      To do the encryption, DES uses "keys" where are also apparently 16 hexadecimal numbers long, or apparently 64 bits long. However, every 8th key bit is ignored in the DES algorithm, so that the effective key size is 56 bits. But, in any case, DES is organized upon the 64 bits (16 hexadecimal digits) round number. [3].

2   Description and Structure

DES is an origenal model of block cipher, i.e  an algorithm that takes a fixed-length string of plaintext bits and transforms it into another ciphertext bitstring of the same length by through a series of complicated operations. The block size is 64 bits. DES customize the transformation by using the key, so that decryption can supposedly only be performed by those who know the particular key used to encrypt. The key ostensibly consists of 64 bits, in which only 56 are actually used by the algorithm and the rest eight bits are used solely for checking parity, which are discarded thereafter. Therefore the effective key length is 56 bits, and it is usually quoted as such.

Like other block ciphers, DES by itself is not a secure means of encryption but must instead be used in a mode of operation. FIPS-81 specifies several modes for use with DES [4,5,6].

The algorithm's overall structure is shown in Figure 2.1 [6]. In which there are 16 identical stages of processing, are called rounds. There is also an initial and final permutation, denoted as IP and FP, which are inverses (IP "undoes" the action of FP, and vice versa). IP and FP have almost no cryptographic significance, but they were apparently included in order to facilitate loading blocks in and out of Mid 1970s hardware, and also to make DES run slower in software.

The 64bits block is divided into two 32-bit halves before the main rounds and processed alternately. And this criss-crossing is known as the Feistel scheme. The structure of Feistel ensures that decryption and encryption are very similar processes and the only difference is that the subkeys are applied in the reverse order when decrypting.

Figure 2.1

But the rest of the algorithm is identical. This greatly simplifies implementation, particularly in hardware, as there is no need for separate encryption and decryption algorithms.

The ⊕ symbol denotes the Exclusive-OR (XOR) operation. The F-function scrambles half a block together with some of the key and the output from that F-function is then combined with the other half of the block, and before the next round the halves are swapped. But after the final round, the halves are not swapped and this is a feature of the Feistel structure which also makes encryption and decryption similar processes [5,6].

The F-function, shown in Figure 2.2 [6], operates on half a block (32 bits) at a time and it consists of four stages:

Figure 2.2 (F-function) of DES

1.                Expansion: in this stage the 32-bit half-block is expanded to 48 bits using the expansion permutation, which is denoted as E in the diagram, by duplicating half of the bits. The output consists of eight 6-bit pieces (8*6=48bits), and each containing a copy of 4 corresponding input bits and a copy of the immediately adjacent bit from each of the input pieces to either side.

2.                Key mixing: in key mixing the result is combined with a subkey using an XOR operation. Sixteen 48-bit subkeys i.e one for each round and they are derived from the main key using the key schedule (ll be described below).

3.                Substitution: the 3rd stage is subsititution. After mixing in the subkey, the block is divided into eight 6-bit pieces before processing by the S-boxes also called substitution boxes. And each of the eight S-boxes replaces its six input bits with four output bits according to a non-linear transformation, provided in the form of a lookup table. The S-boxes provide the core of the security of DES and without the S-boxes the cipher would be linear which will be trivially breakable.

4.                Permutation: and finally, according to a fixed permutation the 32 outputs from the S-boxes are rearranged, the P-box. This is designed in shuch way that after expansion, each S-box's output bits are spread across 6 different S-boxes in the next round.[6]

Here the Figure 2.3 illustrates the key schedule for encryption of the algorithm which generates the subkeys.

Figure 2.3 (Key Scheduling)

 Initially, 56 bits of the key are selected from the initial 64 by Permuted Choice 1 denoted as PC-1 and the remaining 8 bits are used as parity check bits and discarded thereafter as we have discussed earlier. The 56 bits are then divided into two 28-bit halves; each half is thereafter treated separately. In successive rounds, both halves are rotated left by one or two bits ( which is specified for each round), and then Permuted Choice 2 (PC-2) select the 48 subkey bits, i.e 24 bits from the left half, and 24 from the right. The rotations which is denoted by "<<<" in the diagram, mean that in each subkey a different set of bits is used, therefore each bit is used in approximately 14 out of the 16 subkeys.

The key schedule for decryption is similar, but  the subkeys are in reverse order compared to encryption, and the rest of  the process is the same as for encryption. And the same 28 bits are passed to all rotation boxes [6].

3   How DES Algorithms Work

      As I mentioned that DES works on bits, or binary numbers--the 0s and 1s common to digital computers. Each group offour bits makes up a hexadecimal, or base 16, number, and it works by encrypting groups of 64 message bits, which is the same as 16 hexadecimal numbers.

     For example, if we take the plaintext message "8787878787878787", and this message is then encrypt with the DES key "0E329232EA6D0D73", as a result we ll get the ciphertext "0000000000000000". Now if the ciphertext is decrypted using the same secret DES key "0E329232EA6D0D73", the result will be the original plaintext "8787878787878787" [3].

As I mention earlier that DES is a block cipher which means that it operates on plaintext blocks of a given size (64-bits) and that returns ciphertext blocks of the same size. Thus DES results in a permutation among the 2^64 (2 to the 64th power) possible arrangements of 64 bits, each of which may be either 0 or 1. Each block of 64 bits is divided into two blocks of 32 bits each, a left half block L and a right half R. make note that this division is only used in certain operations.

Example: Let suppose that M be the plain text message M = 0123456789ABCDEF, where M is in hexadecimal (also known as base 16) format. Now rewriting M in binary format, we get the 64-bit block of text:

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

L = 0000 0001 0010 0011 0100 0101 0110 0111

R = 1000 1001 1010 1011 1100 1101 1110 1111

The first bit of M is "0". The last bit is "1". We read from left to right.

DES operates on the 64-bit blocks using key sizes of 56- bits. The keys are actually stored as being 64 bits long, but as we mentioned earlier that every 8th bit in the key is not used (i.e. bits numbered 8, 16, 24, 32, 40, 48, 56, and 64). But however we will nevertheless number the bits from 1 to 64, going left to right, in the following calculations. But as you will see the eight bits just mentioned, get eliminated when we create subkeys.

Example: Let suppose that K be the hexadecimal key K = 133457799BBCDFF1. This gives us as the binary key by converting them into binary format, and we will get,

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

The DES algorithm uses the certain steps which are given below:

Step 1: Create 16 subkeys, each of which is 48-bits long.

The 64-bit key is permuted according to the following table, PC-1.

Since the first entry in the table is "57", this means that the 57th bit of the original key K becomes the first bit of the permuted key K+. The 49th bit of the original key becomes the second bit of the permuted key. The 4th bit of the original key is the last bit of the permuted key. Note only 56 bits of the original key appear in the permuted key [3].

From the original 64-bit key

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

we get the 56-bit permutation

K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

Next, split K+ into left and right halves, C0 and D0, where each half has 28 bits.

C0 = 1111000 0110011 0010101 0101111

D0 = 0101010 1011001 1001111 0001111

With C0 and D0 we now create sixteen blocks Cn and Dn, 1<=n<=16.

To do a left shift, move each bit one place to the left, except for the first bit, which is cycled to the end of the block.

So From original pair pair C0 and D0 we obtain:

C0 = 1111000011001100101010101111

D0 = 0101010101100110011110001111

C1 = 1110000110011001010101011111

D1 = 1010101011001100111100011110

C2 = 1100001100110010101010111111

D2 = 0101010110011001111000111101

C3 = 0000110011001010101011111111

D3 = 0101011001100111100011110101

C4 = 0011001100101010101111111100

D4 = 0101100110011110001111010101

C5 = 1100110010101010111111110000

D5 = 0110011001111000111101010101

C6 = 0011001010101011111111000011

D6 = 1001100111100011110101010101

C7 = 1100101010101111111100001100

D7 = 0110011110001111010101010110

C8 = 0010101010111111110000110011

D8 = 1001111000111101010101011001

C9 = 0101010101111111100001100110

D9 = 0011110001111010101010110011

C10 = 0101010111111110000110011001

D10 = 1111000111101010101011001100

C11 = 0101011111111000011001100101

D11 = 1100011110101010101100110011

C12 = 0101111111100001100110010101

D12 = 0001111010101010110011001111

C13 = 0111111110000110011001010101

D13 = 0111101010101011001100111100

C14 = 1111111000011001100101010101

D14 = 1110101010101100110011110001

C15 = 1111100001100110010101010111

D15 = 1010101010110011001111000111

C16 = 1111000011001100101010101111

D16 = 0101010101100110011110001111

Next is to form the keys Kn, for 1<=n<=16, by applying the PC-2, but PC-2 only uses 48 of these.

For the first key we have C1D1 = 1110000 1100110 0101010 1011111 1010101

0110011 0011110 0011110

By applying the permutation PC-2, becomes

K1 = 000110 110000 001011 101111 111111 000111 000001 110010

For the other keys we have

K2 = 011110 011010 111011 011001 110110 111100 100111 100101

K3 = 010101 011111 110010 001010 010000 101100 111110 011001

K4 = 011100 101010 110111 010110 110110 110011 010100 011101

K5 = 011111 001110 110000 000000 111111 110101 001110 101000

K6 = 011000 111010 010100 100111 110010 000111 101100 101111

K7 = 111011 001000 010010 010110 111111 100001 100010 111100

K8 = 111101 111000 101000 000111 010110 010011 101111 111011

K9 = 111000 001101 101111 111101 011111 011110 011110 000001

K10 = 101100 011111 001101 101000 111101 100100 011001 001111

K11 = 001000 010101 111111 010011 110111 101101 001110 000110

K12 = 011101 010111 000111 110101 100101 000110 011111 101001

K13 = 100101 111100 010111 010001 111110 101011 101001 000001

K14 = 010111 110100 001110 110111 111100 101110 011100 111010

K15 = 101111 111001 000110 001101 001111 010011 111100 001010

K16 = 110010 110011 110110 001011 000011 100001 011111 110101

For the subkeys now look at the message itself.

Step 2: Encode each 64-bit block of data.

In this step there is an initial permutation IP of the 64 bits of M. This rearranges the bits according to the table given below.

The above table shows the new arrangement of the bits from their initial order. The 58th bit of M becomes the first bit of IP. The 50th bit of M becomes the second bit of IP. The 7th bit of M is the last bit of IP.

Applying the IP  to the block of text M.

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

Here the 58th bit of M is "1", which becomes the first bit of IP. The 50th bit of M is "1", which becomes the second bit of IP. The 7th bit of M is "0", which becomes the last bit of IP.

Next divide the permuted block IP into a left half L0  and a right half R0 of 32 bits.

L0 = 1100 1100 0000 0000 1100 1100 1111 1111

R0 = 1111 0000 1010 1010 1111 0000 1010 1010

(further full description and calculation is available in the Data Encryption standard illustrated by J.Orlin Grabbe) [3].

And at the end of all calculation the encrypted message derived is 85E813540F0AB405.

So  M = 0123456789ABCDEF and

C = 85E813540F0AB405.

Decryption is simply the inverse of encryption [3].

3   Applications

In general, cryptography is used to protect data while it is being communicated between two points or while it is stored in a medium vulnerable to physical theft [5,6].

The DES is a basic building block for data protection [8].

General Applications

1. Data Encryption:

DES may be used to encrypt a 64-bit plaintext input to a 64-bit ciphertext output.

2. Data Authentication:

The Data Encryption Standard was originally intended for the encryption and decryption of computer data. However, its application has been extended to data authentication as well.

3. Data Encryption and Authentication:

The same data may be protected by both encryption and authentication. So the data is protected from disclosure by using encryption and modification is detected by using authentication.[8]

Specific Applications

1. Data Storage and Mail Systems:

Many computer systems encrypt passwords for storage in the computer memory. When a user signs on the computer and enters the password, so this passwrod is encrypted and compared with the stored value. And the encrypted password is often created by using DES.

To provide secure mail the key notarization system that incorporates the DES may also be used in conjunction with a mail system [8].

2. Electronic Funds Transfers (Retail and Wholesale):

One of the most significant use of DES is the protection of retail and wholesale electronic funds transfer messages. Standards have been develped by the retail and wholesale financial communities for the authentication of EFT messages (ANSI X9.9 and ANSI X9.19), and these efforts have led to encryption (ANSI X9.23 Draft) and key management (ANSI X9.17 and ANSI X9.24 Draft) standards. [8]

4   Weakness & Improvement

With many block ciphers because of reduced cipher complexity there are some keys that should be avoided.

These keys are such that the same sub-key is generated in more than one round, and they include:

·      Weak keys

The same sub-key is generated for every round.

DES has 4 weak keys.

·      Semi-weak keys

Only two sub-keys are generated on alternate rounds.

DES has 12 of these (in 6 pairs).

·      Demi-semi weak keys

 Have four sub-keys generated.

None of these causes a problem since they are a tiny fraction of all available keys.

However they MUST be avoided by any key generation program. [7]

There are some Possible Techniques for Improving DES, which are:

·         Multiple enciphering with DES

·         Extending DES to 128-bit data paths and 112-bit keys.

·         Extending the key expansion calculation[7].

4   Conclusion

The DES algorithm has been a successful effort in the early development of security mechanisms. It is the most widely analyzed, tested, and used cryptoalgorithm and it will continue to be for some time yet to come. But perhaps the most important contribution of the DES is that it has led us to other security considerations, beyond the algorithm itself, that must be made in order to have secure computer systems and networks.

References

[1]William M. Daley, Raymond G. Kammer, “Federal Information Processing Standards Publication”, U.S. Department Of Commerce/National Institute Of Standards And Technology, Oct 1999.

[2]David P. Leech, Michael W. Chinworth,“The Economic Impacts of NIST's Data Encryption Standard (DES) Program”, The National Institute of Standards and Technology Program Office, Oct 2001.

[3]J.Orlin Grabbe, “The DES Algorithm Illustrated”.

[4]Mitsuru Matsui, "The First Experimental Cryptanalysis of the Data Encryption Standard", Computer & Information Systems Laboratory Mitsubishi Electric Corporation, Kaimgawa, 247, Japan.

[5]National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.

[6]http://en.wikipedia.org/wiki/Data_Encryption_Standard#cite_note-17.

[7]Dr. Faheem Bukhatwa, “Communicaton Security”, Lecture notes.

[8]Miles E. Smid And Dennis K. Branstad, “The Data Encryption Standard Past and Future”, National Institute of Standards and Technology.