Cryptanalysis

Cryptanalysis (from other Greek κρυππός - hidden and analysis) is the science of decrypting encrypted information without a key intended for such decryption.

The term was introduced by the American cryptographer William F. Friedman in 1920 as part of his book Elements of Cryptanalysis ^[1] . Informal cryptanalysis is also called a cipher cracking.

In most cases, cryptoanalysis is understood as the elucidation of the key; cryptanalysis also includes methods for detecting the vulnerability of cryptographic algorithms or protocols.

Initially, cryptanalysis methods were based on the linguistic patterns of natural text and were implemented using only pencil and paper. Over time, in cryptanalysis, the role of purely mathematical methods is growing, for the implementation of which specialized cryptoanalytic computers are used.

Attempting to reveal a specific cipher using cryptanalysis methods is called a cryptographic attack on this cipher. A cryptographic attack during which it was possible to unlock the cipher is called a burglary or an attack .

History of cryptanalysis

Cryptanalysis evolved along with the development of cryptography: new, more advanced ciphers replaced the already cracked coding systems only so that cryptanalysts invented more sophisticated methods of cracking encryption systems. The concepts of cryptography and cryptanalysis are inextricably linked with each other: in order to create a system that is resistant to cracking, it is necessary to take into account all possible ways of attacking it.

Classic cryptanalysis

Although the concept of cryptanalysis was introduced relatively recently, some hacking methods were invented tens of centuries ago. The first known written mention of cryptanalysis is the “Manuscript on the decryption of cryptographic messages,” written by Arab scholars Al-Kindi back in the 9th century. In this scientific work contains a description of the method of frequency analysis.

Frequency analysis is the main tool for hacking most classic permutation or replacement ciphers. This method is based on the assumption of the existence of a non-trivial statistical distribution of symbols, as well as their sequences simultaneously in plain text and in ciphertext. Moreover, this distribution will be maintained up to the replacement of characters both during the encryption process and during the decryption process. It is worth noting that, provided the length of the encrypted message is sufficiently long, mono-alphabetic ciphers are easily amenable to frequency analysis: if the frequency of a letter in a language and the frequency of a certain character present in a ciphertext are approximately equal, then in this case it is highly likely that will be this very letter. The simplest example of frequency analysis can be a banal calculation of the number of each of the characters encountered, then follow the procedure of dividing the resulting number of characters by the number of all characters in the text and multiplying the result by one hundred to present the final answer as a percentage. Further, the percentage values ​​are compared with the table of probabilistic distribution of letters for the intended original language.

In the period of the 15th — 16th centuries, polyalphabetical replacement codes were created and developed in Europe. The most famous is the French diplomat cipher Blaise de Vigenere, which is based on the use of a sequence of several Caesar ciphers with different shift values. For three centuries, the Vigenère Cipher was considered completely cryptographically stable until, in 1863, Friedrich Kasiski proposed his own method of breaking this cipher. The basic idea of ​​Kasiski’s method is as follows: if in a clear text between two identical sets of characters there is such a block of text that its length is a multiple of the length of the keyword, then the same set of characters of the clear text will be transferred to the same segments of the ciphertext during encryption. In practice, this means that if there are identical segments of three or more characters in the ciphertext, it is likely that these segments correspond to identical segments of plaintext. How the Kasiski method is applied: in ciphertext, pairs of identical segments of length three or more are searched for, then the distance between them, that is, the number of characters separating the starting positions of the pair of segments, is calculated. As a result of the analysis of all pairs of identical segments, we obtain a set of distances d ₁ , d ₂ , d ₃ , ... Obviously, the key word length will be a divisor for each of the distances and, therefore, for their greatest common divider.

The next stage in the development of cryptanalysis is associated with the invention of rotary cryptographic machines such as, for example, the Enigma invented by Arthur Sherbius. The purpose of such devices was to minimize the number of duplicate pieces of ciphertext, the appearance statistics of which was used when cracking the Vigenere cipher. Polish crypto analysts managed to build a prototype of a decryption machine for the Enigma version used by Nazi Germany. The car received the name “Bomb” because it produced sounds similar to the ticking of the clock. Later it was refined and adopted by the British cryptanalyst.

Modern cryptanalysis

