Analysis of Different Types of Attacks on Stream Ciphers and Evaluation and Security of Stream Ciphers

{LANG_NAVORIGIN} Encryption
Arani Dasgupta 04/27/2005

Techniques for Security Evaluation

The techniques for the security evaluation of stream ciphers are based on the following :

Consideration of the underlying structure of the stream cipher as well as the keystream itself;
Resistance against the attack for predicting a keystream or either reducing or removing the uncertainties in the secret key are the plaintext; this may include:
1. general attacks applicable to a class of stream ciphers.
2. specialized ciphers developed for a particular stream cipher.

It is customary while analyzing stream ciphers to consider known plaintext attacks which essentially means that the attacker, the cryptanalyst has a large volume of keystream. Consequently, the cryptanalyst’s task can be classified to the following:

Distinguishing attack: This is most basic type of cryptanalytic attack. Distinguishing attack can be successful if it is possible to distinguish the output of a cipher from the output of a random permutation. These are closely related to “cipher detection” attacks which can tell that a certain algorithm has been used in communication. In many cases, the distinguishing attacks open doors for more sophisticated key-recovery attacks.
Partial knowledge of the plaintext: In this attack the cryptanalyst has partial knowledge of the plaintext.
Decryption: In this method the attacker is capable of decrypting part of the encrypting traffic. This ability may be reached without the knowledge of the secret key. For example in any encryption system which is an involution (self-inversing), decryption of the cipher can be achieved by re-encrypting the cipher text (this is possible in adaptive chosen plaintext attack).
Encryption: In this method the attacker is able to encrypt meaningful plaintext under unknown secret key.
Partial key recovery: In this attack some predicate of the secret key is gained by the cryptanalyst. This is usually the first step towards total recovery of the secret key.
Total key recovery: This is the most fatal cryptanalytic attack. Once the key has been fully recovered the cryptanalyst is free to do anything he wants.

The techniques used to analyze stream ciphers typically use either mathematical and statistical properties or approximations to the output. The security evaluation should include the main general characteristics of a stream cipher and the attacks to which it should be resistant as given bellow. A good stream cipher must pass all these consideration, but it is only a necessary request and final security evaluation result should include other aspects including specific issues related to a particular stream cipher.

A. General Characteristics to be Evaluated

Period: Clearly, the period of keystram sequence employed in a stream cipher must be large enough that the keystream has virtually no chance of being repeated.

Keystream complexity: Linear and Nonlinear.
The linear complexity of a sequence is the length of the shortest LFSR that can produce the sequence. The linear complexity of a sequence is easily calculated using the Berlekamp-Massey algorithm. If this linear complexity is too small, then an attacker can reproduce the sequence on a simple device and recover the secret key. Other complexity measures (nonlinear complexity, for example) should have appropriate values, as well.

Statistical properties: Ideally, the keystream generator should produce a memory-less sequence of bits. Accordingly, the binary equivalent of a keystream sequence should be a realization of independent identically distributed random variables with the parameter equal to 0.5. If the keystream deviates from these distributions, then an attacker may be able to use this deviation to predict future keystream bits. The same characteristics can be requested for certain internal keystream generator sequences as well. The sets of statistical tests which a good stream cipher should pass are the following ones (specified in [1] and [2]):

Dyadic Complexity test	        Percolation test
Collision test	                Frequency test
Gap test	                Overlapping m-tuple test
Constant Run test	        CouponCollector’s test
Universal Maurer test	        Poker test
Spectral test	                Linear Complexity test
Rank test	                Correlation test
Non-linear complexity test	Ziv-Lempel complexity test

B. General Attacks to be Evaluated

Time-Memory trade-off: In this type of attacks, the time taken to find the secret key is reduced at the expense of the memory required to mount such an attack. It has two phases : pre-processing phase and real-time processing phase. In the preprocessing phase, which can take a very long time, the cryptanalyst explores the algorithm and summarizes his findings, which is not tied to a single, in a table. During the real-time phase, the attacker is provided with actual data produced based on a particular unknown key, and his goal is to use the pre-computed tables in order to find the key as quickly as possible.
The time - memory - data trade-off is based on the birth-day paradox. The birthday paradox implies that two random subsets of a space with N points are likely to intersect when the product of their sizes exceeds N.
Divide and Conquer: In such an attack a part of the key is guessed and the constraint now placed on the keystream may make the determination of the rest of the key faster than searching the rest of the key.
Correlation Attacks: In a correlation attack, the output of a keystream generator is correlated in some manner with the output of much simpler device, such as component LFSR of the generator. This correlation can sometimes be exploited to determine the key. A very important class of the correlation attacks is fast correlation attack. the basic idea of all reported fast correlation attacks include the following two main steps:
- Transform the cryptographic problem into a suitable decoding problem.
- Apply (devise) an appropriate decoding algorithm.
There are two main approaches to realization of fast correlation attacks. The first one is based on decoding technique for block codes (introduced in [8] and [9]) and the second one based on decoding technique for convolution code (proposed in [6] and [7]).
Distinguishing Attack: In such attacks, a method is given for distinguishing the keystream from a genuinely random sequence
Rekeying Attack: There are many uses for which a stream cipher is re-keyed. It is sometimes possible to exploit this re-keying in order to find the keys used.
Linear Consistency Attack: The idea behind this attack is to find a solution for A(K_i)x = b with A(K_i) being a matrix filled with a subkey K_i of the complete key K and b being a piece of output sequence. If a solution is found, the correct subkey K_i can be identified. This is well possible if b is long. This attack successively reveals the complete key K.
Linear syndrome method: It is a successful attack if it is possible to write parts of the output sequence b as b = a + x with a being a piece of a known sequence from a previous period and x being a sequence of only 0’s or only 1’s which occur sparsely. For sequence generators having a short period length this attack could be successful.
Linear Attack: Some linear combination of the input and output bits of the non-linear function executed by the keystream generator is more often than 50% zero than one (or vice versa). By masking one or more bits of the input bitstream it might be possible to find some sub sequences for which the keystream generator is not generating a purely random bit stream. By finding a large number of such sub sequences, the keystream generator output can be predicted to be random or not random for a number of bits to follow.

