View source for Cryptographic generators. Stream ciphers and their cryptanalysis


==Cryptographic generators==
[[Cryptographic generator|Cryptographic generators]] are used to develop the cryptosystem keys and the [[gamma|gamma]] for stream ciphers.

===Base of cryptographic generators===
Base element of [[Cryptographic generator|Cryptographic generators]] is [[Linear shift register|the linear shift register]] with maximum period which output [[Gamma|gamma]] (linear recurrent sequence) has good statistical properties.Owing to that the linear recurrent sequence does not possess nonlinear properties it is possible to restore sequence on its small segment. So [[Linear shift register|the linear shift register]] is not good [[Cryptographic generator|cryptographic generators]], and using of [[Linear shift register|the linear shift register]] when you construct [[Cryptographic generator|cryptographic generators]] should be combined with various functional units and memory elements.

===Filter generators===
One of the elementary methods of sequence complication is the transformation of its subsequences in signs of other sequence by so-called filter function.

Let ''P'' is a final field. [[Autonomous automaton|The autonomous automaton]] [[File:формула 1.gif]], where ''h'' is the linear transformation of [[File:формула 2.gif]] realized by [[Linear shift register|the linear shift register]] of ''n'' length over ''P'' field with ''f'(x)'' feedback function,[[File:формула 3.gif]] is the filter function, is called the filter [[Cryptographic generator|generator]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]].

The filter [[Cryptographic generator|generator]] is called nonlinear, if the filter function is nonlinear. [[Cryptographic scheme of genarator|The cryptographic scheme]] of the filter [[Cryptographic generator|generator]] is represented in figure 1.

   [[File:рис1.jpg|frame|Figure 1. The cryptographic scheme of the filter generator|center]]

The filter [[Cryptographic generator|generator]] has the best characteristics when [[Linear shift register|the linear shift register]] has the maximum period and the balanced filter function is used. It warrants that the period of [[gamma|gamma]] is equal to [[File:формула 4.gif]], where ''k''=|''P''|, and the number of units and zeros on the period is approximately equal.

Nonlinear properties of [[gamma|a gamma]] are provided by a choice of nonlinear filter function. Let ''d'' is the filter function degree of nonlinearity. It is known [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]], that [[Linear complexity|the linear complexity]] of [[gamma|a gamma]] made by the filter [[Cryptographic generator|generator]] estimation is [[File:формула 5.gif]], where [[File:формула 6.gif]] s the number of various conjunctions on ''n'' variables of a rank from 0 to ''d''.

The [[gamma|gamma]] [[Linear complexity|the linear complexity]] estimation of the filter [[Cryptographic generator|generator]] depends on properties of filter function. For example, for bent-functions [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#KiSc83|[KiSc83]]] if 4|''n'', then [[File:формула 7.gif]].

The estimation for other class of functions which means that it is necessary to use filter function with the big degree of nonlinearity to obtain [[gamma|the gamma]] with high [[Linear complexity|the linear complexity]] is known [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#BeGu85|[BeGu85]]].

It is known [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ru85|[Ru85]]], that a part of the filter [[Cryptographic generator|generator]], constructed on [[Linear shift register|the linear shift register]] with maximum period and ''n'' length, where ''n'' is the prime number for which [[Linear complexity|the linear complexity]] is the greatest, tends to 100%.

===Combining generators===
The combining [[Cryptographic generator|generator]] is the complication of the filter [[Cryptographic generator|generator]]. It is constructed on ''m''>1 [[Linear shift register|linear shift registers]] over ''P'' field and [[File:формула 8.gif]] combining function which input is the signs of the linear recurrent sequences made by [[Linear shift register|linear shift registers]]. Let [[File:формула 9.gif]] is the length of LSR-''j'', [[File:формула 10.gif]]. [[Cryptographic scheme of genarator|The cryptographic scheme]] of the combining [[Cryptographic generator|generator]] on two [[Linear shift register|LSRs]] is represented in figure 2.

   [[File:Combining.jpg|frame|Figure 2. The cryptographic scheme of the combining generator|center]]

The combining [[Cryptographic generator|generator]] is called nonlinear, if the combining function is nonlinear.

Initial states of all [[Linear shift register|linear shift registers]] are the initial state of [[Cryptographic generator|the generator]]. If the initial state of all [[Linear shift register|LSRs]] is nonzero then the corresponding initial state of the combining [[Cryptographic generator|generator]] is called nonsingular.

Each [[File:формула 11.gif]]polynomial over  ''P'' final field correspond to a [[File:формула 12.gif]] polynomial over ring of integers, in which all nonzero factors substitute for 1 and addition and multiplication in ''P'' substitute for addition and multiplication in [[File:формула 14.gif]]. [[Linear complexity|The linear complexity]] of [[gamma|a gamma]] mde by the combining [[Cryptographic generator|generator]] estimation is [[File:формула 15.gif]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]].