With the development of new methods of encryption, mathematics became more and more significant. For example, in frequency analysis, a cryptanalyst should have knowledge of both linguistics and statistics. While the theoretical work on cryptoanalysis of Enigma was carried out primarily by mathematicians, for example, Alan Mathison Turing. Nevertheless, thanks to the same mathematics, cryptography has reached such a development that the number of elementary mathematical operations necessary for hacking has begun to reach astronomical values. Modern cryptography has become much more resistant to cryptanalysis than the once used, outdated methods, for breaking which had enough pens and sheets of paper. It may seem that pure theoretical cryptanalysis is not able to more effectively crack modern ciphers. Nevertheless, historian David Kahn writes in his article on the 50th anniversary of the National Security Agency:

“Nowadays, hundreds of firms offer many different cryptosystems that cannot be cracked by any of the known cryptanalysis methods. Indeed, such systems are resistant even to an attack on selected plaintext, that is, a comparison of the plaintext and the corresponding ciphertext does not allow you to find out the encryption key that would allow to decrypt other messages. Thus, in a sense, cryptanalysis is dead. But this is not the end. Cryptanalysis can be dead, but, to put it metaphorically, a skin can be removed from a cat in several ways. ”

Further, in his note describes the increased value of data interception, bookmarks of bugs, attacks on third-party channels and quantum computers as techniques that replace the traditional methods of cryptanalysis. In 2010, former technical director of the National Security Office, Brian Snow, noted that commercial cryptography has almost reached the level of technology development used by intelligence services, and now they are "very slowly moving in an already fully explored area."

However, cryptanalysis is still too early to write off. Firstly, it is not known how effective the methods of cryptanalysis used by special services are, and secondly, during the years of development and improvement of modern computer cryptography, many claims were made both to theoretical and practical cryptographic primitives: ^{[ source not specified 1477 days ]}

• In 1998, a vulnerability to ciphertext-based attacks was discovered in the MADRYGA block cipher, proposed as early as 1984, but not widely used.
• A whole series of attacks by the scientific community, many of which were wholly practical, literally destroyed the FEAL block cipher, proposed as a replacement for DES as a standard encryption algorithm, but also not widely used.
• It was also found that using widely available computational tools, the A5 / 1, A5 / 2 stream ciphers, the CMEA block cipher, and the DECT encryption standard used to protect mobile and wireless telephony can be cracked in hours, minutes, and and in real time.
• The brute force attack has helped to crack some of the application protection systems, for example, CSS — a system for protecting digital media content on DVD media.

Thus, although the most reliable of modern ciphers are much more resistant to cryptanalysis than Enigma, nevertheless, cryptanalysis still plays an important role in the extensive field of information security.

Cryptanalysis methods

Bruce Schneier identifies 4 basic and 3 additional methods of cryptanalysis, suggesting knowledge of the cryptanalyst cipher algorithm:

The main methods of cryptanalysis:

1. Ciphertext Attack
2. The attack on the basis of open texts and the corresponding ciphertexts
3. Attack based on matched plain text (ability to select text to encrypt)
4. An attack based on adaptively matched plain text.

Additional cryptanalysis methods:

1. Attack based on matched ciphertext
2. Attack based on matched key
3. Gangster cryptanalysis

Basic cryptanalysis methods

Ciphertext Attacks

Suppose a cryptanalyst possesses a certain number of ciphertexts resulting from the use of the same encryption algorithm. In this case, the cryptanalyst can only make an attack based on a ciphertext. The goal of a cryptographic attack in this case is to find as many open texts as possible corresponding to the existing ciphertexts, or, even better, to find the key used for encryption.

The cryptanalyst can receive input data for this type of attack as a result of simple interception of encrypted messages. If the transmission is carried out through an open channel, then the implementation of the data collection task is relatively easy and trivial. Ciphertext-based attacks are the weakest and most uncomfortable.

The attack on the basis of open texts and the corresponding ciphertexts

Let the cryptanalyst have at his disposal not only ciphertexts, but also the corresponding open texts.

Then there are two options for setting the problem:

1. Find the key used to convert plaintext to ciphertext
2. Create an algorithm that can decrypt any message encoded with this key

