ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

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:

  1. Initial permutation rearranges bits in a certain, predefined way. This step does not enhance the security of algorithm. It was introduced to make passing data into encryption machines easier, at the times when the cipher was invented.
  2. The input data is divided into two 32-bit parts: the left one and the right one.
  3. 56 bits are selected from the 64-bit key (Permutation PC-1). They are then divided into two 28-bit parts.
  4. Sixteen rounds of the following operations (so called Feistel functions) are then performed:
    1. Both halves of key are rotated left by one or two bits (specified for each round). Then 48 subkey bits are selected by Permutation PC-2.
    2. The right half of data is expanded to 48 bits using the Expansion Permutation.
    3. The expanded half of data is combined using XOR operation with the 48-bit subkey chosen earlier.
    4. The combined data is divided into eight 6-bit pieces. Each part is then an input to one of the S-Boxes (the first 6-bit part is the input to the first S-Box, the second 6-bit part enters the second S-Box, and so on). The first and the last bits stand for the row, and the rest of bits define the column of an S-Box table. After determining the location in the table, the value is read and converted to binary format. The output from each S-Box is 4-bit long, so the output from all S-Boxes is 32-bit long. Each S-box has a different structure.
    5. The output bits from S-Boxes are combined, and they undergo P-Box Permutation.
    6. Then, the bits of the changed right side are added to the bits of the left side.
    7. The modified left half of data becomes a new right half, and the previous right half becomes a new left side.
  5. After all sixteen rounds, the left and the right halves of data are combined using the XOR operation.
  6. The Final Permutation is performed.

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.
Initial Permutation Table
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157
Scheme of DES initial permutation
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).
PC-1 Permutation Table
Left half
5749413325179
1585042342618
1025951433527
1911360524436
Right half
63554739312315
7625446383022
1466153453729
211352820124
Scheme of DES PC-1 permutation
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.
Expansion Permutation Table
321234545
6789891011
1213121314151617
1617181920212021
2223242524252627
282928293031321
Scheme of DES expansion permutation
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.
PC-2 Permutation Table
1417112415328
15621102319124
2681672720132
4152313747553040
5145334844493956
3453464250362932
Scheme of PC-2 permutation
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.
Permutation P Table
167202129122817
11523265183110
282414322739
19133062211425
Scheme of permutation P
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.
Final Permutation Table
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725
Scheme of DES final permutation
Scheme of DES Final Permutationclick to enlarge
Site under development.