Authors: Dibyendu Roy Pratish Datta Sourav Mukhopadhyay
Publish Date: 2014/10/28
Volume: 49, Issue: 1-2, Pages: 397-417
Abstract
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 Grainv1 which is one of the finalist of estream call for stream cipher proposals by injecting fault in one bit of NFSR
Keywords: