Self-synchronizing stream cipher

Self-synchronizing stream ciphers (SSSC ) - a class of stream ciphers in which plaintext is encrypted depending on the key function and a fixed number of characters $M$ ${\ displaystyle M}$ $M$ ciphertext . Therefore, each encrypted character can be decrypted if the previous ones were received correctly. $M$ ${\ displaystyle M}$ $M$ ciphertext characters, and the key function is known. This approach allows the receiving side to decrypt data in asynchronous mode, that is, it does not require synchronization of the key generator of the receiving and transmitting sides.

Cipher Structure

Encryption of the next plaintext bit $m_{i}$ ${\ displaystyle m_ {i}}$ $m_i$ performed by binary addition with the corresponding key bit $z_{i}$ ${\ displaystyle z_ {i}}$ $z_{i}$ :

c_{i}=m_{i}\oplus z_{i}

{\ displaystyle c_ {i} = m_ {i} \ oplus z_ {i}}

c_{i}=m_{i}\oplus z_{i}

,

where is the key bit $z_{i}$ ${\ displaystyle z_ {i}}$ $z_{i}$ determined by encryption function $f_{s}$ ${\ displaystyle f_ {s}}$ $f_s$ depending on the encryption key changing according to a certain rule $K$ ${\ displaystyle K}$ $K$ and from previous $M$ ${\ displaystyle M}$ $M$ ciphertext characters offset by $b$ ${\ displaystyle b}$ $b$ bit:

z_{i}=f_{s}[K](c_{i-b-M+1}\dots c_{i-b})

{\ displaystyle z_ {i} = f_ {s} [K] (c_ {ib-M + 1} \ dots c_ {ib})}

z_{i}=f_{s}[K](c_{i-b-M+1}\dots c_{i-b})

$M$ ${\ displaystyle M}$ $M$ called the encryption memory, and $b$ ${\ displaystyle b}$ $b$ - delayed encryption function. Need for delay $b$ ${\ displaystyle b}$ $b$ due to the fact that when the algorithm is implemented, the processes of sending and receiving encrypted text, as well as encryption and decryption, occur in parallel . Decryption is carried out as follows:

m_{i}=c_{i}\oplus z_{i}

{\ displaystyle m_ {i} = c_ {i} \ oplus z_ {i}}

m_{i}=c_{i}\oplus z_{i}

.

To decrypt the first $M$ ${\ displaystyle M}$ $M$ plaintext bit, you must define the initialization vector:

C_{init}=c_{-M+1}\dots c_{0}

{\ displaystyle C_ {init} = c _ {- M + 1} \ dots c_ {0}}

C_{init}=c_{-M+1}\dots c_{0}

.

The initialization vector must be sent to the recipient first. Moreover, if the first first $k$ ${\ displaystyle k}$ $k$ the initialization vector bit on the receiving side is different from the first $k$ ${\ displaystyle k}$ $k$ bit of the transmitting side, then the probability that the entire ciphertext is received correctly is equal to $2^{-k}$ ${\ displaystyle 2 ^ {- k}}$ $2^{-k}$ . ^[one]

Cryptographic Properties

The cryptographic properties of a self-synchronizing stream cipher follow from the properties of the encryption function. In this model, the cryptanalyst knows the encryption memory $M$ ${\ displaystyle M}$ encryption features $f_{s}$ ${\ displaystyle f_ {s}}$ , and the key $K$ ${\ displaystyle K}$ unknown to him. To ensure a certain level of cryptographic strength of the function $f_{s}$ ${\ displaystyle f_ {s}}$ , you need to select the size of the encryption memory $M$ ${\ displaystyle M}$ depending on the frequency of the key exchange $K$ ${\ displaystyle K}$ . If at the output of the function the cryptanalyst detects two repeating ciphertext sequences of long $M$ ${\ displaystyle M}$ each, then he will be able to find out the sum modulo 2 of the corresponding two bits of plaintext.

Let the ciphertext sequence of the encryption function be obtained $f_{s}$ ${\ displaystyle f_ {s}}$ with a non-changing specific key $K$ ${\ displaystyle K}$ :

[c_{1}c_{2}...c_{M}]c_{M+1}\dots [c_{L+1}c_{L+2}\dots c_{L+M}]c_{L+M+1},L>M+1

{\ displaystyle [c_ {1} c_ {2} ... c_ {M}] c_ {M + 1} \ dots [c_ {L + 1} c_ {L + 2} \ dots c_ {L + M}] c_ {L + M + 1}, L> M + 1}

Without loss of generality, a zero delay ( $b=0$ ${\ displaystyle b = 0}$ )

c_{M+1}=f_{s}[K](c_{1}c_{2}\dots c_{M})\oplus m_{M+1}

{\ displaystyle c_ {M + 1} = f_ {s} [K] (c_ {1} c_ {2} \ dots c_ {M}) \ oplus m_ {M + 1}}

c_{L+M+1}=f_{s}[K](c_{L+1}c_{L+2}\dots c_{L+M})\oplus m_{L+M+1}

{\ displaystyle c_ {L + M + 1} = f_ {s} [K] (c_ {L + 1} c_ {L + 2} \ dots c_ {L + M}) \ oplus m_ {L + M + 1 }}