For the best cryptographic properties of the combining [[Cryptographic generator|generator]] it is necessary that combining function depends on all variables and nonsingular initial states are used. Otherwise the combining [[Cryptographic generator|generator]] degenerates into combining [[Cryptographic generator|generator]] on smaller number of [[Linear shift register|the LSRs]].

If ''P'' is the simple field, and characteristic polynomials of all [[Linear shift register|linear shift registers]] are primitive and have pairwise coprime degrees, then  [[File:формула 16.gif]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#А05|[А05]]].

For some [[Linear shift register|linear shift registers]] and combining function it is possible to ensure good statistical properties and the big period of [[gamma|a gamma]] made by the combining [[Cryptographic generator|generator]]. In particular, if LSR-1, …, LSR-''m'' generate the sequences which [[File:формула 17.gif]] periods are pairwise coprime, and combining function is bijective on each variable, then [[File:формула 18.gif]].

Examples of combining [[Cryptographic generator|generators]]:

1)	Geffe [[Cryptographic generator|generator]];

2)	threshold [[Cryptographic generator|generator]].

Geffe [[Cryptographic generator|generator]] uses a combination of 3 registers. The combining function is equal to [[File:формула 19.gif]]. If all [[Linear shift register|linear shift registers]]  have maximum periods, and [[File:формула 20.gif]] their lengths are pairwise coprime, then the [[gamma|gamma]] period is equal to product of [[Linear shift register|linear shift register]] periods, and [[Linear complexity|the linear complexity]] of [[gamma|a gamma]] made by the [[Cryptographic generator|generator]] is equal to [[File:формула 21.gif]].

A threshold [[Cryptographic generator|generator]] uses a combination of an odd number of registers. The combining function which called majorization function is equal to [[File:формула 22.gif]].The period of [[gamma|a gamma]] made by the threshold [[Cryptographic generator|generator]] is equal to product of [[Linear shift register|linear shift register]] periods, and [[Linear complexity|the linear complexity]] of [[gamma|a gamma]] made by [[Cryptographic generator|the generator]] is equal to [[File:формула 23.gif]].

===Generators with non-uniform movement===
The best cryptographic properties of filter and combining [[Cryptographic generator|generators]] are reached when filter and combining functions of high degree of nonlinearity are used. So certain complexities of [[Cryptographic generator|generators]] engineering and realization are. An important feature of these [[Cryptographic generator|generators]] is the fact that the information in memory elements is updated in regular intervals, that is in each step of functioning. If information movement in some register depends on the sequence made by other register, then the generated [[gamma|gamma]] becomes complicated. So non-uniform movement of the information in some [[Cryptographic generator|generator]] units by a [[Cryptographic generator|generator]] is used. Such schemes also can be constructed on the transformations with convenient realization, for example, on [[Linear shift register|the linear shift registers]].

The [[Cryptographic generator|generators]] constructed by such principle are called [[Cryptographic generator|generators]] with non-uniform movement. The modification of movement rules leads to a modification of [[gamma|a gamma]].

Widely used method of reaching of non-uniform movement is the cascade connection of ''m'' automaton when each previous automaton is called control in relation to the following, the last automaton is called generating. If ''m''>2, then such connection of automata is called cascade. Other method is some automata generating [[gamma|a gamma]] jointly.

====Generators of «[[File:формула 24.gif]] steps»====
If in the two-cascade scheme the control automaton is the filter [[Cryptographic generator|generator]] on [[Linear shift register|the linear shift register]] of ''n'' length with the ''f''(''x'') filter function, and the generating automaton is [[Linear shift register|the linear shift register]] of ''m'' length, which do  [[File:формула 25.gif]] or [[File:формула 26.gif]] steps depending on an control sign, [[File:формула 27.gif]],  then automaton is called [[Cryptographic generator|the generator]] of «[[File:формула 28.gif]] steps» [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]]. If [[File:формула 29.gif]], [[File:формула 30.gif]] then [[Cryptographic generator|the generator]] of «[[File:формула 31.gif]] steps» is called the "stop-forward" [[Cryptographic generator|generator]]. The cryptographic scheme of [[Cryptographic generator|the generator]] of «[[File:формула 32.gif]] steps» is represented in figure 3.

   [[File:Delta1.jpg|frame|Figure 3. The cryptographic scheme of the generator of «[[File:формула 24.gif]] steps»|center]]

Let [[Linear shift register|the linear shift registers]]  have maximum periods, [[File:формула 33.gif]] and [[File:формула 34.gif]]  are states LSR-1 and LSR-2 in the ''i''-th step accordingly, ''i''=1,2,…
The [[gamma|gamma]] obtaining equations are:
[[File:формула 35.gif|center]]
where [[File:формула 36.gif]] is sum movement depth of LSR-2 after ''i'' functioning steps and [[File:формула 37.gif]].

[[File:формула 38.gif]] does not depend on ''x'' [[File:формула 45.gif]] ''i'' is multiple of control [[gamma|gamma]] period [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]]. When ''i'' is multiple of [[File:формула 39.gif]], we use designation [[File:формула 40.gif]]. The period of [[gamma|a gamma]] made by [[Cryptographic generator|the generator]] of «[[File:формула 41.gif]] steps» is equal to [[File:формула 42.gif]].

The [[gamma|gamma]] [[Linear complexity|linear complexity]] estimation is [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ny75|[Ny75]]]:
[[File:формула 43.gif|center]]
where [[File:формула 44.gif]] is the period of LSR-1 output sequence.

====Generators of intermittent steps====
The complication of the «stop-forward» [[Cryptographic generator|generator]] is [[Cryptographic generator|the generator]] of intermittent steps [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]]. Its [[gamma|gamma]] is the [[gamma|gammas]] sum of two «stop-forward» [[Cryptographic generator|generators]] which use [[Linear shift register|the linear shift registers]] LSR-2 and LSR-3 of ''m'' and ''r'' lengths accordingly. Both generating registers have the general operating block which is the filter [[Cryptographic generator|generator]] with ''f''(''x'') filter function on [[Linear shift register|the linear shift register]] of ''n'' length. If the control sign is equal to 1 in the ''i''-th step is then LSR-2 does 1 step and LSR-3 stands still and if the control sign is equal to 1 then the contrary way is. A [[Cryptographic generator|generator]] key is the initial states of [[Linear shift register|linear shift registers]].

Let all registers have maximum periods, [[File:формула 46.gif]], [[File:формула 47.gif]], and [[File:формула 48.gif]] are states of LSR-1, LSR-2 and LSR-3 in the ''i''-th step accordingly, ''i''=1,2,… Then sum movement depth of LSR-2 after ''i'' functioning steps is equal to [[File:формула 49.gif]].

