A generic weakness of the k-normal boolean functions exposed to dedicated algebraic attack

Abstract

A Boolean function is k-normal if it is constant on a k-dimensional flat of its domain. This paper demonstrates that k-normality of a Boolean function can be exploited to mount a dedicated algebraic attack on a stream cipher of the nonlinear filter generator type, which employs a k-normal Boolean function as its filter function. The cryptanalysis is based on the possibility for pre-computing a table of the state-keystream pairs via solving certain system of algebraic equations as a consequence of the employed k-normal Boolean function. This pre-computed table is the main origin for mounting the cryptanalysis and it is independent of a the sample for cryptanalysis and the secret key employed for generating the sample.