RSA Laboratories

2.4.7 What are the most important attacks on stream ciphers?

The most typical use of a stream cipher for encryption is to generate a keystream in a way that depends on the secret key and then to combine this (typically using bitwise XOR) with the message being encrypted.

It is imperative the keystream "looks" random; that is, after seeing increasing amounts of the keystream, an adversary should have no additional advantage in being able to predict any of the subsequent bits of the sequence. While there are some attempts to guarantee this property in a provable way, most stream ciphers rely on ad hoc analysis. A necessary condition for a secure stream cipher is that it pass a battery of statistical tests which assess (among other things) the frequencies with which individual bits or consecutive patterns of bits of different sizes occur. Such tests might also check for correlation between bits of the sequence occurring at some time instant and those at other points in the sequence. Clearly the amount of statistical testing will depend on the thoroughness of the designer. It is a very rare and very poor stream cipher that does not pass most suites of statistical tests.

A keystream might potentially have structural weaknesses that allow an adversary to deduce some of the keystream. Most obviously, if the period of a keystream, that is, the number of bits in the keystream before it begins to repeat again, is too short, the adversary can apply discovered parts of the keystream to help in the decryption of other parts of the ciphertext. A stream cipher design should be accompanied by a guarantee of the minimum period for the keystreams that might be generated or alternatively, good theoretical evidence for the value of the lower bound to such a period. Without this, the user of the cryptosystem cannot be assured that a given keystream will not repeat far sooner than might be required for cryptographic safety.

A more involved set of structural weaknesses might offer the opportunity of finding alternative ways to generate part or even the whole of the keystream. Chief among these approaches might be using a linear feedback shift register to replicate part of the sequence. The motivation to use a linear feedback shift register is due to an algorithm of Berlekamp and Massey that takes as input a finite sequence of bits and generates as output the details of a linear feedback shift register that could be used to generate that sequence. This gives rise to the measure of security known as the linear complexity of a sequence; for a given sequence, the linear complexity is the size of the linear feedback shift register that needs to be used to replicate the sequence. Clearly a necessary condition for the security of a stream cipher is that the sequences it produces have a high linear complexity. RSA Laboratories Technical Report TR-801 [Koç95] describes in more detail some of these issues and also some of the other alternative measures of complexity that might be of interest to the cryptographer and cryptanalyst.

Other attacks attempt to recover part of the secret key that was used. Apart from the most obvious attack of searching for the key by brute force, a powerful class of attacks can be described by the term divide and conquer. During off-line analysis the cryptanalyst identifies some part of the key that has a direct and immediate effect on some aspect or component of the generated keystream. By performing a brute-force search over this smaller part of the secret key and observing how well the sequences generated match the real keystream, the cryptanalyst can potentially deduce the correct value for this smaller fraction of the secret key [Koç95]. This correlation between the keystream produced after making some guess to part of the key and the intercepted keystream gives rise to what are termed correlation attacks and later the more efficient fast correlation attacks.

Finally there are some implementation considerations. A synchronous stream cipher allows an adversary to change bits in the plaintext without any error-propagation to the rest of the message. If authentication of the message being encrypted is required, the use of a cryptographic MAC might be advisable. As a separate implementation issue synchronization between sender and receiver might sometimes be lost with a stream cipher and some method is required is ensure the keystreams can be put back into step. One typical way of doing this is for the sender of the message to intersperse synchronization markers into the transmission so only that part of the transmission which lies between synchronization markers might be lost. This process however does carry some security implications.

Top of the page