Some Results On Design And Analysis Of Stream Ciphers

Stream cipher is one of the most common classes of encryption algorithms. It is small, fast and easy to implement in hardware or software. For this reason, stream ciphers are widely used in the commercial and military applications, especially in wireless communication. Therefore, design and analysis of stream ciphers are very important.Boolean functions are very important components in stream ciphers. The safety of cryptography systems are closely related to the cryptographic prop-erties of Boolean functions. Hence, it is very important to construct Boolean functions with good cryptographic properties. The present thesis considers the construction of Boolean functions with high algebraic immunity and the con-tributions are as follows.(1) The construction of even-variable symmetric Boolean functions with maximum algebraic immunity is an open problem. It has been proved that the structures of these Boolean functions are very complex. In this thesis, we show the construction of all even-variable symmetric Boolean functions.(2) We explicitly construct a large class of symmetric Boolean functions on2k variables with algebraic immunity not less than d, where integer k is given arbitrarily and d is a given suffix of k in binary representation. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than d is derived, which is (2wt(n)+1)2[log2n]. As far as we know, this is the first lower bound of this kind.Besides, the pseudo-random sequence generators are core components of most stream ciphers. FCSR is one of the new pseudo-random sequence genera-tors. F-FCSR-H v3, F-FCSR-16v3and BEAN are FCSR based stream cipher. In this thesis, we analyze those ciphers and the contributions are as follows.(1) In the present thesis, we show a generalized birthday algorithm for searching linear properties of FCSR output sequence. Based on this algorithm, we explicitly show a new such attack on F-FCSR-H v3with online complexities237.2, and offline complexities (for finding the linear relations)256.2, respectively. We focus on this application in the paper, but the presented algorithm is general and applicable to all FCSR combiners with linear filter.(2) Fast correlation attacks were only applicable to LFSR based ciphers. But for FCSR, there is no fast correlation attack before. In this thesis,we generalize the fast correlation attack from LFSR to FCSR. In the generalized model, a new noise on the binary symmetric channel (BSC) is added. As example, we apply the new attack on F-FCSR-16v3. This is the first fast correlation attack on FCSR based stream cipher, and also the first key recovery attack on stream cipher F-FSCR-16v3.(3) A weakness in BEAN was first found by Agren and Hell in2011, re-sulting in a key recovery attack slightly better than brute force. In this thesis, we present new correlations between state and keystream with large statistical advantage, leading to a much more efficient key recovery attack. The time and data complexities of this attack are257.53and259.94, respectively. Moreover, two new output functions are provided as alternatives, which are more efficient than the function used in BEAN and are immune to all attacks proposed on the cipher. Also, suggestions for improving the FCSRs are given.