The [[gamma|gamma]] obtaining equations are:
[[File:формула 50.gif|center]]

The period of [[gamma|a gamma]] made by [[Cryptographic generator|the generator]] of intermittent steps is equal to [[File:формула 51.gif]].

If the characteristic polynomials of LSR-2 and LSR-3 are various and nonreducible and periods of ЛРС-2 and ЛРС-3 output sequences are coprime, then the period of [[gamma|a gamma]] made by [[Cryptographic generator|the generator]] of intermittent steps is equal to product of [[Linear shift register|linear shift registers]] output sequences periods [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]] произведению длин периодов выходных последовательностей [[Линейный регистр сдвига|линейных регистров сдвига]], and the [[gamma|gamma]] [[Linear complexity|linear complexity]] submits to the estimations:
[[File:формула 52.gif|center]]

Both [[Cryptographic generator|the generator]] of «[[File:формула 53.gif]] steps», and [[Cryptographic generator|the generator]] of intermittent steps are broken by approbation of the control [[Linear shift register|linear shift register]] initial state. Owing to it the effective key length of [[Cryptographic generator|the generator]] is close to the control register length.

====Gollman cascade generators====
Gollman cascade [[Cryptographic generator|generator]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]] constructed on ''m'' [[Linear shift register|linear shift registers]]  with maximum periods, is good because it can be used for generation of [[gamma|a gamma]] with the huge period and [[Linear complexity|linear complexity]]. In this scheme the first register controls the second one, the second register controls the third one and etc.

If all [[Linear shift register|linear shift registers]]  have ''n'' length and various primitive characteristic polynomials [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#GoCh89|[GoCh89]]], then the period of [[gamma|a gamma]] made by the ''m''-cascade [[Cryptographic generator|generator]] is equal to [[File:формула 54.gif]], and [[Linear complexity|the linear complexity]] is equal to [[File:формула 55.gif]].

There is a correlation between the first register output [[gamma|gamma]] and the [[Cryptographic generator|generator]] [[gamma|gamma]], which allow to construct an effective method of breaking of [[Linear shift register|the linear shift registers]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Me93|[Me93]]].

====Contracting generators====
Other principle of a movement control is used in the contracting [[Cryptographic generator|generator]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]] which is constructed on the parallel [[Linear shift register|linear shift registers]]  with the maximum periods. [[gamma|A gamma]] is the output from LSR-2 only when control sign of LSR-1 is equal to 1, otherwise generated signs are ignored.

[[gamma|The gamma]] of the contracting [[Cryptographic generator|generator]] has high period and [[Linear complexity|linear complexity]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#CoKrMa94|[CoKrMa94]]]. Cryptographic weaknesses are only when characteristic polynomials contain few nonzero factors. Realization of the contracting [[Cryptographic generator|generator]] has a high velocity.

===Generators with additional memory===
When [[Cryptographic generator|generators]] are designed, additional memory registers are used for reduction of correlation between [[gamma|a gamma]] and some intermediate sequences of [[Cryptographic generator|the generator]]. There are some methods of additional memory using in [[Cryptographic scheme of genarator|cryptographic schemes]].

====MacLaren-Marsaglia generators====
In MacLaren-Marsaglia [[Cryptographic generator|generators]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]] the initial sequence becomes complicated by the memory register and control sequences.

Let there is a memory register of ''m'' length in which elements of ''X'' set are noted. 2 control sequences over a ring [[File:формула 56.gif]] are used for map of entering sequence over ''X'' in output sequence over ''X''. One is used for entry to memory control of and other is used for reading from memory control.

Let [[File:формула 57.gif]] are periods of input, output and control sequences accordingly. The sequence over ''X'' set is called full if it contains all elements of ''X'' set.

If the input and control sequences are periodic and the control sequences are full [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]], then the output sequence is also periodic and [[File:формула 58.gif]], where [[File:формула 59.gif]].

