2.4. Symmetric Stream Encryption

Stream ciphers are characterized by the fact that they encrypt information one bit per encryption clock. Considering that among bit operations there are only two reversible ones - modulo 2 sum and logical negation, then the choice of encryption principle is obvious - clear text bits should be added to the key sequence bits using the operation Е:

          c _i = m _{i is} k _i.

Decryption is similar:

          m _i = c _{i is} k _i.

Given the properties of the addition operation modulo 2, it can be noted that the following is performed:

          k _i = c _{i are} m _i ,

therefore, the robustness of stream ciphers depends entirely on the quality of the keystream generator. Obviously, if the keystream includes only binary zeros, the ciphertext will be an exact copy of the plaintext. The stream of keys of stream ciphers is usually denoted by the Greek letter g (gamma), as a result of which such ciphers are called gamming ciphers. Most modern gamma generators are built on linear shift registers (LSR). It represents (Fig. 2.9) a sequence of bits that is shifted to the right by 1 bit at each encryption cycle, while the output from the rightmost bit is the generator output, and the value calculated as a sum of 2 multiple digits is supplied to the input of the leftmost bit LRS The encryption key of the stream cipher is entered in the LSR before the start of gamma generation.

Fig.2.9. Linear shift register

Consider the work of LRS on the example of a three-digit register, the structure of which is shown in Figure 2.10

Put in the register the initial value of 010 and see what value we get at the output of the gamma.

Table 2.2

The result of the gamma generator on the basis of LRS

The table shows that the state of the LRS is repeated after 7 cycles (the initial state of the LRS coincides with its state at the 7th cycle). The repetition of the state of LRS means that the gamma will also be periodically repeated. The repetition of the gamma reduces the cryptographic strength of stream ciphers, allowing the cryptanalyst to analyze ciphertexts obtained by coding on the same gamut. Therefore, when designing the structure of VRS, there is a problem of achieving the maximum repetition period of VRS. For LRS with a length of n bits, the maximum period is 2 ⁿ -1 clock cycles (the state when all bits are zero is unacceptable, since LRS of any structure does not go out of this state, looping in it). The construction of an LRS with an optimal structure in terms of the gamma repetition period has a clear mathematical basis in the form of the theory of irreducible polynomials. The structure of LRS is described by a polynomial of the form:

      b ₁ * x ⁿ + b ₂ * x ^{n -1} + b ₃ * x ^{n -2} + ... + b _{n -1} * x ² + b _n * x + 1 ,

where b _i = 0 if the i-th bit to the left does not participate in the feedback, and b _i = 1 if it participates. The LRS will have the maximum possible repetition period of the gamma if the polynomial describing it is not decomposed into a product of polynomials of a lesser degree.

The main problem of LRS is their instability to attack based on known plaintext. Even if the internal structure of the LRS is unknown, a cryptanalyst using the Berlekamp-Massey algorithm using the known 2N bits of plaintext and the corresponding ciphertext has the ability to construct the LRS generating such a sequence. Therefore, modern stream ciphers are based on nonlinear shift registers (LDCs). Nonlinear shift registers are constructed on the basis of linear elements with the addition of nonlinear elements to the structure: logical addition and logical multiplication. The most popular classes of nonlinear shift registers today are filtering, combining, and dynamic stream ciphers [6].

Fig.2.11. Stream cipher based on filtering LDCs

Filtering LDCs are constructed using an additional combinational circuit - a filter - at the outputs of some bits of RL (Fig. 2.11). The output of the combinatorial circuit is the gamut.

Fig.2.12. Stream cipher based on combining LDCs

Combining LDCs also use a combinational circuit with nonlinear bit conversions, but the outputs of several LSR are fed to the input of this combinational circuit (Fig. 2.12).

When designing the combined-type LDCs, it is necessary to ensure that the combinational circuit uniformly mixes the outputs of each LRS, otherwise a situation of domination of one of the LSRs may occur when its output coincides with the overall LDC output on the vast majority of cycles.

Dynamic LDCs are also built on the basis of several LSRs, but here they enter into a “master-slave” relationship (Figure 2.13). Depending on the output of the LRS manager, the total output of the LDCs is either the output of the first or the second LSR.

Fig.2.13. Dynamic LDCs stream cipher

An example of a stream cipher built on the basis of shift registers is the A5 algorithm used for coding in the GSM standard. A5 includes 3 RLs with a length of 19, 22 and 23 bits at the gamma output, the sum modulo 2 outputs of all registers is supplied. The scheme of dynamic LDC is used, when each register is clocked depending on the state of the middle digits of all three shift registers.

Stream codes are also RC4, SEAL, WAKE [12].