Hak5
Save 10% at GoDaddy.com with coupon code HAK

DES

From Hak5

Jump to: navigation, search

DES or Data Encryption Standard was used as the encryption standard for until 1997 when it was replaced by AES due to its extreamly small key size of only 56-bits.

Contents

[edit] How it Works

DES encrypts and decrypts data in 64-bit blocks, using a 64-bit key (although the effective key strength is only 56 bits, as explained below). It takes a 64-bit block of plaintext as input and outputs a 64-bit block of ciphertext. Since it always operates on blocks of equal size and it uses both permutations and substitutions in the algorithm, DES is both a block cipher and a product cipher.

DES has 16 rounds, meaning the main algorithm is repeated 16 times to produce the ciphertext.

[edit] Key Scheduling

Although the input key for DES is 64 bits long, the actual key used by DES is only 56 bits in length. The least significant (right-most) is thrown away.

The first step is to pass the 64-bit key through a permutation called Permuted Choice 1, or PC-1 for short. The table for this is given below. Note that in all subsequent descriptions of bit numbers, 1 is the left-most bit in the number, and n is the rightmost bit.

PC-1: Permuted Choice 1

Bit 0123456
1 57 49 41 33 25 17 9
8 1 58 50 42 34 26 18
15 10 2 59 51 43 35 27
22 19 11 3 60 52 44 36
29 63 55 47 39 31 23 15
36 7 62 54 46 38 30 22
43 14 6 61 53 45 37 29
50 21 13 5 28 20 12 4

For example, we can use the PC-1 table to figure out how bit 30 of the original 64-bit key transforms to a bit in the new 56-bit key. Find the number 30 in the table, and notice that it belongs to the column labeled 5 and the row labeled 36. Add up the value of the row and column to find the new position of the bit within the key. For bit 30, 36 + 5 = 41, so bit 30 becomes bit 41 of the new 56-bit key. Note that bits 8, 16, 24, 32, 40, 48, 56 and 64 of the original key are not in the table. These are the unused parity bits that are discarded when the final 56-bit key is created.

Now that we have the 56-bit key, the next step is to use this key to generate 16 48-bit subkeys, called K[1]-K[16], which are used in the 16 rounds of DES for encryption and decryption. The procedure for generating the subkeys - known as key scheduling - is fairly simple:

1. Set the round number R to 1.

2. Split the current 56-bit key, K, up into two 28-bit blocks, L (the left-hand half) and R (the right-hand half).

3. Rotate L left by the number of bits specified in the table below, and rotate R left by the same number of bits as well.

4. Join L and R together to get the new K.

5. Apply Permuted Choice 2 (PC-2) to K to get the final K[R], where R is the round number we are on.

6. Increment R by 1 and repeat the procedure until we have all 16 subkeys K[1]-K[16].

Here are the tables involved in these operations:

Subkey Rotation Table

Round Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Number of bits to rotate 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

PC-2: Permuted Choice 2

Bit 0 1 2 3 4 5
1 14 17 11 24 1 5
7 3 28 15 6 21 10
13 23 19 12 4 26 8
19 16 7 27 20 13 2
25 41 52 31 37 47 55
31 30 40 51 45 33 48
37 44 49 39 56 34 53
43 46 42 50 36 29 32

[edit] Plaintext Preparation

Once the key scheduling has been performed, the next step is to prepare the plaintext for the actual encryption. This is done by passing the plaintext through a permutation called the Initial Permutation, or IP for short. This table also has an inverse, called the Inverse Initial Permutation, or IP^(-1). Sometimes IP^(-1) is also called the Final Permutation. Both of these tables are shown below.

IP: Initial Permutation

Bit 0 1 2 3 4 5 6 7
1 58 50 42 34 26 18 10 2
9 60 52 44 36 28 20 12 4
17 62 54 46 38 30 22 14 6
25 64 56 48 40 32 24 16 8
33 57 49 41 33 25 17 9 1
41 59 51 43 35 27 19 11 3
49 61 53 45 37 29 21 13 5
57 63 55 47 39 31 23 15 7

IP^(-1): Inverse Initial Permutation

Bit 0 1 2 3 4 5 6 7
1 40 8 48 16 56 24 64 32
9 39 7 47 15 55 23 63 31
17 38 6 46 14 54 22 62 30
25 37 5 45 13 53 21 61 29
33 36 4 44 12 52 20 60 28
41 35 3 43 11 51 19 59 27
49 34 2 42 10 50 18 58 26
57 33 1 41 9 49 17 57 25

These tables are used just like PC-1 and PC-2 were for the key scheduling. By looking at the table is becomes apparent why one permutation is called the inverse of the other. For example, let's examine how bit 32 is transformed under IP. In the table, bit 32 is located at the intersection of the column labeled 4 and the row labeled 25. So this bit becomes bit 29 of the 64-bit block after the permutation. Now let's apply IP^(-1). In IP^(-1), bit 29 is located at the intersection of the column labeled 7 and the row labeled 25. So this bit becomes bit 32 after the permutation. And this is the bit position that we started with before the first permutation. So IP^(-1) really is the inverse of IP. It does the exact opposite of IP. If you run a block of plaintext through IP and then pass the resulting block through IP^(-1), you'll end up with the original block.