Getting open source plays a crucial role in the implementation of this attack. Open texts are extracted from various sources. So, for example, you can guess about the contents of the file by its extension.

In the case of hacking correspondence, you can make the assumption that the letter has a structure of the type:

• "Greeting"
• "Main text"
• "The final form of courtesy"
• "Signature"

Consequently, an attack can be organized by selecting different types of “Greetings” (for example, “Hello!”, “Good afternoon”, etc.) and / or “Final form of politeness” (such as “Regards”, “Yours sincerely " etc.). It is easy to see that this attack is stronger than the attack based on ciphertext alone.

Attack based on matched plain text

To implement this type of attack, a cryptanalyst needs to have not only a certain number of open texts and ciphertexts derived from them. Among other things, in this case, the cryptanalyst should be able to pick up several open texts and get the result of their encryption.

The tasks of the cryptanalyst repeat the tasks for the plaintext attack, that is, to obtain the encryption key, or create a decryption algorithm for the given key.

You can get input for this type of attack, for example, as follows:

1. Create and send a fake unencrypted message allegedly from one of the users who usually use encryption.
2. In some cases, you can get an answer, which will contain an encrypted text that quotes the content of a fake message.

When carrying out an attack of this type, the cryptanalyst has the ability to select blocks of plaintext, which under certain conditions can provide more information about the encryption key.

Attacks based on adaptively matched plain text

This type of attack is a more convenient special case of an attack based on selected plaintext. The convenience of an attack based on an adaptively matched plaintext is that, in addition to being able to choose the encrypted text, the cryptanalyst can decide on encrypting a plaintext based on the encryption results already obtained. In other words, when launching an attack based on matched plaintext, the cryptanalyst selects only one large plaintext block for later encryption, and then starts hacking the system based on this data. In the case of an adaptive attack, the cryptanalyst can get the results of encrypting any plaintext blocks, in order to collect data of interest, which will be taken into account when selecting the next plaintext blocks sent for encryption, and so on. The presence of feedback gives an attack based on an adaptive ciphertext an advantage over all the above types of attacks.

Additional cryptanalysis methods

Attack based on matched ciphertext

Assume that the cryptanalyst has temporary access to the descrambler or device. In this case, for a limited period of time, the cryptanalyst can obtain corresponding open texts from the ciphertexts he knows, after which the cryptanalyst will need to proceed with the system hacking. When performing this type of attack, the purpose of hacking is to obtain an encryption key.

It is compressed to formulate this task in the following way:

Given: C ₁ , P ₁ = D _k (C ₁ ), C ₂ , P ₂ = D _k (C ₂ ), C ₃ , P ₃ = D _k (C ₃ ), ..., C _n , P _n = D _k (C _n ),

where C _n is the n-th available ciphertext, P _n is the corresponding C _n plaintext, and D _k is the decryption function using the key k.

Find: used encryption key k.

It may be interesting that an attack based on a selected ciphertext can also be called “Lunchtime attack” or “Midnight attack”. Say, the name “Attacks at lunchtime” reflects the fact that a legitimate user can leave his computer with decryption function unattended for lunch time, and a cryptanalyst can use this.

Attack based on matched key

Contrary to its name, an attack based on a matched key does not imply that the cryptanalyst is simply going through the keys in the hope of finding the right one. This type of attack is based on the fact that a cryptanalyst can observe the operation of an encryption algorithm that uses several keys. The cryptanalyst initially knows nothing about the exact meaning of the keys, but he knows some mathematical relation between the keys. An example of this is the situation when a cryptanalyst found out that the last 80 bits of all keys are the same, although the actual values ​​of the bits may be unknown.

A cryptanalyst can use the so-called “human factor”, that is, try using blackmail, bribing, torture or other means to obtain information about the encryption system or even the encryption key itself. For example, giving a bribe, as one of the types of gangster cryptanalysis, may be called "Opening with the purchase of a key." Thus, the autopsy technique is built on the weakness of people as an integral part of the information security system.

Gangster cryptoanalysis is considered a very powerful way of hacking the system, and often the best way to open ciphers.

Different types of attacks

• Attack "man in the middle"
• Third-party attack
• Attack "birthdays"
• Attack "brute force"
• Related key attack