Cryptanalysis of Stream Ciphers

Cryptanalysis is the study of deciphering the encrypted message without knowing the secret key. A trivial attack to any cryptosystem is to try every possible key until the correct one is recovered. If the key size is k, attacker has to try 2^k keys in the worst case, and on the average 2^{k-1} keys. To detect the correct key, a plaintext/ciphertext pair is needed. However, if the plaintext contain redundancies, it may still be possible to recover the key using only the ciphertexts. One advantage of the attack is that it can be implemented in parallel. As the ability to compute increases, larger key sizes are needed. The size of the secret key should be large enough to avoid these exhaustive or brute force search attacks. In todays technology, 80-bit keys seem to offer acceptable level of security.

All other attacks applied to stream ciphers are compared to exhaustive key search in terms of time, data and memory complexity. Time complexity is related to the required number of primitive operations and can be separated into two parts, offline and online. The offline part is done once independent of the secret key and the results obtained in this part is used to attack the system in the online part. Data complexity considers the amount of data required for the attack, lastly, memory complexity is determined by the required amount of memory. The attack is considered to be successful if the maximum of time, data and memory complexity is less than the complexity of exhaustive search. Attacks with higher complexity are not be considered to be successful.

Ciphertext Only Attacks: In this type, the attacker aims to obtain information about the secret key or the plaintext by only observing the ciphertext. This kind of attack is successful if some information about the plaintext such as the language is available.Also, if plaintext is written using ASCII characters, it is very likely that the most significant bit of each character is equal to 0. In that case, ciphertext only attacks can be considered as known plaintext attacks.

Known Plaintext Attacks: Most of the attacks available in the literature use this scenario. Since keystream is generated independent of plaintext, this type is equivalent to known keystream attacks. Well known chosen plaintext or chosen ciphertext attacks are not suitable to analyze synchronous stream ciphers since chosen plaintext attack is also equivalent to the known plaintext attack.

Known IV or Chosen IV Attacks: In most of the protocols the value of IV is assumed to be public. In chosen IV attacks, the attacker is allowed to choose the set of IVs and resynchronize the cipher using this set.

The attack models against symmetric cryptosystems are divided into two groups depending on the intention of the attacker. Key recovery attacks aim to recover the secret key whereas distinguishing attacks aim to find deviations of cipher outputfrom ideal distribution. It is clear that distinguishing attacks are weaker compared to key recovery attacks that enable to decrypt anygiven encrypted message. However, distinguishing attacks are suitable to detect the cipher used during communication, this has significant importanceespecially in military applications.Moreover, in many cases, the idea of distinguishers may be improved to recover the key. It should also be noted that most of the candidates of the NESSIE project were broken by distinguishing attacks and were not included in the final report of the project.