Under the given condition $[c_{1}c_{2}\dots c_{M}]=[c_{L+1}c_{L+2}\dots c_{L+M}]$ ${\ displaystyle [c_ {1} c_ {2} \ dots c_ {M}] = [c_ {L + 1} c_ {L + 2} \ dots c_ {L + M}]}$

c_{M+1}\oplus c_{L+M+1}=m_{M+1}\oplus m_{L+M+1}

{\ displaystyle c_ {M + 1} \ oplus c_ {L + M + 1} = m_ {M + 1} \ oplus m_ {L + M + 1}}

The minimum cipher memory value is determined $M$ ${\ displaystyle M}$ to prevent the described vulnerability . If we consider the ciphertext stream as a sequence of random numbers, the probability $q(N,M)$ ${\ displaystyle q (N, M)}$ that in a random binary sequence of length $N$ ${\ displaystyle N}$ all subsequences of length $M$ ${\ displaystyle M}$ different equal to:

q(N,M)=\prod _{i=0}^{N-1}(1-i2^{-M})

{\ displaystyle q (N, M) = \ prod _ {i = 0} ^ {N-1} (1-i2 ^ {- M})}

Using Taylor's decomposition $\ln(1-x)\approx -x$ ${\ displaystyle \ ln (1-x) \ approx -x}$ for small $x$ ${\ displaystyle x}$ it turns out:

\ln q(N,M)=\sum _{i=0}^{N-1}\ln(1-i2^{-M})\approx -2^{-M}\sum _{i=0}^{N-1}i=-N(N-1)2^{-M-1}

{\ displaystyle \ ln q (N, M) = \ sum _ {i = 0} ^ {N-1} \ ln (1-i2 ^ {- M}) \ approx -2 ^ {- M} \ sum _ {i = 0} ^ {N-1} i = -N (N-1) 2 ^ {- M-1}}

We set the admissible probability p of the repetition of 2 subsequences of length M inside a sequence of length N. The length of the sequence N is given for a certain key K of the encryption function $f_{s}$ ${\ displaystyle f_ {s}}$ .

p<1-q(N,M)\approx \ln q(N,M)

{\ displaystyle p <1-q (N, M) \ approx \ ln q (N, M)}

From here we find that the encryption memory M must be selected:

M\geqslant \log _{2}({\frac {N^{2}}{p}})

{\ displaystyle M \ geqslant \ log _ {2} ({\ frac {N ^ {2}} {p}})}

For example, for $p=10^{-9}$ ${\ displaystyle p = 10 ^ {- 9}}$ and $N=10^{12}$ ${\ displaystyle N = 10 ^ {12}}$ encryption memory score - $M\geqslant 110$ ${\ displaystyle M \ geqslant 110}$ . On the other hand, one should take into account the possibility of errors when transmitting data over a communication channel . An error in one bit during transmission of the ciphertext extends to the next M bits during decryption. Therefore, the encryption memory M should be selected as small as possible. Given the above arguments, for a specific example, select $M\in [80,128]$ ${\ displaystyle M \ in [80,128]}$ seems reasonable to meet security conditions and error tolerance. ^[2]

Differential Cryptanalysis

For self-synchronizing ciphers, differential cryptanalysis can be successfully applied, giving restrictions on the type of encryption function $f_{s}$ ${\ displaystyle f_ {s}}$ . For each pair of input vectors $C_{1}$ ${\ displaystyle C_ {1}}$ and $C_{2}$ ${\ displaystyle C_ {2}}$ long M, differing by $a^{'}$ ${\ displaystyle a '}$ function $f_{s}$ ${\ displaystyle f_ {s}}$ returns a pair of encrypted bits. We fix one input vector $C_{1}$ ${\ displaystyle C_ {1}}$ . Number of possible deviations $a^{'}$ ${\ displaystyle a '}$ from this vector: $N=2^{M}-1$ ${\ displaystyle N = 2 ^ {M} -1}$ $(a\neq [00...0])$ ${\ displaystyle (a \ neq [00 ... 0])}$ . Consider pairs $C_{1}$ ${\ displaystyle C_ {1}}$ and $C_{2}=C_{1}\oplus a'$ ${\ displaystyle C_ {2} = C_ {1} \ oplus a '}$ . Define the differential probability $DP_{f_{s}}(a',1)$ ${\ displaystyle DP_ {f_ {s}} (a ', 1)}$ that the output bits are equal: $f_{s}(C_{1})=f_{s}(C_{2})$ ${\ displaystyle f_ {s} (C_ {1}) = f_ {s} (C_ {2})}$ . Differential cryptanalysis considers difference $DP_{f}(a',1)$ ${\ displaystyle DP_ {f} (a ', 1)}$ from ${\frac {1}{2}}$ ${\ displaystyle {\ frac {1} {2}}}$ . If the differential probability can be represented as:

DP_{f_{s}}(a',1)={\frac {1}{2}}\pm l^{-1}

{\ displaystyle DP_ {f_ {s}} (a ', 1) = {\ frac {1} {2}} \ pm l ^ {- 1}}

,

then the number of input pairs of vectors needed to calculate the difference $DP_{f_{s}}(a',1)-{\frac {1}{2}}$ ${\ displaystyle DP_ {f_ {s}} (a ', 1) - {\ frac {1} {2}}}$ approximately equal $l^{2}$ ${\ displaystyle l ^ {2}}$ . It follows that the encryption function should not have a differential probability $DP_{f_{s}}(a',1)$ ${\ displaystyle DP_ {f_ {s}} (a ', 1)}$ different from ${\frac {1}{2}}$ ${\ displaystyle {\ frac {1} {2}}}$ more than $2^{-{\frac {M}{2}}}$ ${\ displaystyle 2 ^ {- {\ frac {M} {2}}}}$ :

l^{-1}=2^{-{\frac {M}{2}}}

{\ displaystyle l ^ {- 1} = 2 ^ {- {\ frac {M} {2}}}}

Number of required pairs:

l^{2}=2^{M}>N=2^{M}-1

{\ displaystyle l ^ {2} = 2 ^ {M}> N = 2 ^ {M} -1}

So, to find out the difference $DP_{f_{s}}(a',1)-{\frac {1}{2}}$ ${\ displaystyle DP_ {f_ {s}} (a ', 1) - {\ frac {1} {2}}}$ giving information about the key, it is necessary to completely sort through all the possible differences a '. ^[3]

Comparison of self-synchronizing stream ciphers with analogues

Comparison with synchronous stream ciphers

In synchronous stream ciphers , a key stream is generated regardless of the ciphertext. For correct decryption, it is necessary that the key stream generator be synchronized on the receiving and transmitting sides. As a rule, this is done by resetting the generator when a certain stream of ciphertext bits of a fixed length appears - markers . In case of a marker transfer error, the generators will stop working synchronously and further decryption will fail. At the same time, when a wrong bit is received once in the case of self-synchronizing encryption, decryption will continue correctly after M bits. On the other hand, if the generators are synchronized in synchronous stream encryption, the reception of one incorrect bit gives rise to the incorrect decryption of one bit, while in the self-synchronizing encryption M bits will be incorrectly decrypted.

Comparison with block cipher

Self-synchronizing ciphers can be considered as block ciphers operating in a single-bit feedback mode . To encrypt one plaintext bit, it is required to perform the encryption function of the whole block, which is much slower than the encryption function of the self-synchronizing cipher. Therefore, a self-synchronizing cipher works much more effectively than a block cipher in a given mode. Another important feature of self-synchronizing ciphers is that every bit of plaintext affects the entire ciphertext. Compared to block ciphers, self-synchronizing ciphers give the best performance when attacking based on redundancy of plaintext . ^[four]

Notes

↑ Matthew Robshaw, Olivier Billet. New Stream Cipher Designs - The eSTREAM Finalists . - Springer, 2008 .-- S. 210-213.
↑ Ueli M. Maurer. New Approaches to the Design of Self-Synchronizing Stream Ciphers // Advances in Cryptology - EUROCRYPT '91. - Springer, Berlin, Heidelberg, 1991-04-08. - P. 465-466 . - ISBN 3540464166 . - DOI : 10.1007 / 3-540-46416-6_39 .
↑ Matthew Robshaw, Olivier Billet. New Stream Cipher Designs - The eSTREAM Finalists. - Springer. - S. 212-213.
↑ Ueli M. Maurer. New Approaches to the Design of Self-Synchronizing Stream Ciphers // Advances in Cryptology - EUROCRYPT '91. - Springer, Berlin, Heidelberg, 1991-04-08. - P. 459-460 . - ISBN 3540464166 . - DOI : 10.1007 / 3-540-46416-6_39 .

Literature

Matthew Robshaw, Olivier Billet. New Stream Cipher Designs - The eSTREAM Finalists . - Springer. - 1997 .-- S. 210-216.
Ueli M. Maurer. New Approaches to the Design of Self-Synchronizing Stream Ciphers // Advances in Cryptology - EUROCRYPT '91. - Springer, Berlin, Heidelberg, 1991-04-08. - S. 459-466 . - ISBN 3540464166 .

[1] Matthew Robshaw, Olivier Billet. New Stream Cipher Designs - The eSTREAM Finalists . - Springer, 2008 .-- S. 210-213.

[2] Ueli M. Maurer. New Approaches to the Design of Self-Synchronizing Stream Ciphers // Advances in Cryptology - EUROCRYPT '91. - Springer, Berlin, Heidelberg, 1991-04-08. - P. 465-466 . - ISBN 3540464166 . - DOI : 10.1007 / 3-540-46416-6_39 .

[3] Matthew Robshaw, Olivier Billet. New Stream Cipher Designs - The eSTREAM Finalists. - Springer. - S. 212-213.

[4] Ueli M. Maurer. New Approaches to the Design of Self-Synchronizing Stream Ciphers // Advances in Cryptology - EUROCRYPT '91. - Springer, Berlin, Heidelberg, 1991-04-08. - P. 459-460 . - ISBN 3540464166 . - DOI : 10.1007 / 3-540-46416-6_39 .