Data Encryption Standard (DES) is a data encryption standard invented in the USA in the 80s of the XX century. Among ciphers, he is rightfully considered a "pensioner", while remaining a workhorse of cryptography. DES has ceased to be suitable in conditions of ultrafast technology and large amounts of data due to limitations of 56 bits per key and 64 bits per data. However, it is still in use.
What are block ciphers?
DES is a block cipher algorithm. Over the past 20-30 years, many block ciphers have been created, but creating a good cipher that would be safe is a rather complicated task. It is important that the cipher possesses characteristics that will enable it to function in many fields and industries.
Block ciphers consist of several iterations in turn using a certain cipher. Each iteration is called a round. As practice shows, even some of the primitive algorithms, when used sequentially, are able to create reliable ciphers. The DES algorithm is an example that has remained reliable and indestructible for 20 years.
This approach to cipher development greatly simplifies the process and simplifies security analysis. For example, a test attack on a block cipher begins with a minimum number of rounds and methodically continues with an increase in the number of rounds.
Using DES
Although DES is deprecated and does not meet modern requirements, it can be used, for example, in the form of 3DES, when the cipher is used three times in a row. This approach removes the key size limit, but the block of encrypted data remains the same. At the time, DES was a fairly fast and cryptographic cipher. Now this is not the case, and 3DES is at all three times slower. Despite this, DES is still used in a number of systems, but its use in new projects is prohibited.
Officially, the DES cipher algorithm was the standard in the United States until 1998. In 1997, the creation of a new standard, which was called AES (Advanced Encryption System), began, and although cryptanalysis shows that trying to crack DES leads to many systems of non-linear equations, analytical methods cannot help solve the problem - its weak point is the small number of possible keys . Their number is 2 56 and all options can be sorted out using modern technology in a relatively short time.
One round in the algorithm
For clarity of presentation and description of the DES algorithm, we use the figure (linear calculation diagram) 4.1, showing the structure of one round.
Each rectangle in the line diagram represents some calculations, and the arrow emanating from it indicates where the results of the block will be transmitted. A plus sign circled indicates an “exclusive or” operation, called XOR programming. The operation is also called "bitwise addition" or "addition without transfer". On the net you can find the DES algorithm in C and study it for a better understanding.
DES accepts a 64-bit text block. It goes through the initial permutation according to a certain principle. When analyzing the algorithm, it turned out that there was little sense in this rearrangement, since it does not give any cryptographic effect. The text block is divided into 2 equal parts: right (R) and left (L). Then the encrypted parts are interchanged and combined, and at the end of the round, a 64-bit data block is obtained, only encrypted.
General algorithm
The DES algorithm includes 16 rounds performed according to the scheme described above. All rounds are numbered through i, where i = (1; 16). Each i-th round of the pair (Li-1, Ri-1) receives a new pair (Li, Ri) using the key Ki. Major transformations occur inside function F.
Function F Operation Algorithm
As can be seen from Figure 4.1, R goes through the operation "Expansion". This block duplicates a number of bits from R and supplements it with them, receiving a 48-bit value. The result passes through bitwise addition with the 48-bit key Ki. And the result of this operation is transferred to block S. Block S contains 8 small matrix substitutions, which are selected in a special way.
Each matrix receives 6 bits of information at the input and produces a 4-bit value. As a result, at the input, block S receives 48-bit data, and at the output it represents the result in the form of a 32-bit value.
This 32-bit value goes through another permutation operation, after which it is summed by the xor operation with L. Finally, the right and left parts are swapped and the round ends. As already mentioned, the algorithm makes 16 rounds of such rounds.
Here we will not overload the article with examples that take up a lot of space. The operation of the DES encryption algorithm and examples can be viewed on the network.
Feistel cipher
The DES algorithm is based on the Feistel cipher. His idea is very elegant. At each round, part L is added with the value F (R, Ki) and L changes position with R. A key feature of the Feistel algorithm is that decryption and encryption consist of the same steps: parts L and R are interchanged, and then the addition operation L and F (R, Ki). This allows you to make encryption and decryption procedures simple and understandable.
One interesting change is often introduced in the Feistel ciphers - the cancellation of the permutation L and R in the last iteration. This makes the encryption and decryption algorithms completely symmetrical. The only difference is the use of the Ki keys. This principle turned out to be extremely convenient for use at the software level, since encryption and decryption occurs using the same function. For example, a concise implementation of the DES encryption algorithm in C.
Encryption keys
DES uses sixteen 48-bit keys to encrypt data. One key per round. Each key is created by sampling 48 bits from a 56-bit primary key. The creation of keys for a given round is determined by the mechanism described in detail in the DES documentation.
Briefly, the key selection algorithm i is as follows. Bits are added to the main key at positions 8, 16, 24, 32, 40, 48, 56, 64. This is done so that each byte contains an odd number of units. Compliance with the rule helps to detect key exchange errors. After that, using special tables, the augmented key is subject to permutation and shifts, with the exception of the bits that were added. Thus, the required key is obtained.
DES Components
Each component of the DES algorithm solves a specific problem:
- Feistel's algorithm simplifies encryption and decryption, while guaranteeing mixing of both halves of the text.
- The bitwise summation of parts of the text with the keys mixes the open data with the key and encrypts them.
- S-block and correspondence tables make the algorithm non-linear, increasing its resistance to various attacks.
- Extension, S-block and permutations provide diffusion of the algorithm - an avalanche effect. In other words, if at least 1 bit changes in the input of function F, then this will cause a change in the set of bits at once. If an avalanche effect is not observed in the cipher, then changes in open data will lead to equivalent changes in encrypted form, which can be tracked and used for hacking. In cryptography there is a criterion for the avalanche effect. The algorithm satisfies it if, when changing 1 bit of open data, at least half of the encrypted data changes. The DES algorithm satisfies him starting from round 4. Bottom line - when changing 1 bit of open data in the DES cipher, 29 bits will change.
DES security issues
An obvious DES problem is fetching encryption keys from a shared key. What happens if you select a zero value as the key (all bits of the key are 0)? This will lead to the fact that the selection of all keys for encryption in each round will be the same, and all keys will be zero. Not only will 16 encryption take place with one key, because the DES encryption and decryption algorithms differ only in the order in which the keys are used, they will be exactly the same. The whole point of encryption is lost.
DES has 4 keys, which are called weak, leading to the described effect. DES has 12 semi-weak and 48 pseudo-weak keys, which limit the variation of the generated keys in rounds. In other words, it is likely that during encryption in 16 rounds not 16 different keys will be used, but 8, 4 or even 2.
A less obvious drawback of DES is the complementarity property. It means that if you use plain text padding and key padding during encryption, you will end up with a value that is padded with ciphertext. This ridiculous property can lead to successful attacks on projects using DES for security.
Encryption Key Problem
It is fundamental to DES and is considered the main reason why you should abandon this algorithm. Since the key size in DES is 56 bits, then to search through all the keys you need to look at 2 56 options. Is this so much?
If you carry out 10 million key checks per second, then the verification will take about 2000 years. The algorithm seems to be quite robust. It was such in the last century, when the creation of a computer of such power was almost an impossible task both from a technical and financial point of view.
If you create a computer with a million chips, it will take 20 hours to sort through the entire set of DES keys. The first such computer for decryption according to the DES algorithm appeared in 1998, which coped with the task in 56 hours. Modern technologies of networks and parallel processes can reduce this time even more.
Cryptanalysis and DES
It can be said without exaggeration that DES became the cause of the emergence of applied science under the name "Cryptographic Analysis". From the very beginning of the advent of DES, attempts were made to crack it, scientific work was carried out to study it. All this led to the emergence of such areas of mathematics as:
- linear cryptanalysis - the study and identification of the relationship between plaintext and encrypted;
- differential cryptanalysis - the study and analysis of dependencies between several plaintexts and their encrypted versions;
- cryptanalysis on related keys - the study of the dependencies between encrypted texts received on the primary key and keys associated with the primary in any way.
DES survived 20 years of worldwide cryptanalysis and attacks, but remained a strong cipher. But he who seeks will always find ...
- Biham and Shamir, scientists from Israel, in 1991 showed using differential cryptanalysis that a DES could be attacked in which the key was calculated provided that the attacker had 2,447 specially selected pairs of plaintext and encrypted texts.
- The Japanese scientist Mitsuru Matsui in 1993 showed that the key can be calculated using linear cryptanalysis. To do this, you just need to know 2 47 pairs of plaintext and the corresponding encrypted version.
In the future, these hacking methods were slightly improved, improved and simplified, and a number of new hacking methods also appeared. But they remain too complicated, against their background a complete enumeration of all key options seems to be the most adequate attack on DES.