On Several Cryptanalytic Techniques Of Stream Ciphers

As an important cryptographic primitive, stream ciphers have found widespreadapplications in secure communications. Cryptanalytic technology has been proven in-dispensable to the design of stream ciphers, and has been one of the most di?cult andactive research areas in cryptology. This dissertation focuses on the theory and applica-tions of stream cipher cryptanalytic technology. The contributions of the dissertationare listed as follows:(1) Algebraic attacks are proposed on two kinds of nonlinear filter generators withsymmetric Boolean functions as the filter functions. Di?erent from the classicalalgebraic attacks, the proposed attacks utilize a combinatorial property of thelinear feedback shift register (LFSR) and the symmetric Boolean function to de-rive a low–degree algebraic relation, and hence the complexities of the proposedattacks are independent of the algebraic immunity (AI) of the filter functions.It is shown that the improper combining the LFSR with the filter function canrender the filter generator vulnerable to algebraic attacks. As a result, the com-binatorial way of the LFSR and the filter function with large AI must be properlydeployed in order to withstand the proposed algebraic attacks.(2) A resynchronization attack is proposed on stream ciphers filtered by Maiorana–McFarland (M–M) functions and equipped with a linear resynchronization mech-anism. The proposed attack utilizes the linearity weakness of the resynchroniza-tion mechanism and the partial linearity of M–M functions, and then applies thelinear consistency test method to recover the secret key. It is shown that an M–M function should not be implemented by itself but rather in combination withother nonlinear components in stream ciphers. It is also shown that linear resyn-chronization mechanisms should be designed elaborately in synchronous streamciphers to withstand the proposed attack despite their simple implementationand high e?ciency.(3) Based on the analysis of the algebraic structure of the stream cipher Grain,three design weaknesses of the keystream generator are pointed out. Althoughwe fail to provide a general key–recovery attack on the generator, knowing anintermediate state of the keystream generator does help us successfully launch akey–recovery attack on Grain. The Grain keystream generator turns out to havedesign weaknesses. Furthermore, an improvement on the generator is presentedto withstand the proposed key–recovery attack. (4) The security of the multiplexer generator is investigated with respect to algebraicattacks. All the linearly independent lowest degree annihilators of the multiplexfunction are determined and accordingly an algebraic attack on the multiplexergenerator is presented. Comparisons show that the proposed attack gains someadvantages over the existing attacks in some situations.