On the probability of breaking stream ciphers by the overlap method.
On the probability of breaking stream ciphers by the overlap method
Let there be a hoop or circle with a circumference of L centimeters. A strip of paper of length l1 is glued to this hoop., centimeters. After this, the hoop is turned at a random angle and another strip of paper l2 centimeters long is glued to it. Determine the probability of overlapping the strips of paper by more than s centimeters.
The solution to this, at first glance, «childish» problem contains answers to a number of serious questions that arise when creating, cracking and assessing the strength of stream ciphers.
Definitions and statement of the problem
The principle of stream encryption is to impose a cipher gamma on open data. A cipher gamma is a sequence of random bits {Гi}, produced by a generator R(k) according to some algorithm (in this case, it does not matter whether the generator R(k) works in a truly random or pseudo-random way). The generator parameter k is called a key, it determines the starting value of the generator and is selected randomly from a sufficiently large key set К. Knowing the generator's operating algorithm and its initial state (key), you can easily calculate the encryption gamma.
If the bit depth R(k)is n bits, then the maximum period of the sequence generated by such a generator is 2n-1 bits, after which the sequence of bits of the gamma [ 1 ] is repeated.
Let us denote by L = 2n-1 the length of the cycle of such a sequence.
It is unacceptable for any stream cipher to use the same key twice, since it is easy to extract encrypted information from two ciphertexts encrypted with the same gamma, even without knowing the encryption key. The corresponding decryption method is called the overlap method. However, even in the case of using two different (random) keys for encryption, overlapping (intersecting) gamma segments is not excluded, which also entails the possibility of reading the encrypted information.
Obviously, to ensure a high degree of cipher strength, it is necessary that the probability of intersection of two ciphertexts be extremely small, therefore, the study of the strength of stream ciphers includes the study of the probability of overlapping of gamma segments obtained on random keys.
Decryption of messages by the overlap method
Let us briefly describe the principle of decryption of information by the overlap method.
Let there be two cryptograms (ciphertext 1 and ciphertext 2), encrypted on a computer.
1. Suppose that in this cryptogram, some Word 1 was encrypted from the first position. From the relation ciphertext = plaintext + gamma, taking into account the ASCII encoding, we calculate the probable gamma Probable. We remove the calculated segment of gamma Probable from the ciphertext 2 from the first position and check the resulting text against the dictionary — does it correspond to any word or part of a word. In case of failure, we remove the gamma Probable from the second position of ciphertext 2, then from the third, etc. until the end of ciphertext 2.
2. In case of failure of the previous step, we assume the occurrence of Word 1from the second position of ciphertext 1 and perform the procedure described in point 1. In case of failure, we assume the occurrence of Word 1 from the third position of ciphertext 1, and so on until the end of ciphertext 1.
3. If no meaningful result was obtained at the previous stage, then we select Word 2 from the dictionaryand repeat steps 1 and 2. Repeat this process until there are no more possible words (the dictionary runs out). Obviously, to optimize the speed of the decryption algorithm, it is advisable to order the words in the dictionary not alphabetically, but by frequency of use in the texts of the correspondence: the most frequently used ones — at the beginning, the least used ones — at the end. To do this, the cryptanalyst must first study the features of the encrypted correspondence of his opponent.
4. If nothing useful came out of the described process, i.e. as a result of executing points 1, 2, 3 the semantic text cannot be extracted, then these cryptograms have no intersections. In this case, you can either stop cryptanalysis or select the next pair of cryptograms (ciphertexts). For n cryptograms, the number of possible paired samples is expressed by the «number of combinations»; 
If a meaningful text appears at any stage of cryptanalysis, the cryptanalysis of the remaining part of the text can be continued in the manner described above. Usually, knowledge of the decrypted words helps to guess the next word that is suitable in meaning, as well as to select words, part of a word and a space, a phrase or a group of words included in the undecrypted part of the text. You can also try to analyze a segment of the resulting gamma Probability to determine the algorithm of the generator R(k) — analytically determine the law of formation of pseudo-random bits and thus decrypt the remaining part of the message.
Probability
Since communication sessions are usually approximately the same length (a day, a week, a month), all segments of the gamma are equal in length, which we will denote by l. We will denote by s the maximum permissible overlap of two segments of the gamma, that is, the volume of ciphertext, the decryption of which does not entail the disclosure of secrets.
For example, in the language of correspondence, one can propose the average length of one word, several words, or the average length of a phrase as such a value.
In Russian, the average length of one word is 7-8 characters, usually followed by one space. Thus, s ~ 8 or 9 bits. Obviously, establishing the value of this parameter requires special linguistic research for each language in which encrypted correspondence is conducted.
In the ASCII code, one message character is encoded by 8 bits, therefore, the permissible overlap value of two texts encrypted on a computer is 64-72 bits. In the MTK-2 code, the message character is encoded by five bits, therefore, the permissible overlap value for telegraph messages is 40-45 bits. You can even increase this value slightly in the first case by 7, and in the second by 4 bits, so that the last character is incomplete.
In the specified notations, the probability that two copies of the gamma formed by two random keys will intersect by more than s bits is: 
The maximum number of session gammas for the cryptosystem under study is L/(l — 2s). To achieve a high degree of security of a stream cipher, the number L/(l — 2s) must be large enough.
Formula (1) does not reflect two important points. First, when deriving this formula, it is necessary to take into account that the adversary usually does not intercept all encrypted messages. Thus, when calculating the probability of decryption, it is necessary to take into account the probability of interception of messages by the adversary p. Secondly, formula (1) is correct for calculating the probability of overlapping only two messages. However, it is logical to assume that during the use of this cipher (let's denote it as m), more than two messages will be encrypted.
Taking into account the above, the desired probability should be calculated using the following formula: 
The approximate number of messages encrypted during the «lifetime» of a cipher can be calculated as follows. Let's assume that N copies of encryption tools are to be produced, the «lifetime» of which is M years. Then, if we denote the validity period of a session key (in seconds) as Tk, during the lifetime of the equipment, m = N*M*(C0/Tk) pieces of the gamma will be generated on session keys, where C0=31 558 153 is the number of seconds in a year. The parameter m is inversely proportional to the validity period of the key. The length of the session gamma l also depends on Tk. If we denote by Vgamma generation rate of the cipher equipment, then l = Va*Tk
Thus, formula (2) can be rewritten as follows: 
From expression (3), we can derive the formula for the validity period of the session key Tk if we set the remaining parameters of the cryptosystem (P, N, M, L, s, Va, p). In particular, for this it is necessary to set the numerical value of the probability P, which guarantees that the strength of stream ciphers exceeds the enemy's ability to crack them.
In this case, two approaches are possible:
A. The strength of the chain is determined by the strength of the weakest link, therefore, the probability P should not exceed the probability of finding a random key for it, which in the ideal case is equal to 1/K, where K is the power of the set of keys.
B. Other types of ciphers can be used as a basis for comparison. If we require that the security of stream ciphers be no less secure than that of block ciphers, then we can obtain numerical values of probability P: P=10-17 (DES), P=10-38 (RC4), P=10-77 (GOST).
It is obvious that as the enemy accumulates ciphertexts, the probability of overlap will increase. This process of accumulation of cryptogram segments reflects the process of «aging» of the encryption tool, and upon reaching a certain critical value, it is apparently necessary to plan a change of cipher or significant changes to the algorithm of its operation. It is necessary to take into account the computing resources of the enemy, which he is able to direct to opening ciphers.
Recommendations
Formula (2) allows to analyze the parameters of the encryption algorithm L, l (Tk, Va ), s, m (N, M, Tk), p, on which the stability of the stream cipher depends, and to give recommendations on increasing the stability of encryption systems of this type.
So, the following options are available to increase the stability of the stream cipher.
Reduce the parameter р. Reducing this parameter means that it is necessary to make it more difficult for the enemy to intercept encrypted information. Despite the fact that the information is encrypted and, as one might think, in a secure form, its interception by the enemy is dangerous with a probability of р and must be prevented.
Increase L. Since L = 2n, then to increase L it is necessary to increase the bit depth of the generator R(k), which is similar to replacing the cipher.
To increase the cryptographic strength of the cipher, you can, for example, use a combination of several different generators (R = R1+R2+R3+…) with different periods. In this case, the total period length is equal to the product of the period lengths of individual generators. To complicate the cryptanalyst's work, it would not hurt to come up with a more complex combination of different generators.
Since Tk is usually a day, a week, a month, and the speed of the equipment is fixed, then from the ratio L/(l-2s)we can determine the minimum value of L, which will give the minimum value of the bit depth R(k). In practice, this relationship for increasing the cipher strength prescribes increasing L, all other things being equal.
Decrease l. Since l = Tk*Va , then decreasing lmeans decreasing the validity period of the session key or decreasing the speed of issuing gamma into the communication channel. However, decreasing the validity period of the session key leads to an increase in the number of communication sessions m, which leads to an increase in the probability of overlaps. Thus, using this parameter is useless.
Decrease m. Since m = N*M*(C0/Tk), this means decreasing the number of devices implementing this cipher (N), or decreasing the lifespan of this encryption tool (M).
Ratio (3) also means that the security of information of one of the users of the cipher is determined by the number of other subscribers using a similar cipher and the intensity of their encrypted correspondence.
Therefore, the manufacturer of the cipher must calculate the maximum number of copies of the encryption tools that it can sell to its customers without compromising the security, as well as the maximum number of customers using this cipher. The manufacturer is obliged to warn the consumer in advance about the maximum service life of this type of cipher, after which it is subject to replacement. The consumer must be sure that the manufacturer will not violate these restrictions under any circumstances for reasons of commercial benefit. It is reasonable to demand written guarantees and theoretical calculations in this regard.
This remark once again confirms the fact that a large number of keys to the cipher does not guarantee its security. For example, the security of a stream cipher with any key length can be made arbitrarily small by increasing the number of overlaps. Of course, this case is quite hypothetical, since the enemy's computing power may not allow him to process a large number of messages in an acceptable time.
Literature
1. Zhelnikov V. Cryptography from papyrus to computer.
2. Kuzminov T. V. Cryptographic methods of information protection. Novosibirsk. Institute of Informatics Systems SB RAS, 1998.
3. Gnedenko B. V. Fundamentals of probability theory. Moscow, 1989.
4. Barichev S. Fundamentals of cryptography.
5. Sapegin, Wegner. Protection of personal computer software.