Algebraic cryptanalysis of stream ciphers using decomposition of Boolean function

Algebraic attack is an important attack strategy against symmetric ciphers, particularly stream ciphers. The most vital issue of this attack strategy is to reduce the degree of the algebraic equations as much as possible in order to obtain a lower time complexity. This paper first presents one such means of obtaining low degree equations using the decomposition of Boolean functions. This method overcomes the three major drawbacks of fast algebraic attack. We discuss the general attack strategy using decomposable Boolean function. We also demonstrate the decomposition of some Boolean function used in practical stream ciphers. Then we find a bound on the degree of a function to be multiplied with a given function so that the product has low degree decomposition. The second major contribution of this paper is a new probabilistic algebraic attack for LFSR based stream cipher by using decomposition of Boolean function. Finally we apply our method to the stream cipher Grain-v1, which is one of the finalist of estream call for stream cipher proposals, by injecting fault in one bit of NFSR.