====Shift register with transposition feedback====
Other method of additional memory using is connected with the scheme which is called the shift register with transposition feedback (SRTF) [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]]. SRTF is the autonomous shift register having of additional memory, which called the transposition register. The most simple variety of SRTF is constructed on the [[Linear shift register|linear shift register]] and the additional memory register for entry of integers from 0 to [[File:формула 60.gif]], where ''r'' is the number of feedback function variables.
  
Let [[File:формула 61.gif]] are noted in register and [[File:формула 62.gif]]is noted in additional memory. In a following step the last bit arrives on the output sequence and memory and free register unit are updated as follows:

1)	[[File:формула 63.gif]] is calculated, where [[File:формула 64.gif]] are the binary factors from which ''r'' factors are equal to 1;

2)	[[File:формула 65.gif]] is calculated;

3)	the low bit of [[File:формула 66.gif]] is noted in a free register unit and the remaining bits corresponding to [[File:формула 67.gif]] are new contents of memory.

The estimation of the period of [[gamma|a gamma]] made by SRTF is [[File:формула 68.gif]] [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10|[Ф10]]].

The important feature of SRTF is the fact that the traditional mathematical apparatus of final fields is inapplicable for their analysis. Therefore the theory based on 2-adic numbers [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ke76|[Ke76]]] is developed for study of schemes with transposition.

Using of SRTF in cryptosystems considerably complicates the cryptanalysis of [[Cryptographic generator|generators]] on the correlation attacks  [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Go94|[Go94]]]. So the Gollman cascade [[Cryptographic generator|generators]]  constructed on the some SRTFs are perspective.

==Stream ciphers and their cryptanalysis==

''' A stream cipher ''' - is a symmetric cipher in which each plaintext character is transformed into a symbol of the ciphertext depends not only on the key used , but also on its position in the flow of the plaintext . Stream ciphers are one of the components of the symmetric encryption schemes , the general form of which is usually presented in the form of one or more shift registers and a nonlinear function [[ References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10 | [Ф10]]] . Since itself [[Linear recurrent Register ( LRR ) | linear recurrent Register]] ( LRR ) - linear device , the task of the nonlinear function ( NLF ) - introduction of nonlinearity in the output sequence .
Stream ciphers convert plaintext into ciphertext bit by bit . The simplest implementation is shown in Figure 4 . Generated bitstream : [[File: form2.jpg]], called [[gamma | gamma]] . Bitstream plaintext [[File: form3.jpg]] and flow [[ gamma | gamma]] undergo surgery XOR, the result is a bit stream cipher text [[File:form4.jpg]], where [[File: form5.jpg ]] , this mode is called XOR encryption . Decryption uses a similar formula [[File: form6.jpg]]. 
[[File: img1.jpg | frame | Figure 4 . The process of encryption and decryption | center]]
Distinguish between synchronous and self-synchronizing stream ciphers .
 
===Synchronous stream ciphers===

Synchronous stream ciphers ( SSC ) is characteristic independence sequence [[gamma | gamma]] of the plaintext and ciphertext for encryption with decryption .

   [[File: img2.jpg | frame | Figure 5 . Encryption using a SSC | center]]

SSC pluses :
* Do not propagate distortions text characters , which often occur during transmission over communication channels.
If you are sending the message was garbled mi sign or transfer over the communication channel has been distorted sign of ci, then the synchronous operation of generators , these distortions will not affect the correctness of the decryption of all characters except the i-th .
* Protects against unauthorized transmitted text insertions and deletions , as in these cases will not be synchronized , and the intervention will show up immediately .
SSC minus:
* Does not protect against intentional substitution segment messages to another segment of the same length .
Segment known plaintext attacker can easily substitute another that Transcribe at a predetermined interval text of the same length .

Conditions to ensure a high level of protection of information through the NPN running [[gamma | gamma]] must have [[ References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10 | [Ф10]]] :
* A greater length of the period;
* High [[Linear complexity | linear complexity]] ;
* Statistical characteristics [[Multigramma | multigramm]] close to the corresponding characteristics of ideal random sequences .

=== Self-synchronizing stream ciphers === 

Self-synchronizing stream ciphers ( SSSC ) , they are characterized by dependence generated [[gamma | gamma]] from the previous ciphertext bits [[ References to section Cryptographic generators. Stream ciphers and their cryptanalysis#Ф10 | [Ф10]]] . Each begins with a message to encrypt a random interval of n characters that does not carry substantial loads, he shifruestya transmitted and then decrypted . Due to mismatch of the initial states of generators, this segment stands incorrectly , but after the transfer n characters generators synchronized.
   [[File: img3.jpg | frame | Figure 6. Encryption using SSSC | center]]

SSSC pluses :
* Mixing statistics plaintext ;
SSSC minus :
* Reproduction errors
Single error in the ciphertext n generates errors in the plaintext .
* Vulnerable to simulate posts
Intruder can record any section of them intercepted ciphertext and later send it to the address . After a few inconsistencies in the beginning of the message (up to n characters) sent segment Transcribe true, and the recipient will not be able to determine that the message received outdated .
To protect against imitation messages must use the timestamp or change keys for each new message .

===Cryptanalysis=== 

Cryptographic stream cipher resistance determined by the proximity of its properties to the property an ideal cipher. Therefore, every stream cipher should be evaluated as more or less skillful imitation of the ideal cipher. Best imitation of an ideal cipher is obtained when the ciphering sequence maps simulates a sequence of independent random mappings .

Cryptanalysis methods stream encryption schemes can be divided into three classes:
* Analytical attack ;
* Statistically attack ;
* Power Attack .

====Power Attack==== 

'''''Power Attack''''' based on the principle of exhaustive search of all possible key combinations .
If the computational complexity of cryptanalysis schemes less than the computational complexity of exhaustive search of all key combinations this cipher , it is considered that the attack was successful.

Correctness key found with the knowledge of open and encrypted text is checked quite simple - when testing the plaintext is encrypted , and the result is compared with the ciphertext . Coincidence suggests that the desired key is found .

Somewhat more complicated with the attack on the basis of only the ciphertext . In this case, the presence of any additional information about the plain text , such as  [[ References to section Cryptographic generators. Stream ciphers and their cryptanalysis#П09 | [П09]]] :

1) if the plaintext is meaningful in any language , the ciphertext must be longer than the unicity distance ( number of characters ciphertext required for unique recovery key) ;

2) if the plaintext is binary, need information about what he is is ( text structure ) .
Despite the simplicity of the method , there are various methods to improve it , in particular, it is very simple parallelization .

====Analytical attack==== 
'''''Analytical Attack''''' - these are the attacks, in which an algorithm for constructing the attack is based on the principles of analytical dissection kriptoskhemy . This class can be divided into two subclasses [[ References to section Cryptographic generators. Stream ciphers and their cryptanalysis#С13 | [С13]]]: the encryption methods of cryptanalysis [[gamma | gamma]] procedures and methods of cryptanalysis key initialization and re-initialization . In the first subclass , due to the specifics of the principles of construction of stream ciphers , the main type of attacks on data circuits are correlation attack , the basic idea of which is to find a correlation between the encryption [[gamma | gamma]] and various linear combinations of keys ( shift register ) . Object of study in the correlation attacks are the nonlinear functions that introduce non-linearity in the output shift register sequence - so each time , depending on the device used nonlinear function realization correlation attacks will be different and will be based on the specific structure of the analyzed function .

It is assumed that a cryptanalyst known description of the generator ( generators polynomials form of a nonlinear transformation) , it has an open and closed its corresponding text. Problem cryptanalyst - definition of the applicable key ( initial population ) . Figure 7 shows the best-known analytical attacks to the SSC .
   [[File: img4.jpg | frame | Figure 7 . Analytical attack | center]]

* '''''Correlation Attack (CA)'''''
SC and use the most common correlation output sequence encryption schemes output sequence registers to restore the initial filling of the latter.

Attacks of this class are the following attacks :

1. Basic SC .

2 . Attacks based on parity checks nizkovesovyh .

3 . Attacks based on the use of convolution codes.

4 . Attacks that use the technique of turbo codes .

5 . Attacks based on the recovery of linear polynomials.

6. Fast Chepyzhova SC , Johansson , Smits.

Under fast spacecraft understand attacks , computational complexity is significantly less than the computational complexity of security attacks.

Korrellyatsionnaya attack quite easily applicable in case complications Boolean functions used in generators ( filtering functions , combining functions, the functions of domination ) have good linear approximations . It is believed that it is effective if there is a linear approximation is true for all sets δ truth table function where δ> 0,5.

* '''''Compromise "time - memory"'''''
It is assumed that a cryptanalyst known diagram of the device and some fragment of the encryption [[gamma | gamma]] , then the purpose of this attack is to restore the initial state of the shift register by a fragment of the encryption [[gamma | gamma]] .
The complexity of the attack depends on the length of the intercepted [[gamma | gamma]] and the size of the internal state of the cipher. Such an attack has been successfully applied to cryptoalgorithms A5 / 1 . In general, the attack involves the following steps :

1. Built a large dictionary containing all possible pairs of " state-output ."

2 . It is assumed that the code is in a fixed state ( the assumption of certain filling all the memory cells) . Based on these inputs , the output sequence is generated and then view the captured output sequence in order to find compliance with the generated output. In case of conformity , a fixed state with a high probability of initial filling is considered sensitive, otherwise the algorithm continues .

* '''''"Presuppose and stipulate"'''''
It is assumed that a cryptanalyst known encrypts [[gamma | gamm]], the number of shifts between the outputs of the register and the feedback polynomial . In general, the attack consists of the following steps :

1. Assumed the cell contents of the register.

2 . Determined the complete filling of the register by applying a linear recurrence of the register on the basis of assumptions .

3 . Generated output sequence . If it is equivalent to the encryption [[gamma | gamma]] , the assumption is considered valid , otherwise - go to step 1.

* '''''Contrails attack'''''
It is assumed that the known polynomial feedback filter function and a sequence of points detachably . The purpose of this attack - the restoration of the initial state of the shift register by a fragment of the encryption sequence.

* '''''Key loading , initialization / reinitialization'''''
Since no single algorithm load exists, each time depending on the circuit structure , a key loading procedure will be different .
Is desired design , eliminating the download key means of linear operations and zero filling registers, each bit register must be initialized nonlinear function of each bit of the key used. Using linear operations makes it possible to use cryptanalysis by solving linear equations.

Is much easier to solve the problem of cryptanalysis for two plaintexts differ only insert one or more characters . In this case, use the following analytical recovery attack .

'''Attack by inserting a character.'''
Let the plaintext [[File: x.jpg]] c using [[gamma | gamma]] [[File: k.jpg]] converted to ciphertext [[File: y.jpg]] in accordance with the above equations encryption. Cryptanalyst known ciphertext , but not known plaintext and
[[gamma | gamma]] .
We also assume that the cryptanalyst has cryptogram received encoding using the same [[gamma | gamma]] modified plaintext inset for a position known bits x '. Suppose there is a modified plaintext [[File: seq1.jpg]] and the corresponding ciphertext have [[File: seq2.jpg]]
Two ciphertexts can be determined from the date of insertion , and [[gamma | gamma]] , and plain text .

Character insertion position can be determined by comparing the original and modified ciphertexts . If the value is inserted character is unknown, the value of its options are moving .
To protect against attacks by inserting a character enough not to use the same intervals [[gamma | gamma]] .

====Statistical attack==== 
'''''Statistical attacks''''' based on the evaluation of the statistical properties of the encryption [[gamma | gamma]] . This class is divided into two sub- methods , and the sequence complexity of cryptanalysis techniques of cryptanalysis properties of the encryption [[gamma | gamma]] . Methods of the first subclass are aimed at identifying the possible generation of sequences similar to the encryption [[gamma | gamma]] , in some other way , the complexity of the implementation of which would be smaller compared to the method of generating the encryption [[gamma | gamma]] Ideally found method must be applicable in practice. These methods use the concept of [[Linear complexity | linear complexity]] , Profile [[Linear complexity | linear complexity]] , quadratic scale. Second subclass methods aimed at identifying possible imbalance in the output sequence kriptoskhemy with a view to finding ways assumptions next bit output sequence with a probability better than random selection . These methods operate on a variety of statistical tests , the selection of necessary and sufficient number of tests - the prerogative of the cryptanalyst .

Management [[gamma | gamma]] should be longer period ( repeatedly exceeding the length of the plaintext ) and does not contain long repetitive segments. Otherwise cryptanalysis much easier.

'''Analysis ciphers using a scale with the same repetitive segments.'''

Consider a stream cipher that implements the modular equations with XOR encryption

[[File: 1x.jpg]], i = 1,2, ...

Let cryptanalyst has cryptograms [[File: 2.jpg]] and [[File: 3.jpg]], corresponding plaintext [[File: 4.jpg]] and [[File: 5.jpg]] using the same segments [[gamma|gamma]] . Need to recover plaintext.

The difference data is not dependent on cryptograms [[gamma | gamma]] :

[[File: 6.jpg]], i = 1,2, ...

Consequently, the solution of the problem reduces to the selection of two plaintexts , the difference of which is given . Guessing the same plaintext fragment ( using pre -known standards or themes inherent in this source open messages ) , you can calculate a fragment of another plaintext .

Search options continue guessed text fragments can be realized as brute characters ordered by descending posterior probabilities .

This method does not always lead to success. However, if the right to recover part of the text , it allows the cryptanalyst to recover [[gamma | gamma]] and solve the problem of determining the key signs of the known [[gamma | gamma]] .

===Minimum requirements cryptographically strong stream cipher===

Minimum requirements for confrontation cryptanalytic attacks when constructing circuits stream encryption [[ References to section Cryptographic generators. Stream ciphers and their cryptanalysis#С13 | [С13]]] :
* Each bit of the initial state of the register should be a function of the nonlinear transformation of all bits of the key

* In the construction of nonlinear functions , these functions must satisfy the criteria for persistence : be balanced , have high nonlinearity , have a high algebraic degree .

* If the key length ''k'' bit internal state of the generator (internal memory ) must be at least ''k'' bit.

* Minimum register length must be at least ''l'' = 100 bits generator polynomial have approximately ''l'' / 2 non-zero coefficients of the feedback .

* For maximum [[Linear complexity | linear complexity]] generating polynomial degree should be a prime number .

* To generate a register sequence of maximal length and high [[Linear complexity | linear complexity]] this register should be based on a primitive polynomial feedback , moreover , length ''l'' LRR and algebraic order nonlinear function d must be large enough , to the value [[File: form1.jpg]] was significantly greater than the length of the encryption [[gamma | gamma]] .

* When using multiple registers their length must be relatively prime .

==Glossary== 


* [[Autonomous automaton]]

* [[Gamma]]

* [[Cryptographic scheme of genarator]]

* [[Cryptographic generator]]

* [[Linear complexity]]

* [[Linear shift register]]

* [[Linear recurrent Register (LRR)]]

* [[Multigramma]]

==References==

Go to [[References to section Cryptographic generators. Stream ciphers and their cryptanalysis | list of references]] to the section "Cryptographic generators. Stream ciphers and their cryptanalysis."


Avezova J., Gendugova D., 2013

[[Part I. Foundations of Cryptography (Cryptographic Primitives) | Back]]