Conclusion

Recently the following trends have been noticed in the design of stream ciphers

32/64 bit words are used as elements.
Native microprocessor instruction are used which makes them suited to a specific platform.
Techniques from block cipher are being incorporated so that increasingly mixed modes of encryption is being used.
Avoid linear structures so that it becames more resistant to different forms of attacks.
Concepts from different domains of algebra are being used.

Any new stream cipher algorithm should be designed such that it is resistant to the following types of attacks:

Degree of linearity tests.
Distinguishing attacks.
Statistical tests.
Guess and set attacks.
Side Channel attacks.
Correlation attacks.
Re-keying attacks.
Algebraic attacks.

Stream ciphers seem to be inherently weaker than block ciphers as :

Attacks on block ciphers (like differential attacks) are also applicable to stream ciphers.
Attacks on stream ciphers (like correlation attacks) are not applicable to block ciphers.
Algebraic attacks seem to be more effective against stream ciphers.
Guess and set attacks on stream ciphers can recover either the key or any plaintext.
Generic time/memory trade-off attacks on stream ciphers (TM²D²=N² )are stronger than corresponding attacks on block cipher (TM²=N²) since they can exploit the availability of lots of data.

Given the facts that stream ciphers appear to be less secure than block cipher and the rapid emergence of block cipher due to the availability of cheap VLSI-based electronic gates, memories and microprocessors, it appears that ultimately stream ciphers will be replaced by block ciphers in all departments except for some cliché applications which have:

a hardware oriented scheme with exceptionally small footprint (gates, power consumption, etc.).
a software oriented scheme with an exceptionally high speed.

The view seems to be vindicated by the fact that large number of applications which were initially based on stream ciphers have shifted to block ciphers.

References

"New European Schemes for Signatures, Integrity and Encryption (NESSIE) Project", http://www.cryptonessie.org.
NIST Federal Information Processing Standard Publication 140-2 "Security requirements for Cryptographic Modules". US National Institute for Standards and Technology, US Department of Commerce, June 2001. http://csrc.nist.gov/publications/fips.
Nicolas T. Courtois, Willi Meier, "Algebraic Attacks on Stream Ciphers with Linear Feedback", Extended version of Eurocrypt 2003 paper.
Christophe De Cannière,Thomas Johansson, Bart Preneel "Cryptanalysis of Bluetooth Cipher".
Miodrag J. Mihaljevic, Mark P.C. Fossorier and Hideki Imai, "A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack".
T. Johannesson and P. Jonsson, "Improved fast correlation attacks on stream ciphers via convolution codes", Advances in Cryptology-EUROCRYPT’99, Lecture Notes in Computer Science, vol. 1592, pp. 347-362,1999
T. Johannesson and P. Jonsson, "Fast correlation attacks based on turbo code technique", Advances in Cryptology-CRYPTO’99, Lecture Notes in Computer Science, vol. 1666, pp. 181-197,1999
W. Meier and O Staffelbach, "Fast Correlation attacks on certain stream ciphers", Journal of Cryptology, vol. 1, pp 159-176,1989.
K. Zeng and M. Huang, "On the linear syndrome method in cryptanalysis", Advances in Cryptology-CRYPTO’88, Lecture Notes in Computer Science, vol. 403, pp. 469-478,1990.
A. Biruykov and A. Shamir "Cryptanalytic Time/Memory/Data Tradeoff for Stream Ciphers", Advances in Cryptology-ASIACRYPT’2000, Lecture Notes in Computer Science, vol. 1807, pp. 573-588,2000.
M.E. Hellman "A cryptanalytic time-memory trade-off”,IEEE Trans. Inform. Theory, vol. IT-26, no. 4 , pp. 401-406,July 1980.
Hongjun Wu and Feng Bao, "Cryptanalysis of Stream Cipher COS (2,128) Mode I"

Continued 1 2

E-Mail Link

Your IP address will be sent with this e-mail