ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη  # DES (Data Encryption Standard)

• Description
• Algorithm
• Block diagrams
• Mathematical functions
• Implementation
DES was one of the most popular block symmetric ciphers. It was created in the early 1970s at IBM and adopted as a federal standard by NBS in 1976.
Block cipher with symmetric secret key
Block length = 64 bits
Key length = 56 bits
DES is one of the most thoroughly examined encryption algorithms. In 1981 it was included in ANSI standards as Data Encryption Algorithm for private sector.
At the beginning of the 21st century, DES started to be considered insecure, mainly due to its relatively short secret key length, what makes it vulnerable to brute force attacks. In 2001 DES cipher was replaced by AES. DES is still one of the most popular cipher.

DES uses the key which is 64-bit long, however only 56 bits are actually used by the algorithm. Every 8th bit of the key is a control one and it can be used for parity control.

In the encryption process, the data is first divided into 64-bit long blocks. Then, each block undergoes the following operations:

During decryption, the same set of operations is performed but in reverse order. The subkeys are also selected in reverse order (compared to encryption).

## Weak keys in DES

A weak key in the DES cipher is a key which generates the same subkeys in all the successive rounds of encryption algorithm. There are four known weak keys in DES (expressed in hexadecimal):

## Semiweak keys in DES

A semiweak key in the DES cipher is a key for which one can find another key that produces the same encrypted ciphertext from the same given plaintext. There are twelve known semiweak keys in DES (expressed in hexadecimal, along with parity bits):

## Initial and Final Permutations in DES

The Initial and Final Permutations have no influence on security. They don't use a secret key and can be undone by anybody. They were introduced to make hardware implementation easier in some contexts. A hardware circuit which receives data over an 8-bit bus can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit area) than a single 64-bit register. This process naturally performs the Initial Permutation of DES.

Let's assume that somebody is designing a hardware circuit which should do some encryption with DES. The data will be received in blocks of 8 bits. This means that there are 8 lines, each yielding one bit at each clock. A common device for accumulating data is a shift register: the input line plugs into a one-bit register, which itself plugs into another, which plugs into a third register, and so on. At each clock, each register receives the contents from the previous register, and the first register accepts the new bit. Therefore, the contents are shifted.

With an 8-bit bus, 8 shift registers are needed, each receiving 8 bits for every input block. The first register receives bits 1, 9, 17, 25, 33, 41, 49 and 57. The second register receives bits 2, 10, 18, ..., and so on. After eight clocks, eight registers received the complete 64-bit block and it is time to proceed with the DES algorithm itself.

If initial permutation was not used, then the first step of the first round would extract the 'left half' (32 bits) which, at that point, would consist of the leftmost 4 bits of each of the 8 shift registers. The 'right half' would also get bits from all the 8 shift registers. If you think of it as wires from the shift registers to the units which use the bits, then you end up with a bunch of wires which heavily cross each other. Crossing is doable but requires some circuit area, which is the expensive resource in hardware designs.

On the other hand, if you consider that the wires must extract the input bits and permute them as per the DES specification, you will find out that there is no crossing anymore. In other words, the accumulation of bits into the shift registers inherently performs a permutation of the bits, which is exactly the initial permutation of DES. By defining that initial permutation, the DES standard says: 'well, now that you have accumulated the bits in eight shift registers, just use them in that order, that's fine'.

The same thing is done again at the end of the algorithm during the Final Permutation.

DES was designed at a time when 8-bit bus were the top of the technology and one thousand transistors were an awfully expensive amount of logic.

## Security of DES

DES is considered to be a well-designed and effective algorithm. However, just after its publication, many cryptographers believed that the size of its key is too small. At present, the 56-bit long key can be broken relatively cheaply, by using brute force attacks within a few days.

It is quite easy to attack DES knowing some parts of plaintext. The intruder can try all 256 possible keys. He looks for a key, which used for decryption of an encrypted block of the known plaintext, produces exactly the same plaintext. In practice, it is enough to know two or three blocks of plaintext to be able to determine if the currently testing key which works for them, will be working for other blocks as well. Probability that the found key is incorrect and converts correctly only the known plaintext blocks is negligibly small.

The fastest known attacks on DES use linear cryptanalysis. They require knowing 243 blocks of plaintext and their time complexity is around 239 to 243.

Permutations are presented in the form of tables only to make them easier to comprehend; one should bear in mind that input data is vectors, not matrices. Click to learn more on how to read the permutation table.

Initial Permutation
Initial Permutation is processed on each block of input data in the beginning of encryption.
 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Scheme of DES Initial Permutationclick to enlarge
Key Permutation PC-1
56 bits are selected from 64-bit key. The key is then divided into two parts. Each part undergoes bit shifting (every eighth bit is excluded from encryption and can be used for parity control).
 Left half 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 Right half 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 Scheme of DES PC-1 Permutationclick to enlarge
Expansion Permutation
Expansion Permutation initiates each round of Feistel functions. It expands the right half of data from 32 bits to 48 bits.
 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Scheme of DES Expansion Permutationclick to enlarge
Binary Rotation
In each round of Feistel functions, the 28-bit halves of key are rotated left by one or two bits.
Binary Rotation Table
No. of cycleAmount of bits
10
11
12
13
14
15
16
Key Permutation PC-2
During Key Permutation PC-2 48 bits are selected from the 56-bit subkey obtained for a given round of Feistel functions.
 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Scheme of PC-2 permutationclick to enlarge
S-Blocks
In S-Boxes encryption each 6-bit input block is replaced by 4-bit output.

If input bits are marked as a1, a2, a3, a4, a5 and a6, then the a1 and a6 comprise a 2-bit figure standing for a row, and the a2, a3, a4 and a5 comprise a 2-bit figure standing for a column (both columns and rows are numbered from zero). Where the row and column cross, there is the output figure of the block. For example, if the input string of bits is 101010, the output will be 0110.

S1
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01441312151183106125907
0yyyy10157414213110612119538
1yyyy04114813621115129731050
1yyyy11512824917511314100613
S2
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01518146113497213120510
0yyyy13134715281412011069115
1yyyy00147111041315812693215
1yyyy11381013154211671205149
S3
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01009146315511312711428
0yyyy11370934610285141211151
1yyyy0136498153011212510147
1yyyy11101306987415143115212
S4
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy07131430691012851112415
0yyyy11381156150347212110149
1yyyy01069012117131513145284
1yyyy13150610113894511127214
S5
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy02124171011685315130149
0yyyy11411212471315015103986
1yyyy04211110137815912563014
1yyyy11181271142136150910453
S6
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01211015926801334147511
0yyyy11015427129561131401138
1yyyy09141552812370410113116
1yyyy14321295151011141760813
S7
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy04112141508133129751061
0yyyy11301174911014351221586
1yyyy01411131237141015680592
1yyyy16111381410795015142312
S8
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01328461511110931450127
0yyyy11151381037412561101492
1yyyy07114191214206101315358
1yyyy12114741081315129035611
Permutation P
Permutation P is processed on the 32-bit output block from eight S-Boxes.
 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Scheme of Permutation Pclick to enlarge
Final Permutation
Final Permutation is processed for each block of data after the last round of Feistel functions. It is the inverse of the Initial Permutation.
 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Scheme of DES Final Permutationclick to enlarge
Site under development.