Cryptographic generators. Stream ciphers and their cryptanalysis

From CryptoWiki
Revision as of 17:40, 7 December 2013 by 13-04-AvezovaYE (Talk | contribs)

Jump to: navigation, search

Contents

Cryptographic generators

Cryptographic generators are used for development of cryptosystem keys and gamma for stream ciphers.

Base of cryptographic generators

Base element of Cryptographic generators is the linear shift register with maximum period which output 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 the linear shift register is not good cryptographic generators, and using of the linear shift register when you construct 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. The autonomous automaton Формула 1.gif, where h is the linear transformation of Формула 2.gif realized by the linear shift register of n length over P field with f'(x) feedback function,Формула 3.gif is the filter function, is called the filter generator [Ф10].

The filter generator is called nonlinear, if the filter function is nonlinear. The cryptographic scheme of the filter generator is represented in figure 1.

Figure 1. The cryptographic scheme of the filter generator

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

Nonlinear properties of a gamma are provided by a choice of nonlinear filter function. Let d is the filter function degree of nonlinearity. It is known [Ф10], that the linear complexity of a gamma made by the filter generator estimation is Формула 5.gif, where Формула 6.gif s the number of various conjunctions on n variables of a rank from 0 to d.

The gamma the linear complexity estimation of the filter generator depends on properties of filter function. For example, for bent-functions [KiSc83] if 4|n, then Формула 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 the gamma with high the linear complexity is known [BeGu85].

It is known [Ru85], that a part of the filter generator, constructed on the linear shift register with maximum period and n length, where n is the prime number for which the linear complexity is the greatest, tends to 100%.

Combining generators

The combining generator is the complication of the filter generator. It is constructed on m>1 linear shift registers over P field and Формула 8.gif combining function which input is the signs of the linear recurrent sequences made by linear shift registers. Let Формула 9.gif is the length of LSR-j, Формула 10.gif. The cryptographic scheme of the combining generator on two LSRs is represented in figure 2.

Figure 2. The cryptographic scheme of the combining generator

The combining generator is called nonlinear, if the combining function is nonlinear.

Initial states of all linear shift registers are the initial state of the generator. If the initial state of all LSRs is nonzero then the corresponding initial state of the combining generator is called nonsingular.

Each Формула 11.gifpolynomial over P final field correspond to a Формула 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 Формула 14.gif. The linear complexity of a gamma mde by the combining generator estimation is Формула 15.gif [Ф10].

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

If P is the simple field, and characteristic polynomials of all linear shift registers are primitive and have pairwise coprime degrees, then Формула 16.gif [А05].

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

Examples of combining generators:

1) Geffe generator;

2) threshold generator.

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

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

Generators with non-uniform movement

The best cryptographic properties of filter and combining generators are reached when filter and combining functions of high degree of nonlinearity are used. So certain complexities of generators engineering and realization are. An important feature of these 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 becomes complicated. So non-uniform movement of the information in some generator units by a generator is used. Such schemes also can be constructed on the transformations with convenient realization, for example, on the linear shift registers.

The generators constructed by such principle are called generators with non-uniform movement. The modification of movement rules leads to a modification of 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 a gamma jointly.

Generators of «Формула 24.gif steps»

If in the two-cascade scheme the control automaton is the filter generator on the linear shift register of n length with the f(x) filter function, and the generating automaton is the linear shift register of m length, which do Формула 25.gif or Формула 26.gif steps depending on an control sign, Формула 27.gif, then automaton is called the generator of «Формула 28.gif steps» [Ф10]. If Формула 29.gif, Формула 30.gif then the generator of «Формула 31.gif steps» is called the "stop-forward" generator. The cryptographic scheme of the generator of «Формула 32.gif steps» is represented in figure 3.

Figure 3. The cryptographic scheme of the generator of «Формула 24.gif steps»

Let the linear shift registers have maximum periods, Формула 33.gif and Формула 34.gif are states LSR-1 and LSR-2 in the i-th step accordingly, i=1,2,… The gamma obtaining equations are:

Формула 35.gif

where Формула 36.gif is sum movement depth of LSR-2 after i functioning steps and Формула 37.gif.

Формула 38.gif does not depend on x Формула 45.gif i is multiple of control gamma period [Ф10]. When i is multiple of Формула 39.gif, we use designation Формула 40.gif. The period of a gamma made by the generator of «Формула 41.gif steps» is equal to Формула 42.gif.

The gamma linear complexity estimation is [Ny75]:

Формула 43.gif

where Формула 44.gif is the period of LSR-1 output sequence.

Generators of intermittent steps

The complication of the «stop-forward» generator is the generator of intermittent steps [Ф10]. Its gamma is the gammas sum of two «stop-forward» generators which use 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 generator with f(x) filter function on 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 generator key is the initial states of linear shift registers.

Let all registers have maximum periods, Формула 46.gif, Формула 47.gif, and Формула 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 Формула 49.gif.

The gamma obtaining equations are:

Формула 50.gif

The period of a gamma made by the generator of intermittent steps is equal to Формула 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 a gamma made by the generator of intermittent steps is equal to product of linear shift registers output sequences periods [Ф10] произведению длин периодов выходных последовательностей линейных регистров сдвига, and the gamma linear complexity submits to the estimations:

Формула 52.gif

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

Gollman cascade generators

Gollman cascade generator [Ф10] constructed on m linear shift registers with maximum periods, is good because it can be used for generation of a gamma with the huge period and 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 registers have n length and various primitive characteristic polynomials [GoCh89], then the period of a gamma made by the m-cascade generator is equal to Формула 54.gif, and the linear complexity is equal to Формула 55.gif.

There is a correlation between the first register output gamma and the generator gamma, which allow to construct an effective method of breaking of the linear shift registers [Me93].

Contracting generators

Other principle of a movement control is used in the contracting generator [Ф10] which is constructed on the parallel linear shift registers with the maximum periods. A gamma is the output from LSR-2 only when control sign of LSR-1 is equal to 1, otherwise generated signs are ignored.

The gamma of the contracting generator has high period and linear complexity [CoKrMa94]. Cryptographic weaknesses are only when characteristic polynomials contain few nonzero factors. Realization of the contracting generator has a high velocity.

Generators with additional memory

When generators are designed, additional memory registers are used for reduction of correlation between a gamma and some intermediate sequences of the generator. There are some methods of additional memory using in cryptographic schemes.

MacLaren-Marsaglia generators

In MacLaren-Marsaglia generators [Ф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 Формула 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 Формула 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 [Ф10], then the output sequence is also periodic and Формула 58.gif, where Формула 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) [Ф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 and the additional memory register for entry of integers from 0 to Формула 60.gif, where r is the number of feedback function variables.

Let Формула 61.gif are noted in register and Формула 62.gifis 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) Формула 63.gif is calculated, where Формула 64.gif are the binary factors from which r factors are equal to 1;

2) Формула 65.gif is calculated;

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

The estimation of the period of a gamma made by SRTF is Формула 68.gif [Ф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 [Ke76] is developed for study of schemes with transposition.

Using of SRTF in cryptosystems considerably complicates the cryptanalysis of generators on the correlation attacks [Go93]. So the Gollman cascade 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 [ F10 ] . Since itself 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 : Form2.jpg, called gamma . Bitstream plaintext Form3.jpg and flow gamma undergo surgery XOR, the result is a bit stream cipher text Form4.jpg, where Form5.jpg , this mode is called XOR encryption . Decryption uses a similar formula Form6.jpg.

Figure 4 . The process of encryption and decryption

Distinguish between synchronous and self-synchronizing stream ciphers .

Synchronous stream ciphers

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

Figure 5 . Encryption using a NPN

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 must have [ F10 ] :

  • A greater length of the period;
  • High linear complexity ;
  • Statistical characteristics 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 from the previous ciphertext bits [ F10 ] . 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.

Figure 6. Encryption using SSSC

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 [ P09 ] :

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 [ C13 ]: the encryption methods of cryptanalysis 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 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 .

Figure 7 . Analytical attack
  • 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 , then the purpose of this attack is to restore the initial state of the shift register by a fragment of the encryption gamma . The complexity of the attack depends on the length of the intercepted 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 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 , 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 X.jpg c using gamma K.jpg converted to ciphertext Y.jpg in accordance with the above equations encryption. Cryptanalyst known ciphertext , but not known plaintext and gamma . We also assume that the cryptanalyst has cryptogram received encoding using the same gamma modified plaintext inset for a position known bits x '. Suppose there is a modified plaintext Seq1.jpg and the corresponding ciphertext have Seq2.jpg Two ciphertexts can be determined from the date of insertion , and 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 .

Statistical attack

Statistical attacks based on the evaluation of the statistical properties of the encryption gamma . This class is divided into two sub- methods , and the sequence complexity of cryptanalysis techniques of cryptanalysis properties of the encryption gamma . Methods of the first subclass are aimed at identifying the possible generation of sequences similar to the encryption gamma , in some other way , the complexity of the implementation of which would be smaller compared to the method of generating the encryption gamma Ideally found method must be applicable in practice. These methods use the concept of linear complexity , Profile 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 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

1x.jpg, i = 1,2, ...

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

The difference data is not dependent on cryptograms gamma :

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 and solve the problem of determining the key signs of the known gamma .

Minimum Requirements cryptographically strong stream cipher

Minimum requirements for confrontation cryptanalytic attacks when constructing circuits stream encryption [ C13 ] :

  • 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 .
  • To generate a register sequence of maximal length and high 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 Form1.jpg was significantly greater than the length of the encryption gamma .
  • When using multiple registers their length must be relatively prime .

Glossary

References

Go to list of references under the heading "Cryptographic generators. Stream ciphers and their cryptanalysis."


Avezova JE, Gendugova DV, 2013

Back