Cryptanalysis Techniques for Stream Cipher: A Survey <s> Time Memory Tradeoff Attacks <s> In 1980 Hellman introduced a general technique for breaking arbitrary block ciphers with N possible keys in time T and memory M related by the tradeoff curve TM2 = N2 for 1 ≤ T ≤ N. Recently, Babbage and Golic pointed out that a different TM = N tradeoff attack for 1 ≤ T ≤ D is applicable to stream ciphers, where D is the amount of output data available to the attacker. In this paper we show that a combination of the two approaches has an improved time/memory/data tradeoff for stream ciphers of the form TM2D2 = N2 for any D2 ≤ T ≤ N. In addition, we show that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters. <s> BIB001 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Time Memory Tradeoff Attacks <s> Given a certain amount of known keystream from a keystream generator (KG), the most obvious way to determine the state of the generator is to search through all possible states, checking for a match between the resulting and observed keystream. In this paper, we draw attention to two attacks on stream cipher systems which, although their complexity grows exponentially with the size of the KG state, are more efficient than a simple-minded search through all possible KG states. Indeed, given sufficient storage and sufficient known keystream, each attack can almost halve the effective entropy of the state to be searched. <s> BIB002 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Time Memory Tradeoff Attacks <s> A binary stream cipher, known as A5, consisting of three short LFSRs of total length 64 that are mutually clocked in the stop/go manner is cryptanalyzed. It is allegedly used in the GSM standard for digital cellular mobile telephones. Very short keystream sequences are generated from different initial states obtained by combining a 64-bit secret session key and a known 22-bit public key. A basic divide-and-conquer attack recovering the unknown initial state from a known keystream sequence is first introduced. It exploits the specific clocking rule used and has average computational complexity around 240. A time-memory trade-off attack based on the birthday paradox which yields the unknown internal state at a known time for a known keystream sequence is then pointed out. The attack is successful if T ċ M ≥ 2633.32, where T and M are the required computational time and memory (in 128-bit words), respectively. The precomputation time is O(M) and the required number of known keystream sequences generated from different public keys is about T/102. For example, one can choose T ≅ 227.67 and M ≅ 235.65. To obtain the secret session key from the determined internal state, a so-called internal state reversion attack is proposed and analyzed by the theory of critical and subcritical branching processes. <s> BIB003 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Time Memory Tradeoff Attacks <s> A5/1 is the strong version of the encryption algorithm used by about 130 million GSM customers in Europe to protect the over-the-air privacy of their cellular voice and data communication. The best published attacks against it require between 240 and 245 steps. This level of security makes it vulnerable to hardware-based attacks by large organizations, but not to software-based attacks on multiple targets by hackers. ::: ::: In this paper we describe new attacks on A5/1, which are based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets. After a 248 parallelizable data preparation stage (which has to be carried out only once), the actual attacks can be carried out in real time on a single PC. ::: ::: The first attack requires the output of the A5/1 algorithm during the first two minutes of the conversation, and computes the key in about one second. The second attack requires the output of the A5/1 algorithm during about two seconds of the conversation, and computes the key in several minutes. The two attacks are related, but use different types of time-memory tradeoffs. The attacks were verified with actual implementations, except for the preprocessing stage which was extensively sampled rather than completely executed. ::: ::: REMARK: We based our attack on the version of the algorithm which was derived by reverse engineering an actual GSM telephone and published at http://www.scard.org. We would like to thank the GSM organization for graciously confirming to us the correctness of this unofficial description. In addition, we would like to stress that this paper considers the narrow issue of the cryptographic strength of A5/1, and not the broader issue of the practical security of fielded GSM systems, about which we make no claims. <s> BIB004
A time memory tradeoff attack is a method of cryptanalysis that aims to attack a cryptographic primitive with lower complexity than look up table and an online complexity lower than exhaustive key search. TMTO is an improvement to the exhaustive key search attack that trades off computational time against memory complexity  . This attack can be divided into two phases; an offline phase or pre-computation phase and online phase. In offline phase a table is constructed in like lookup table method by selecting different random keys and generating the output for each chosen key. These pairs of output strings and keys are stored in an indexed table by the output strings. In the second phase or online phase, the attacker observes the output generated by unknown keys. Then these outputs are matched with the outputs of the table generated in the offline phase. If a match is found then corresponding key will be the key off the matched output. Amirazizi and Hellmen were the first to propose Time memory processor trade-off attack  on block ciphers and in case of stream ciphers, TMTO was proposed by Babbage BIB002 in 1995 and Golic BIB003 in 1997 independently. Later on Biryukov and Samir combined Babbage and Golic scheme with Hellmen attack BIB001 . This attack was further refined by Birykov, Shamir and Wagner and applied on A5/1 BIB004 . To avoid TMTO on stream ciphers, Hong and Sarkar  suggested that state size should be equal to or greater than sum of key size and size of IV and it should be random. Babbabge BIB002 and Golic BIB003 suggested that state size should be at least double the size of key.