Encryption With DES

ALGORITHM DES (DATA ENCRYPTION STANDARD)

Introduction to DES

• The DES (Data Encryption Standard) is perhaps the best-known, most widely used encryption system in the world.
• It is reasonably fast (faster than PGP, although not particularly suited for software implementation)
• It is extensively analyzed (large amount of people have tried to break it, but failed, no major defects found)
• The key size is marginal (64-bit key becomes obsolete, breaking the key is as difficult as exhaustively searching from 1 to 2⁵⁶ for the possible key value; on the average this takes 2⁵⁵ calculations and the use of network computers can today challenge that - See Note).
• It was not primarily designed for software
• Key distribution needed

The DES Algorithm

The Encryption Procedure

The input of the cipher is the plaintext in blocks of 64 bits and a 64-bit long key consisting of a 56-bit number and 8 parity bits. The stages are depicted in Fig. 1 and are briefly described below.

1. The Initial Permutation (IP) moves bits around according to the box in Fig. 2 (the 58^th bit is moved to position 1 and so on). Some software implementations of  DES leave out the Initial and Final Permutation, since they can cost in performance although they do not affect DES's strength.

2. The block is broken into a right and a left half, each 32 bits long.
3. Then, 16 rounds of the function f (described below) take place in which the data is combined with the key.
4. The output of the function is XORed with the left half of the data block, then left and right halves are switched and the new round starts.
5. After the 16^th round, the two halves are connected and a Final Permutation (Fig. 3) is performed.

The f Function

In every round, the following things occur :

1. We reduce the 64-bit key to 56 bits, by ignoring every eighth (parity) bit.

2. Then, 16 subkeys are generated for each one of the rounds of DES.

The subkeys are determined in the following way:

a. The 56-bit key is divided as well in two halves of 28 bits. The two blocks are shifted left one or two positions, depending on the round for which they will be used. Fig. 4 gives the number of shifts.

b. After the shift, 48 out of the 56 bits are selected, according to the following compression permutation.

c. The right half of the data in each round is expanded to 48 bits according to the table in Fig. 6, which is called the expansion permutation.

d. The data and the compressed key are XORed. The result of the XOR operation undergoes the substitution operation. There are 8 S-boxes (Fig.7) to help this stage. Each one takes in order 6 bits from the 48-bit input and outputs 4 bits. At the end, a 32-bit stream will be produced. The numbers in the S-boxes are the 4-bit numbers which will be the output. The input is used to find the row and the column of this particular number. (Row counting in the S-Boxes start from zero).

For example, assume that the output is 100011. The first and the last bit is 3 (11), which corresponds to row 3 and the center bits are 1 (0001) which corresponds to column 1. If this is the fourth round, so the fourth S-Box is used, the output will be 15.

Note: The security of DES lies on the way these S-Boxes work to recover the "important" 32 bits, since a lot of redundancy was introduced in the previous steps. It is believed that the S-boxes are so powerful that if we "swap" two of the numbers in them, the algorithm is trivial to break.

e. The final step in the f function is called the P-Box permutation. The 32-bit output of the S-Box is once more permuted according to the table shown in Fig. 8.

Note: It must be clear that, despite the so many operations on the initial plaintext, no information is discarded.

Decryption of DES

The decryption of a ciphertext is done in a symmetric (almost identical) to the encryption way. The only thing that changes is that the keys will be used from the last (K₁₆) to the first one (K₁).

Differential cryptanalysis
Differential cryptanalysis requires that we have some kind of access to the encryption mechanisms. This means that we can create pairs of plaintext and ciphertext, without knowing the key (i.e. by challenging a server, or having someone's smart card). The goal is to recover this key. First, we know C1 = {M1}k and C2 = {M2}k . We perform Val1 = C1 XOR C2 and if we created the plaintexts in such way that they have a fixed difference, we can find specific "difference patterns" in the ciphertexts as well. As we analyze more and more of these differences, we are lead towards to the correct key.

Using differential cryptanalysis, we need approximately 243 plaintext - ciphertext pairs, compared to the 256 calculations which must be made in an exhaustive search. Of course, a user must have access to a such great number of pairs.

Linear cryptanalysis

Linear is more complicated than the differential cryptanalysis and needs approximately 247 operations. Plaintext and ciphertext pairs are also needed and the main idea behind it is that by XORing some bits from the plaintext, some from the ciphertext and then XOR the output, a clue as to what the key is may come up.

"Switching" cipher blocks

As we said, the DES algorithm is implemented on blocks of data. If what's always encrypted by a particular application is in a fixed format, the attacker can interfere with the content even if it's encrypted and has no idea of the key. For example, he can swap the blocks of between two messages and they will still have meaning.
To prevent such kids of attacks, a technique other than the Electronic Codebook (ECB) mode described above, is used:

CBC (Cipher block Chaining) Mode
In CBC, we start off with an initialization vector, which can be a string of random data. The IV is XORed with the plaintext and feed the result to DES along with the key. At the second block, B2 is encrypted using the ciphertext of B1 as the initialization vector, B3 is encrypted using the ciphertext of B2 as IV and so on. In this way, identical plaintext blocks are encrypted to different ciphertext blocks, as long as at least one previous plaintext block is different. Fig. 9 shows how the previous ciphertext block is used to encrypt the following plaintext block.

Properties of CBC :

• Patterns in plaintext are concealed
• An error is only propagated in one block
• Last block can be used as integrity check on message
• Track of length and padding data has to be kept
• Random access decryption can be implemented: In most encrypting methods, we have to decrypt all previous blocks of data to come up with a needed block. On the contrary, with CBC mode, all we need is look only one block backwards.