Research Of Distinguishing Attacks On ESTREAM Candidates

A distinguishing attack is an efcient cryptanalytic method. Its main idea is usinghypothesis testing to tell whether a sequence has been generated by the keystream gen-erator or random generator. Although stream ciphers are widely used in communication,business and military encryption, the output sequence does not always get the truly ran-dom. So the distinguishing attack on stream ciphers has very important value in boththeory and applications, it has been and still remains one of the hot research tasks incryptology. This dissertation investigates the eSTREAM candidate stream ciphers, withemphasis on Achterbahn, HC-256, Sosemanuk and Sfnks. The author obtains the mainresults as follows:(1). For the Boolean combining function of stream cipher Achterbahn-v2andAchterbahn-128, a linear distinguishing attack based on better parity check is pro-posed using the idea of Plasencia’s attack. Then the key is recovered by the meet-in-the-meddle attack. Compared with the best known attack, the keystream bitscan be reduced from O(252) to O(251.6) for Achterbahn-v2. Furthermore, it can bereduced from O(255.61) to O(255.07) for Achterbahn-128.(2). For stream cipher HC-256′which is a variant of HC-256, by fnding the weaknesson the even positions of output keystream sequence {s2i}, a distinguishing attack isproposed. Firstly, on the even positions of the output keystream bits, the diferentnonlinear Boolean functions replace the state update functions. Furthermore, in theleast signifcant bit a distinguisher is constructed. The result shows that it needsabout O(2313) keystream bits to distinguish HC-256’ form random sequence withadvantage of0.9545.(3). For the stream cipher Sosemanuk with a fnite state machine (FSM) and Serpent1,a linear distinguishing attack is proposed using the linear masking idea of Nybergand Lee’s attack. This method frst uses linear maskings to replace modular addi-tions and Trans functions by exclusive ORs (XORs). Then, linear approximationof the FSM uses diferent maskings. Finally, a distinguisher is built by linear ap-proximation of the output Boolean function. The results show that the keystreamgenerated by Sosemanuk is distinguishable from a random sequence after observingapproximately O(2221) bits.(4). For the stream cipher Sfnks which is based on a linear feedback shift register(LFSR), a fast key recovery method is proposed using the ideas of the algebraic cube attack. The idea is to fnd more low degree equations by cube attack, thenusing algebraic attack to recover the secret keys. Compared with the best knownattack, the computation complexity of this attack decreases from O(271) to O(243).Moreover, the keystream bits decrease from O(243) to O(221).(5). The security of the stream cipher LILI-128is studied with the algebraic cube attack.Based on the characteristics of the frst register LFSRcbeing used to clock thesecond register LFSRd, a key recover attack is presented by algebraic cube attackswhen the state of the frst register LFSRcis guessed and clocked2391clocks ata time, respectively. Comparisons show that the algebraic cube attack gains someadvantages over the existing attacks.