[edit] DES Core Function

Once the key scheduling and plaintext preparation have been completed, the actual encryption or decryption is performed by the main DES algorithm. The 64-bit block of input data is first split into two halves, L and R. L is the left-most 32 bits, and R is the right-most 32 bits. The following process is repeated 16 times, making up the 16 rounds of standard DES. We call the 16 sets of halves L[0]-L[15] and R[0]-R[15].

1. R[I-1] - where I is the round number, starting at 1 - is taken and fed into the E-Bit Selection Table, which is like a permutation, except that some of the bits are used more than once. This expands the number R[I-1] from 32 to 48 bits to prepare for the next step.

2. The 48-bit R[I-1] is XORed with K[I] and stored in a temporary buffer so that R[I-1] is not modified.

3. The result from the previous step is now split into 8 segments of 6 bits each. The left-most 6 bits are B[1], and the right-most 6 bits are B[8]. These blocks form the index into the S-boxes, which are used in the next step. The Substitution boxes, known as S-boxes, are a set of 8 two-dimensional arrays, each with 4 rows and 16 columns. The numbers in the boxes are always 4 bits in length, so their values range from 0-15. The S-boxes are numbered S[1]-S[8].

4. Starting with B[1], the first and last bits of the 6-bit block are taken and used as an index into the row number of S[1], which can range from 0 to 3, and the middle four bits are used as an index into the column number, which can range from 0 to 15. The number from this position in the S-box is retrieved and stored away. This is repeated with B[2] and S[2], B[3] and S[3], and the others up to B[8] and S[8]. At this point, you now have 8 4-bit numbers, which when strung together one after the other in the order of retrieval, give a 32-bit result.

5. The result from the previous stage is now passed into the P Permutation.

6. This number is now XORed with L[I-1], and moved into R[I]. R[I-1] is moved into L[I].

7. At this point we have a new L[I] and R[I]. Here, we increment I and repeat the core function until I = 17, which means that 16 rounds have been executed and keys K[1]-K[16] have all been used.

When L[16] and R[16] have been obtained, they are joined back together in the same fashion they were split apart (L[16] is the left-hand half, R[16] is the right-hand half), then the two halves are swapped, R[16] becomes the left-most 32 bits and L[16] becomes the right-most 32 bits of the pre-output block and the resultant 64-bit number is called the pre-output.

[edit] Tables used in the DES Core Function

E-Bit Selection Table

Bit 0 1 2 3 4 5
1 32 1 2 3 4 5
7 4 5 6 7 8 9
13 8 9 10 11 12 13
19 12 13 14 15 16 17
25 16 17 18 19 20 21
31 20 21 22 23 24 25
37 24 25 26 27 28 29
43 28 29 30 31 32 1

P Permutation

Bit 0 1 2 3
1 16 7 20 21
5 29 12 28 17
9 1 15 23 26
13 5 18 31 10
17 2 8 24 14
21 32 27 3 9
25 19 13 30 6
29 22 11 4 25

S-Box 1: Substitution Box 1

Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

S-Box 2: Substitution Box 2

Row / Column0123456789101112131415
01518146113497213120510
13134715281412011069115
20147111041315812693215
31381013154211671205149

S-Box 3: Substitution Box 3

Row / Column0123456789101112131415
01009146315511312711428
11370934610285141211151
21364981530111212510147
31101306987415143115212

S-Box 4: Substitution Box 4

Row / Column0123456789101112131415
07131430691012851112415
11381156150347212110149
21069012117131513145284
33150610113894511127214

S-Box 5: Substitution Box 5

Row / Column0123456789101112131415
02124171011685315130149
11411212471315015103986
24211110137815912563014
31181271142136150910453

S-Box 6: Substitution Box 6

Row / Column0123456789101112131415
01211015926801334147511
11015427129561131401138
29141552812370410113116
34321295151011141760813

S-Box 7: Substitution Box 7

Row / Column0123456789101112131415
04112141508133129751061
11301174911014351221586
21411131237141015680592
36111381410795015142312

S-Box 8: Substitution Box 8

Row / Column0123456789101112131415
01328461511110931450127
11151381037412561101492
27114191214206101315358
32114741081315129035611

[edit] Ciphertext Preparation

The final step is to apply the permutation IP^(-1) to the pre-output. The result is the completely encrypted ciphertext. Encryption and Decryption

The same algorithm can be used for encryption or decryption. The method described above will encrypt a block of plaintext and return a block of ciphertext. In order to decrypt the ciphertext and get the original plaintext again, the procedure is simply repeated but the subkeys are applied in reverse order, from K[16]-K[1]. That is, stage 2 of the Core Function as outlined above changes from R[I-1] XOR K[I] to R[I-1] XOR K[17-I]. Other than that, decryption is performed exactly the same as encryption.

[edit] Weakness

It's main weekness is it's small key size --spektormax

Retrieved from "http://wiki.hak5.org/wiki/DES"