Cryptographic generators. Stream ciphers and their cryptanalysis

From CryptoWiki
Revision as of 23:56, 25 November 2013 by 13-02-GendugovaDV (Talk | contribs)

Jump to: navigation, search

Avezova Y.,

Gendugova D.


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 [ C13 ] . 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 .


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 .