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

{LANG_NAVORIGIN} Encryption
Arani Dasgupta 04/27/2005

Abstract

Cryptographic techniques play an important part in network security and stream ciphers are one of the main cryptographic techniques that play a very important part in maintaining security and protecting valuable information from potential misuse. Cryptanalysis of stream iphers are at least as important as the other encryption technique – the block cipher technique – and in military circles more important. The main objective of this paper is to evaluate the different cipher techniques to provide an idea of the cryptographic strength of the technique as well as to provide parameters to compare with other techniques.

Introduction

The stream cipher technique consists of encrypting each byte or each bit of the digital message. Examples of this type of encryption method are the Vernam the autokeyed Vigenère cipher and perhaps the most popular of them all – RC4 stream cipher deigned by Ronald Rivest.

The stream ciphers encryption is based on the employment of a sequence called keystream. A stream cipher usually encrypts one character at a time, using an encryption transformation which varies with time. Such a cipher is typically implemented by the use of a so-called pseudo-random number generator (PRNG) or a keystream generator which expands a short secret key into a long running key sequence. A keystream generator is equivalent to a final state machine that based on some secret key, generates a keystream for controlling an encryption transformation. The initial state of the keystream generator is determined by the secret key.

Most stream ciphers are based on simple devices that are easy to use and run efficiently such as a linear feedback shift register (LFSR). But the output of such devices is predictable and hence the output of these devices is used as inputs to some other non-linear function that produces the keystream. In general there are two main approaches for constructing keystream generator:

1. a construction that is resistant to all known attacks.
2. a construction which yields security under certain assumptions.

Though (i) is the most popular construction approach, it suffers from the shortcoming that security is not ensured even though it is known that none of the attacks have been successful. On the other hand approach (ii) implies to prove the absence of any attack under some assumptions. If somehow a attack is found, it only proves that the assumptions were wrong. This approach converts the problem of keystream security to a problem of assumption security.

General Evaluation Criteria

Usually the following criteria are considered while evaluating the security of a stream cipher:

1. An attack should be at least as hard as finding the secret key by exhaustive search of the key.
2. Existence of an attack which requires lesser resource than that predicted by the designer should make the algorithm less recommendable.
3. Stream ciphers should be evaluated under the stated environment. Thus consideration of vulnerability to side channel attacks must be considered.

Accordingly the major issues for security analysis include:

1. Resistance to cryptanalysis: A stream cipher should be resistant at the relevant security level to cryptanalytic attacks. However while considering the attack on the technique, various factors need to be considered, namely the overall complexity (both time and space) of the attack and the volume and type of attack required to mount such an attack. The type of attack may be any one of the following:
   1. Cipher-text only: This is the most powerful type of attack since it only requires passive eavesdropping on the part of the attacker to obtain the cipher-text. The information available to the cryptanalyst is minimal and may include information about the distribution of the plaintext. For example, information available may be as trivial as the language of the encrypted plaintext.
   2. Known Plain-text attack: This scenario assumes that the attacker already knows a portion of the plaintext. The aim may either be to know from the known part of the cipher-text, the secret key of the cipher or at least determine some unknown portion of the cipher text.
   3. Chosen Plain-text attack: In this case, the attacker has the ability to encrypt a plaintext of his choice. This can be achieved when an encryption box with a securely embedded unknown secret key is available or when it is possible to send chosen plaintext to the owner of the secret key and then eavesdrop the transmission of the chosen text in encrypted form to a third party.
   4. Chosen Cipher-text attack: This is similar to the previous case but also requires the ability to choose the cipher text for a decrypting device.
   5. Adaptive chosen plaintext or cipher text: This is a highly unrealistic but theoretically interesting situation. It assumes the ability of adaptive choice of encrypted text based on already available results of encryption (or decryption). This is possible only if the attacker has a device with an unknown secret key. From a ‘Learning Theory’ point of view, cryptanalysis of a cipher can be seen as a problem of learning the unknown parameter ‘k’ of a function f(x,k). The aim of the attacker is to learn ‘k’ using the minimum number of queries to the function.
   6. Related keys: This scenario assumes the knowledge (or choice) of relation between keys in two different encryptions in addition to one of the scenarios described earlier. This attack may discover important flaws in the key scheduling algorithm of the cipher.
   7. Partial knowledge of the key: In this scenario the attacker possess partial knowledge of the secret key (for example due to a flaw in the randomization procedure which generates the encryption keys ). In a good cipher the knowledge of part of the key should not make finding of rest of the key any easier. Otherwise an exhaustive search on such a cipher will be made much easier.
2. Design Philosophy and Transparency: An important consideration when assessing the security of a stream cipher is the design philosophy and transparency of the design. It is easier to have confidence in the assessment of the security if the design is clear and straightforward, and is based on well-understood mathematical and cryptographic principles.
3. Strength of Modified Primitives: One common technique to assess the strength of a stream cipher is to assess a modified one, obtained by changing or removing a component of the considered stream cipher. Conclusions about the original stream cipher based on assessment of the modified one have to be carefully considered as the influence may or may not be straightforward.
4. Cryptographic Environment: In certain cryptographic environments, a cryptographic technique may have been designed to posses intrinsic security advantages or disadvantages. Such properties should be considered when assessing security of a stream cipher, as well.
5. Testing: The purpose of testing is to highlight anomalies in the operation of a stream cipher that my indicate cryptographic weakness and require further investigation.

Your IP address will be sent with this e-mail

From e-mail to e-mail